Skip to content

Sorting.md

Latest commit

 

History

History
227 lines (176 loc) · 14.5 KB

Sorting.md

File metadata and controls

227 lines (176 loc) · 14.5 KB

정렬

  • 순서가 없는 사물들을 순서대로 나열하는 것을 말함
  • 정렬은 무언가를 찾을 때, 즉 효율적인 탐색을 위해 사용됨
  • 정렬을 위해서는 사물들을 서로 비교할 수 있어야 함
  • 또한 비교할 수 있는 모든 속성은 정렬의 기준이 될 수 있음
  • 정렬의 기준이 달라지면 자료가 나열되는 순서도 달라짐
  • 같은 정렬 기준을 사용하더라도 오름차순(ascending order)과 내림차순(descending order)으로 나열할 수 있음

정렬 관련 용어

  • 정렬시켜야 할 대상으로 보통 레코드(record)라고 부름

  • 레코드는 여러 개의 필드(field)로 이루어짐

  • 정렬의 기준이 되는 필드를 키(key) 또는 정렬 키(sort key)라고 부름

  • 결국 정렬이란 레코드들을 키(key)의 순서로 재배열하는 것을 말함

  • 알고리즘이 단순하면 일반적으로 비효율적임

    • 삽입 정렬, 선택 정렬, 버블 정렬 등

  • 효율을 높이기 위해서는 복잡한 알고리즘을 사용해야 함

    • 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬, 팀 정렬 등

  • 효율성 외에도 정렬 알고리즘들을 분류하는 중요한 특성들이 있음

  • 안정성(stability)은 입력 데이터에 같은 키값을 갖는 레코드가 여러 개 있을 때, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것을 말함

  • 제자리 정렬(in-place sorting)은 입력 배열 이외에 추가적인 배열을 사용하지 않는 정렬을 말함

  • 효율성이 같다면 안정성을 갖고 제자리 정렬 특성이 있는 알고리즘이 더 우월함

선택 정렬

  • 선택 정렬(selection sort)은 가장 단순하고 확실한 방법을 사용함
  • 리스트에서 가장 작은 숫자를 하나씩 찾아 순서대로 저장하는 것임
  • 즉, 정렬이 작은 값부터 순서대로 나열하는 작업이므로 리스트에서 가장 작은 값을 찾아 출력하고, 남은 항목 중에서 다시 가장 작은 값을 출력하는 과정을 반복하면 당연히 정렬된 결과를 얻을 수 있음
  • 이 알고리즘은 단순하지만 한 가지 문제가 있음
    • 정렬을 위해 입력 리스트 외에 추가적인 리스트가 필요한 것임
  • 하지만 약간의 아이디어를 추가하면 이 알고리즘을 입력 리스트 이외에 추가적인 메모리를 사용하지 않는 제자리 정렬로 개선할 수 있음
  • 최솟값이 선택되면 이 값을 출력 리스트에 저장하는 것이 아니라 입력 리스트의 첫 번째 요소와 교환하는 것임
  • 이러한 과정을 $n-1$번 반복하면 전체 리스트가 정렬됨

선택 정렬 알고리즘(제자리 정렬 방식)

def selection_sort(A):
    n = len(A) # 리스트의 크기
    for i in range(n-1): # i는 정렬되지 않은 부분의 시작 인덱스 0부터 n-2까지 순서대로 대입
        least = i
        for j in range(i+1, n):
            if (A[j] < A[least]): # i+1부터 n-1까지의 요소 중에서 최솟값의 인덱스 least를 구함
                least = j
        A[i], A[least] = A[least], A[i] # A[i]와 A[least]를 교환 , 튜플을 이용한 두 변수의 교환

선택 정렬의 특징

  • 알고리즘은 간단하지만 시간 복잡도는 $O(n^2)$로 효율적이지는 않음 (제자리 정렬이면 추가 공간은 $O(1)$)
  • 안정성을 만족하지도 않음
  • 제자리 정렬로 추가적인 리스트가 필요하지 않음
  • 자료의 구성에 상관없이 비교 횟수가 고정된다는 장점이 있음
    • 각 $i$에 대해 남은 구간에서 최솟값을 찾으므로, 비교는 대략 $(n-1) + (n-2) + \cdots + 1 = \dfrac{n(n-1)}{2}$번이며 $\Theta(n^2)$임
    • 이것은 정렬할 리스트의 크기가 정해지면 리스트에 어떤 숫자가 어떻게 들어가 있는지와 무관하게 정렬에 걸릴 시간을 예측할 수 있는 것임
  • 리스크가 크지 않은 문제라면 충분히 사용할 수 있는 알고리즘임

삽입 정렬

  • 정렬이 안 된 부분의 맨 앞의 숫자를 정렬된 부분의 적절한 위치에 끼워 넣는 과정을 반복함
  • 이때 끼워 넣는다는 것은 넣을 자리 이후의 숫자들을 한 칸씩 밀고 그 자리에 복사하는 것을 말함

삽입 정렬 알고리즘

  • [3, 6, 7]이 정렬된 상태에서 4를 끼워 넣으려면 먼저 4가 들어가야 할 정확한 위치를 찾아야 함
  • 하나는, 맨 앞의 요소인 3부터 시작해 오른쪽으로 순서대로 움직이며 찾는 것임
  • 하나는, 맨 뒤에서부터 앞으로 움직이며 찾는 것임
  • 두 방법 모두 같은 위치가 나오지만 두 번째 방법을 사용하면 약간의 장점이 있음
    • 비교할 때마다 정렬된 부분의 요소가 크면 그것을 한 칸 뒤로 미리 옮겨 놓을 수 있다는 것임
  • 이를 위해 실제로 요소들을 매번 교환할 필요는 없음
  • 앞의 요소만 뒤로 복사하고, 맨 마지막에 삽입할 요소를 찾은 위치에 복사하면 되기 때문임
  • 이를 위해 삽입할 요소를 미리 다른 변수에 저장해 두어야 함
def insertion_sort(A):
    n = len(A)
    for i in range(1, n): # i의 범위: 1 ~ n-1
        key = A[i] # 삽입할 요소를 미리 key에 저장해둠
        j = i - 1
        while j>=0 and A[j] > key: # i-1 요소부터 비교하여 앞으로 진행하는데, 이 요소가 key보다 크면 뒤로 한 칸 옮김
            j-= 1
        A[j + 1] = key # j+1이 A[i]가 삽입될 위치임

삽입 정렬은 얼마나 빠를까?

  • 외부 루프는 항상 $1$에서 $n-1$까지 총 $n-1$번 반복됨
  • 다만 내부 루프가 문제임
    • 입력 리스트의 자료가 어떤가에 따라 while문이 한 번만에 끝날 수도 있고 여러 번 반복될 수도 있음
  • 즉, 삽입 정렬은 선택 정렬과 달리 입력 리스트의 크기가 같더라도 그 안에 어떤 값이 들어 있는가에 따라 처리 시간이 달라지는 알고리즘임

최선의 경우

  • 입력 리스트가 이미 오름차순으로 정렬된 경우
  • 외부 루프(for)가 $n-1$번 반복되는데, 그 안에서 내부 루프(while)는 한 번만 처리됨
  • 즉, 전체 비교 연산은 $n-1$번 수행됨
  • 이것은 시간 복잡도 $O(n)$으로 매우 효율적이지만 특별한 경우로 실제 상황에서 자주 나타나지 않음

최악의 경우

  • 역순으로 정렬된 리스트가 최악의 입력임
  • 끼워 넣을 위치가 항상 맨 앞이 되기 때문에 while문의 조건 검사를 항상 맨 앞까지 진행해야 함
  • 즉 $A[i]$를 삽입하기 위해 $A[i-1]$부터 $A[0]$까지 $i$개의 요소를 모두 비교해야 함

삽입 정렬의 특징

  • 입력의 구성에 따라 처리 시간이 달라지며, 최악·평균 시간 복잡도는 $O(n^2)$, 최선은 $O(n)$, 제자리 정렬이면 추가 공간은 $O(1)$임
  • 끼워 넣기를 위해 많은 레코드의 이동이 필요하므로 레코드의 크기가 큰 경우 선택 정렬보다도 효율적이지 않음
  • 제자리 정렬이고, 안정성도 충족함
  • 레코드 대부분이 이미 정렬된 경우라면 효율적으로 사용될 수 있음
  • 최선의 경우에 대한 효율성이 매우 뛰어나기 때문임 (실제로 이러한 장점에 착안해 다른 정렬 알고리즘에서 사용되기도 함)

퀵 정렬

  • 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
    • 분할 정복 전략을 이용함
    • 분할 정복은 하나의 문제를 둘 또는 여러 개의 작은 부분 문제로 나누고, 부분 문제들을 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략임
  • 먼저 기준이 되는 요소를 선택하고, 이 요소보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동시킴
  • 이때 기준을 피벗(pivot)이라 부름
  • 피벗은 무엇이 되든 상관없음
  • 퀵 정렬의 '분할'은 기준보다 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 이동시키는 작업임
  • 한 번의 분할이 끝나면 원래의 정렬 문제는 두 개의 문제로 나누어짐
  • 원래의 문제(8개 정렬)가 각각 5개와 2개를 정렬하는 두 개의 작은 문제로 나누어짐
  • 피벗은 이미 제자리를 찾았고, 이제 작아진 두 문제만 각각 해결하면 정렬이 끝남
  • 다음으로 작아진 문제들에 같은 분할 과정을 적용하면 됨
  • 계속 분할을 하다가 크기가 1이 되면 그 리스트는 이미 정렬된 것이므로 분할이 종료됨

퀵 정렬 알고리즘

def quick_sort(A, left, right):
    if (left < right): # 정렬 범위가 2개 이상인 경우
      q = partition(A, left, right) # 피벗을 중심으로 리스트를 두 부분으로 분할하고, 피벗의 위치 q를 구함
      quick_sort(A, left, q-1) # 이제 왼쪽(left ~ q-1)과 오른쪽 (q+1 ~ right) 부분 리스트를 각각 정렬하면 전체 정렬 완료
      quick_sort(A, q+1, right)
  • 요소가 하나 이하라면 이미 정렬된 것임
  • 피벗을 기준으로 두 개의 부분 리스트로 분할하는 partition()이 남았음

분할은 어떻게 할까?

  • 퀵 정렬에서 복잡한 부분은 정렬이 아니라 분할임

  • 입력 리스트를 피벗을 중심으로 왼쪽과 오른쪽의 부분 리스트로 나누어야 하는데, 피벗보다 작은 항목들은 모두 왼쪽 부분 리스트로 이동하고, 큰 항목들을 오른쪽으로 이동해야 함

  • 이때 부분 리스트들의 내부가 정렬될 필요는 없음

  • 단지 피벗을 중심으로 분리만 하는 것임

  • 분할은 탐색-교환 과정을 반복하는 것임

  • 정렬할 리스트 A의 시작과 마지막 인덱스 left, right가 주어지면 피벗을 선택하고 탐색-교환 과정을 위한 두 인덱스 low와 high를 준비함

  • 이들은 각각 왼쪽과 오른쪽 부분 리스트를 만드는 데 사용되는데, low=left+1, high=right로 초기화됨

  • 탐색은 low를 오른쪽으로, high를 왼쪽으로 진행하면서 조건에 맞지 않는 요소를 찾는 과정임

  • 왼쪽 부분 리스트: A[low]가 피벗 이하이면 왼쪽 부분 리스트에 적합하므로 low를 오른쪽으로 전진시키다가 A[low]가 피벗보다 클 때 멈춤

  • 오른쪽 부분 리스트: A[high]가 피벗보다 크면 high를 왼쪽으로 전진시키다가 A[high]가 피벗보다 작으면 멈춤

  • 피벗을 두 부분 리스트의 중앙으로 옮겨야 함

  • 피벗과 high의 항목을 교환하면 됨

  • 마지막으로 피벗의 위치인 high를 반환함

def partition(A, left, right):
    pivot = A[left]
    low = left + 1 # 왼쪽(left) 요소를 피벗으로 사용하면 low는 left+1이 되고
    high = right # high는 right가 됨

    while (low < high): # low와 high가 역전되지 않는 한 반복
        # 양쪽에서 조건이 맞지 않은 요소를 찾는 과정
        while low <= right and A[low] <= pivot:
            low += 1 # A[low] <= 피벗이면 low를 오른쪽으로 진행

        while high >= left and A[high] > pivot:
            high-= 1 # A[high] > 피벗이면 high를 왼쪽으로 진행

        if low < high: # 역전이 아니면 두 레코드 교환
            A[low], A[high] = A[high], A[low]
    # 마지막으로 피벗과 high를 교환하고, 피벗의 인덱스 high를 교환
    A[left], A[high] = A[high], A[left]
    return high
  • partition() 함수는 반드시 피벗의 인덱스를 반환해야 함
  • 길이가 $n$인 리스트 A를 정렬하기 위해서는 quick_sort(A, 0, n-1)과 같이 퀵 정렬 함수를 호출해야 함
data = [5, 3, 8 ,4 ,9, 1, 6, 2, 7] # 입력 리스트
quick_sort(data, 0, len(data)-1) # 퀵 정렬

퀵 정렬은 정말 그렇게 빠를까?

  • 피벗을 제외한 모든 요소는 피벗과 반드시 한 번씩 비교되어야 함
  • 따라서 전체 요소의 수가 $n$이라면 $n-1$번의 비교가 필요함

최선의 경우

  • 최선의 경우는 분할이 항상 리스트의 중앙에서 이루어질 때임
  • $n$이 2의 거듭제곱이라고 가정하면, 부분 리스트의 크기는 레벨에 따라 $\dfrac{n}{2},\ \dfrac{n}{4},\ \dfrac{n}{8},\ \ldots,\ \dfrac{n}{2^k}$처럼 절반으로 줄어듦
  • 이러한 분할은 리스트의 크기가 1이 될 때, 즉 $\dfrac{n}{2^k} = 1$일 때까지 진행됨
  • 따라서 $2^k = n$, 즉 순환 호출 트리의 높이는 $k = \log_2 n$이 됨
  • 트리의 각 레벨에서 여러 번의 partition()이 실행되는데, 한 레벨에서 피벗을 제외한 모든 요소를 비교해야 하므로 합쳐 최대 약 $n$번의 비교가 필요함
  • 따라서 전체 비교 연산은 대략 $n \cdot k = n \log_2 n$에 비례함
  • 빅오 표기에서는 로그의 밑은 상수 배 차이만 만들므로 보통 $O(n \log n)$으로 쓰기도 함. 퀵 정렬은 최선(균형 분할)에서 시간 복잡도 $O(n \log n)$인 효율적인 알고리즘임

최악의 경우

  • 최악의 입력은 리스트가 계속 불균형하게 나누어지는 경우임
  • 이미 정렬된 리스트는 퀵 정렬에서 최악의 입력인데 분할을 할 때마다 남은 요소들이 한쪽에 몰리기 때문임
  • 정렬을 위한 순환 호출의 깊이가 $O(n)$이 되므로, 레벨마다 $O(n)$ 비교가 붙어 전체는 $O(n^2)$에 비례함
  • 즉, 퀵 정렬의 최악 시간 복잡도는 $O(n^2)$로 선택 정렬·삽입 정렬과 같은 차수임 (제자리 정렬이면 추가 공간은 평균 $O(\log n)$ 스택, 최악 $O(n)$)

퀵 정렬의 특징

  • 퀵 정렬은 제자리 정렬이지만 안정성은 만족하지 않고, 최악 시간 복잡도는 $O(n^2)$인 알고리즘임
  • 최악의 경우는 좋지 않지만, 평균적인 경우는 최선의 경우에 비해 추가적인 연산이 39% 정도만 늘어나는 것으로 알려져 있음
  • 결국 평균적으로는 최선의 입력과 비슷한 속도가 나옴
  • 특히 병합 정렬이나 힙 정렬과 같은 다른 알고리즘과 비교해도 매우 빠른 것으로 알려져 있는데, 그 이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환하며, 한번 결정된 피벗들이 추후 연산에서 제외되는 등의 특징 때문이라고 함
  • 퀵 정렬의 성능을 더 개선하려는 방법들이 연구되고 있는데, 불균형 분할을 완화하기 위해 피벗을 리스트의 중앙값에 더 가깝도록 선택하는 방법이 있음
    • 예를 들어 리스트 내의 몇 개의 값 중에서 중간값을 피벗으로 사용할 수 있음
    • 리스트의 왼쪽, 오른쪽, 중간 3개의 요소 중에서 중간값을 선택하는 방법이 많이 사용됨

기수 정렬

  • 추후 작성할 예정