[Algorithm] 여러 정렬 알고리즘

정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것

 

Selection Sort

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복

 

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] # Python Swap Code

print(array)

이 예제 코드에서 Swap 코드를 주목하자. 

Python에서는 특정 리스트가 주어졌을 시 주석 부분과 같이 두 변수의 위치를 간단하게 변경할 수 있다.

시간 복잡도

다른 알고리즘들에 비해 매우 비효율적인 모습을 보인다.

데이터의 개수 (N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
100	0.0123 초	0.00156 초	0.00000753 초
1,000	0.354 초	0.00343 초	0.0000365 초
10,000	15.475 초	0.0312 초	0.000248 초

 

 

Insertion Sort

특정 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부르며, 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

 

따라서 삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 보고, 두 번째 데이터부터 시작한다.

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)

시간 복잡도

Selection Sort와 마찬가지로 O(N^2)의 시간 복잡도를 가진다. 그러나 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 왜냐하면 중첩 반복문 중 대부분이 else 절로 넘어갈 것이기 때문이다. 최선의 경우, 즉 이미 리스트 내 데이터가 모두 정렬되어 있는 경우 O(N)의 시간 복잡도를 갖는다.

 

Quick Sort

정렬 알고리즘 중 가장 많이 사용되는 알고리즘으로, 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작하는 알고리즘이다. 

 

본 포스트에서는 '리스트에서 첫 번째 데이터를 피벗으로 정한다' 의 분할 방식을 갖는 호어 분할 방식으로 설명한다.

 

array = [7, 5, 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[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1 , end)
    
quick_sort(array, 0, len(array)-1)
print(array)

 Python 언어의 장점을 더 살린다면 다음과 같이 구현할 수 있다.

array = [7, 5, 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))

구현은 한층 편리해지지만, left_side와 right_side 리스트 선언 부분을 보면 비교 연산은 리스트 내 원소 만큼 실시해야 큰 값이나 작은 값이 나오면 즉각 비교 연산을 멈춘 앞선 코드와 다르게 연산횟수가 증가한다. 따라서 시간 복잡도는 비교적 느린 편이다.

 

시간 복잡도

퀵 정렬의 시간 복잡도는 O(NlogN)으로, Selection Sort와 Insertion Sort에 비해 매우 빠른 편이다. 이러한 이유는 분할에 있는데, 분할이 이루어지는 횟수가 기하급수적으로 감소하기 때문이다.

데이터의 개수(N)	N^2(선택 정렬, 삽입 정렬)	NlogN(퀵 정렬)
1,000	approx 1,000,000	approx 10,000
1,000,000	approx 1,000,000,000,000	approx 20,000,000

다만, 최악의 경우 시간 복잡도는 O(N^2)가 된다. 이 때의 최악의 경우는 이미 데이터가 정렬되어 있는데 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때를 말한다.

 

Count Sort

특정 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘이다.

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용이 가능하다.

(일반적으로 가장 정수 형태 데이터의 Range가 1,000,000을 넘지 않을 때 효과적으로 사용이 가능)

 

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다.

 

구현 방법

가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화하고, 각 데이터가 몇 번 등장했는지 데이터에 대응하는 인덱스에 그 횟수를 기록한다. 이 과정을 거쳐 생성된 리스트 내 데이터 자체가 정렬된 형태 그 자체로 볼 수 있다.

 

array = [7, 5, 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=' ')

시간 복잡도

원소의 개수 N, 리스트 내 최댓값을 K라고 할 때 계수 정렬의 시간 복잡도는 O(N + K)이다.

공간 복잡도

때에 따라서 심각한 비효율성을 초래할 수 있는데, 리스트를 따로 선언하는 것이기에 리스트의 크기가 최대 100만 개까지 선언해야 할 수 있다. 빠른 시간 복잡도만 보고 사용하기 보다는 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합한 알고리즘이라고 할 수 있다. 공간 복잡도 또한 O(N + K)이다.

 

Python의 정렬 라이브러리

* sorted() : 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌으며, 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 리스트, 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력한다.

 

* sort(): 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬하는 방법으로, 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.