[Algorithm] 정렬 (Sorting)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다.

정렬(Sorting)이란

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

정렬 알고리즘은 이진 탐색(Binary Search)의 전처리 과정이기도 하다.

정렬 알고리즘은 굉장히 다양한데 이 중에서 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 다뤄본다.

 

 

선택 정렬(Selection Sort)

"데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다."

이처럼 가장 작은 것을 선택하는 방식의 정렬 알고리즘을 선택 정렬이라고 한다.

 

코드

def selection_sort(array):
    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
        # Swap
        array[i], array[min_index] = array[min_index], array[i]

 

Swap

• 두 변수의 위치를 변경하는 작업을 의미한다
  • Python 코드

    • array[i], array[j] = array[j], array[i]

  • C 언어 코드

    • int temp = array[i];
      array[i] = array[j];
      array[j] = array[i];

 

시간 복잡도

N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하므로 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2로 N x (N + 2) / 2 번의 연산을 수행한다고 가정한다.

 

따라서 선택 정렬의 시간 복잡도는 O(N^2)이다.

 

 

 

삽입 정렬(Insertion Sort)

"데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 과정을 반복한다."

이처럼 데이터를 적절한 위치에 삽입하는 방식의 알고리즘을 삽입 정렬이라고 한다.

 

선택 정렬 vs 삽입 정렬

• 선택 정렬
  • 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교한 후 위치를 바꾼다.
• 삽입 정렬
  • 필요할 때 위치를 바꾼다.
  • 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

 

따라서, 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘이다.

 

코드

def insertion_sort(array):
    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

 

시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)인데, 만약 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 즉, 최선의 경우 O(N)의 시간 복잡도를, 평균과 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

 

 

 

퀵 정렬(Quick Sort)

"기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다."

이처럼 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식의 정렬 알고리즘을 퀵 정렬이라고 한다.

큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 피벗(Pivot)이라 한다. 퀵 정렬을 수행하기 전에 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분한다.

 

호어 분할(Hoare Partition)

리스트에서 첫 번째 데이터를 피벗으로 정하는 분할 방식이다.

아래 코드는 호어 분할 방식을 이용한다.

 

코드

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)

 

시간 복잡도

퀵 정렬의 평균과 최선의 시간 복잡도는 O(NlogN)이다. 퀵 정렬에서 최선의 경우는 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확이 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할하는 경우다.

최악의 경우는 매번 피벗으로 정렬 기준 가장 왼쪽 혹은 오른쪽 데이터를 삼을 때이다. 이때 시간 복잡도는 O(N^2)된다.

 

분할 횟수가 관건

최선의 경우 총 n개의 데이터를 정렬할 때, 피벗이 정확이 절반으로 분할하므로 총 log2n번 분할을 진행하게 되며 각각에 대해 n번 연산을 진행하므로 시간복잡도는 O(nlogn)이 된다.

최악의 경우 총 n개의 데이터를 정렬할 때, 피벗이 매번 정렬 기준 가장 왼쪽 혹은 가장 오른쪽 데이터를 기준으로 분할하므로 총 n번 분할을 진행하게 되며 각각에 대해 n번 연산을 진행하므로 시간복잡도는 O(n^2)이 된다.

 

** 기본 정렬 라이브러리는 O(NlogN)을 보장한다. **

 

계수 정렬

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 특히, 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

이처럼 계수 정렬(Count Sort)은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다.

 

 

코드

def count_sort(array):
    # 모든 범위를 포함하는 리스트 선언
    count = [0] * (max(array) + 1)
    for i in range(len(array)):
        count[array[i]] += 1
        
    n = 0
    for i in range(len(count)):
        for j in range(count[i]):
            array[n] = i
            n += 1

 

시간 복잡도

데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다.

계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복을 수행해야 하기 때문이다.

 

공간 복잡도

계수 정렬은 때에 따라서 매우 공간 비효율적인데, 데이터가 0과 999,999 단 2개만 존재한다고 가정할 때 정렬을 위해 선언하는 리스트는 100만 개의 크기이다. 따라서 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

즉 데이터의 크기가 한정되어 있고, 중복된 데이터가 많을 수록 계수 정렬을 사용하기 유리하다.

 

기수 정렬(Radix Sort)과 계수 정렬(Count Sort)

현존하는 정렬 알고리즘 중에서 계수 정렬은 기수 정렬(Radix Sort)와 더불어 가장 빠르다고 볼 수 있다.

보통 기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다.