말로만하는 - 정렬 알고리즘(for 기술면접)

정렬 역시 프로그래밍 기술면접 단골질문이다. 정렬은 기술면접을 떠나서 자료구조/알고리즘 과목에서도 기초로 배운다. 다양한 방법으로 구현할 수 있고, 구현방법에 따라서 시간복잡도 역시 천차만별이기 때문에 학습용으로 제격이 아닐까. 이번 글에서는 6가지 대표적인 정렬 알고리즘에 대해서 정리해보았다. 기술면접을 대비한 정리로 ‘말/글’로 표현하는 데에 집중되어 있으며, 파이썬 코드를 첨부하였다. (참고로 이 글에 구현된 quick sort 코드의 경우 구현의 편의 상 새로운 리스트를 만드는 과정으로 인해 runtime이 매우 길어 개선이 필요하다.)

정렬 알고리즘의 분류

정렬 알고리즘에는 대표적으로 selection sort, insertion sort, bubble sort, quick sort, merge sort등이 있다. 정렬알고리즘은 실행방법에 따라서 또는 정렬 장소에 따라서 분류할 수 있다.

실행방법

실행 방법에 따라서 비교식 정렬(comparative sort)과 분산식 정렬(distribute sort)로 분류할 수 있다. 비교식 정렬은 두 값을 비교하여 교환하며 정렬해나가는 방법이고, 분산식 정렬은 키값을 기준으로 부분집합을 만든 뒤 각 부분집합을 정렬해나가는 방법이다.

정렬 장소

정렬 장소에 따라서 내부 정렬(internal sort)와 외부 정렬(external sort)로 분류할 수 있다. 내부 정렬은 정렬할 데이터를 메모리에 모두 올려서 정렬하는 방식이다. 반면, 외부 정렬은 주기억장치에 정렬할 데이터를 모두 올리기 어려운 경우에 보조기억장치를 활용하는 방법이다. 주기억장치에 올릴 수 있을 만큼의 데이터만 올린 뒤 내부정렬 방법을 사용하여 정렬하고 정렬된 데이터를 보조기억장치에 쓴다. 정렬된 데이터가 N개 있으면, 차례로 일부분씩 불러와 merge sort와 같은 방법으로 정렬하여 보조기억장치에 쓴다.
이제 각 정렬방식을 비교해보자.

선택정렬(selection sort)

가장 작은 것을 선택해서 앞으로 보내는 정렬기법.

• 내부정렬 중 교환방식에 의한 정렬기법이다.
• i번째에 올 데이터를 i+1 ~ N(끝)번째 원소 중 i번째 원소보다 작은 값 중 가장 작은 값을 선택하여 i번째 원소와 교환한다. i를 0부터 N-1까지 순회하면 차례대로 정렬된다.
• 시간복잡도는 min/max O(n제곱)/O(n제곱)이다.

  def selection_sort(A):
    N = len(A)
    for i in range(N-1):
        min_idx = i
        for j in range(i+1, N, 1):
            if A[j] < A[min_idx]:
                min_idx = j
        if min_idx != i:
            A[min_idx], A[i] = A[i], A[min_idx]
    return A
  

버블정렬(bubble sort)

연속적인 두 원소끼리 비교해서 큰 값을 뒤로 보내나가는 정렬 기법이다.

• 내부정렬 중 교환방식에 의한 정렬기법이다.
• 첫 번째 원소와 두 번째 원소를 비교하여 대소관계가 안맞으면 스왑해준다. 마찬가지로 두 번째 원소와 세 번째 원소도 동일한 과정을 반복한다. 각 루프를 돌면 끝에서부터 정렬된 값들이 추가된다.
• 시간복잡도는 min/max O(n제곱)/O(n제곱)이다.
• 재밌는 점은, 시간복잡도는 선택정렬과 동일하지만 runtime은 선택정렬보다 크다. 선택정렬보다 스왑 할 경우의수가 많기 때문이다. 실제로, O(n제곱)의 시간복잡도를 가지는 정렬알고리즘 중 runtime이 가장 느린 것으로 보인다.

  def bubble_sort(A):
    N = len(A)
    for k in range(N-1):
        for i in range(0, N-k-1):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
    return A
  

삽입정렬(insertion sort)

각 숫자를 적절한 위치에 삽입하는 정렬 기법.

• 내부정렬 중 삽입방식에 의한 정렬기법이다.
• i번째 원소를 이미 정렬된 i-1번째 까지의 원소과 비교하여 적절한 위치에 삽입한 뒤 나머지 원소들을 한 칸씩 shift한다. i를 1부터 N까지 iterate하면 정렬된다.
• 손 안의 카드를 정렬하는 방법과 동일하다.
• 최악의 경우 O(n제곱), 최선의 경우에는 이동하지 않고 비교만 할 경우에 O(n) 시간복잡도를 가진다.

  def insertion_sort(A):
    N = len(A)
    for i in range(1, N):
        for j in range(i-1):
            if A[i] < A[j]:
                A[j:i+1] = [A[i]] + A[j:i]
                break
    return A
  

퀵정렬(quick sort)

리스트 내 임의의 값을 기준으로 작은 값들/큰 값들 두 부분으로 나눈 뒤 재귀적으로 소팅하는 방법이다.

• 리스트에서 임의의 원소인 pivot을 고른다. pivot보다 작은 값들을 리스트에, pivot보다 큰 값들을 또 다른 리스트에 담고 두 리스트를 재귀적으로 quick sort 한다.
• 리스트의 길이가 1이하가 되면 리스트 자체를 return함으로써 재귀는 끝난다.
• 파이썬에서는 아래와 같이 간편하게 구현할 수 있는데 아래와 같은 코드에서는 사실 새 리스트 두 개를 만드는 부분때문에 코드의 runtime이 다른 정렬에 비해 매우 크다.

  def quick_sort(A):
    N = len(A)
    if N <= 1:
        return A
      
    left, right = [], []
    pivot = A[-1]
    now = [pivot]
    for i in range(N-1):
        if A[i] < pivot:
            left.append(A[i])
        elif A[i] > pivot:
            right.append(A[i])
        else:
            now.append(A[i])
    return quick_sort(left) + now + quick_sort(right)
  

• 이는 리스트를 새로 만들지 않고 in-place 정렬하는 방식으로 개선할 수 있다.(추후 예정)
• 한편, quick sort는 pivot을 어떻게 설정하느냐에 따라 시간복잡도가 달라진다. 최선의 경우 O(nlogn)이지만 pivot을 잘못 골라 두 리스트가 균등하지 않은 경우에는 O(n제곱)이 된다.

합병정렬(merge sort)

정렬할 배열을 반으로 나누어 각각 재귀적으로 정렬한 뒤 병합하는 방법이다.

• 외부정렬 방식으로 배열할 데이터를 전부 메모리에 올리지 않아도 배열이 가능하다. (외부정렬과 관련해서는 이글에서 merge sort를 이용한 예제를 아주 잘 설명되어있다.)
• 배열할 정렬을 반으로 나눈 뒤 각 배열을 재귀적으로 merge sort한다. 배열의 길이가 1 이하일 때에는 리스트 자체를 리턴하도록 하여 재귀를 끝낸다.
• 리턴받은 두 배열의 원소를 순차적으로 비교하며 새로운 배열에 크기 순서대로 담고 리턴한다.
• 최선/최악 O(nlogn)의 시간복잡도를 가진다.

  def merge_sort(A):
    N = len(A)
    if N <= 1:
        return A
      
    k = N//2
    left, right = merge_sort(A[:k]), merge_sort(A[k:])
    l, r = 0, 0
    sorted_A = []
    for i in range(k+1):
        if left[l] < right[r]:
            sorted_A.append(left[l])
            l += 1
        else:
            sorted_A.append(right[r])
            r += 1 
  
        if l >= len(left):
            sorted_A += right[r:]
            break
        elif r >= len(right):
            sorted_A += left[l:]
            break
    return sorted_A
  

  
  
  이렇게 각 정렬알고리즘 방식과 코드를 정리해보았다. 위의 6가지 정렬방법 이외에도 heap sort, shell sort 등의 정렬방식이 있다. 또, 위에서 설명된 quick sort는 in-place 정렬방식을 사용하여 개선이 필요하다. 추후 개선사항은 반영할 예정이다.