정렬 알고리즘

선택 정렬

• 선택정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꿈
• 매번 가장 작은 것을 선택한다

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

for i in range(len(array)):
    min_index = i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]
    
print(array)

• 시간복잡도 : O(N^2)

삽입 정렬

• 삽입정렬 : 정렬되어 있는 데이터리스트에서 적절한 위치를 찾은 뒤 그 위치에 삽입
• 특정한 데이터를 적절한 위치에 삽입한다 (그 앞까지 데이터는 이미 정렬되어있다고 가정)

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

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
        
print(array)

• 시간복잡도 : O(N^2), 최선의 경우(데이터가 거의 정렬되어있는 경우) O(N)

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다
• 기준(피벗) 설정 -> 큰 수와 작은 수 교환 -> 리스트 반으로 나눔
• 리스트의 첫번째 데이터를 피벗으로 정한다
• 피벗을 기준으로 큰데이터와 작은 데이터의 위치를 바꿔서 분할
• 피벗을 옮기고 왼쪽과 오른쪽을 똑같이

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

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[pivot] = array[pivot], array[left]
    
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

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

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(array))

• 시간복잡도 : O(NlogN)

계수 정렬

• 특정한 조건이 부합할 때만(데이터 크기가 제한되어 있을 때 빠름) 사용할 수 있지만 매우 빠른 알고리즘
• 비교 기반 정렬 알고리즘 아님
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다

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

count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1
    
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end = ' ')

• 시간복잡도 : O(N+K)
• 공간복잡도 : O(N+K)
  • 데이터의 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리