코딩묻은 디자이너

1. 카운팅정렬이란

요소의 계수를 세고 정렬하는 알고리즘

리스트의 값의 범위가 크지 않을 때 효율적이다

지금까지 많은 알고리즘을 배우진 않았지만(버블 정렬, 카운팅 정렬, 선택정렬... 정도) 가장 이해가 힘들었던 정렬 중 하나로, 몇번이나 손코딩을 해야했다

2. 선택정렬 파이썬 코드

# 카운팅 정렬

nums = [1, 5, 8, 9, 1, 3, 4, 6, 5, 7, 6, 1, 1, 3, 2]

sort_nums = [0] * len(nums)         #요소들을 정렬해줄 배열을 선언한다
big_num = -1                        #big_num은 요소들 중 가장 큰 값을 의미
for i in nums:
    if big_num < i:
        big_num = i

counts = [0] * (big_num + 1)        #가장 큰 값까지 카운팅 해줄 배열을 선언한다


for i in range(len(nums)):
    counts[nums[i]] += 1            #각 요소의 자리에 (해당 코드의 경우 9까지) 요소의 갯수를 더해준다
print(counts)                       #[0, 4, 1, 2, 1, 2, 2, 1, 1, 1]


for i in range(1, len(counts)):
    counts[i] += counts[i - 1]      # 배열에 누적값 표현
print(counts)                       #[0, 4, 5, 7, 8, 10, 12, 13, 14, 15]

for i in range(len(nums) - 1, -1, -1): # 뒤에서 부터 시행하는 이유는 안정정렬을 위해서
    n = nums[i]
    counts[n] -= 1
    idx = counts[n]
    sort_nums[idx] = n

print(sort_nums)

시간복잡도는 O(NM) N이 큰 경우 O(N), M이 큰 경우 O(M)이라고,,, 생각했는데 다른 블로그들을 보아 O(N) 인 것 같다

1. 이진 검색 알고리즘이란

정렬되어있는 리스트에서 특정한 값의 위치를 찾는 알고리즘으로

찾고자 하는 값이 중간 값보다 크면 중앙값(또는 중앙값 +1)이 새로운 최솟값이 되어 다시 값을 찾는다

검색이 반복될 때마다 목표값을 찾을 확률이 두 배가 된다.

업다운 게임과 알고리즘의 형태가 비슷하다고 생각한다

2. python 코드

def binarySearch(a, key):
    start = 0
    end = len(a)-1

    while start <= end:
        middle = (start + end) // 2
        if a[middle] == key:
            return True
        elif a[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15]

print(binarySearch(arr, 4))
print(binarySearch(arr,12))

True
False

4는 배열 안에 있기 때문에 True 12는 배열에 존재하지 않기 때문에 False를 반환한다

이진탐색 코드는 반드시 '정렬된 리스트'에서 실행되어야 한다.

1. 버블정렬이란

  인접한 두 원소를 비교하여 정렬하는 알고리즘

2. 버블정렬 특징

  코드가 단순하여 구현이 간단하다

  하나의 요소가 끝까지 이동하기 위해 모든 요소와 교환되어야 하기 때문에 속도가 느리다

3. 버블 정렬 파이썬 코드

for i in range(len(a)-1, 0, -1):
    for j in range(0, i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

뒤에서 부터 탐색하는 이유는 안정정렬을 위해서라고 한다.

 def BubbleSort(a):
     for i in range(len(a)):
         for j in range(i , len(a)):
             if a[i] > a[j]:
                 a[i],a[j] = a[j],a[i]
     return a

버블정렬을 접하고 스스로 다음과 같은 코드를 구현해보았다

하지만 해당 코드는 가장 인접한 요소 끼리의 교환이 아닌 인덱스i 를 가진 값과 j 를 가진 값을 교환하는 것이기 때문에 선택정렬과 버블정렬이 섞인 코드라고 볼 수 있다고 한다...

오름/내림차순 정렬을 하기 위해 스스로 처음 만들었던 코드 형태라 그런지 이 코드가 익숙해서 계속 사용하게 된다...