정렬 — Mathlife의 학습 노트

1. 선택 정렬 ( Selection Sort )

인덱스 순서대로 (0 $\leq$ i < n-2) 정렬을 진행한다.

step i 에서는 a[i : ]에서 최솟값을 선택해서 정렬한다.

예시 : [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 를 정렬한다고 하자.

step 0 : [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 의 최솟값인 0과 a[0]의 자리를 바꾼다 ▶ [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
step 1 : [5, 9, 7, 3, 1, 6, 2, 4, 8] 의 최솟값인 1과 a[1]의 자리를 바꾼다 ▶ [0, 1, 9, 7, 3, 5, 6, 2, 4, 8]
...

소스 코드

def selection_sort(a):
    n = len(a)
    for i in range(n-1):
        min_idx = i
        for j in range(i, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

수행 시간 : $O(n^2)$

2. 삽입 정렬 ( Insertion Sort )

인덱스 순서대로 (1 $\leq$ i < n) 정렬을 진행한다.

step i 는 이미 정렬되어 있는 a[ : i]에서 적절한 위치를 찾아 a[i]를 삽입하는 방식으로 이루어진다.

좀 더 자세히 말하자면, 삽입은 a[i]를 왼쪽 원소와 비교하고 스왑하는 과정을 반복하는 방식으로 이루어진다.

번호표를 뽑아 번호순으로 입장하는 상황을 생각하면 쉽다.

a[i] : 몇 번 이세요? 저는 5번이에요

a[i-1] : 저 7번이요
a[i] : 아! 제가 더 번호가 작으니까 앞쪽으로 갈게요

( a[i], a[i-1] = a[i-1], a[i] )

예시 : [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 를 정렬한다고 하자.

step 1 : [7]은 이미 정렬되어 있다. 5를 적절한 위치에 삽입하면 [5, 7, ...] -> [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
step 2 : [5, 7]은 이미 정렬되어 있다. 9를 적절한 위치에 삽입하면 [5, 7, 9, ...] -> [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
step 3 : [5, 7, 9]는 이미 정렬되어 있다. 0을 적절한 위치에 삽입하면 [0, 5, 7, 9, ...] -> [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
...

소스 코드

def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if a[j] < a[j - 1]:  
                a[j], a[j - 1] = a[j - 1], a[j] # 앞 사람보다 번호가 작으면 앞 사람과 자리를 바꾼다
            else: 
                break # 앞 사람보다 번호가 크거나 같으면 그 자리에서 멈춘다

수행 시간: 평균 $O(n^2)$, 이미 정렬되어 있는 경우 $O(n)$

3. 퀵 정렬 ( Quick Sort )

divide and conquer 알고리즘을 사용해 재귀적으로 구현한다.

기본적인 아이디어는 매우 간단하다.

[a[pivot] 보다 작거나 같은 수들] + [pivot] + [a[pivot] 보다 큰 수들] 을 만들어준다.

이제 각 부분수열에 대해 다시 퀵 정렬을 수행한다.

소스코드 (인덱스 X : a 자체를 새로 할당; 메모리를 조금 더 사용)

def quick_sort(a):
    n = len(a)
    if n <= 1:
        return

    pivot_dat = a[0]
    temp = a[1:]
    left = [x for x in temp if x <= pivot_dat]
    right = [x for x in temp if x > pivot_dat]

    quick_sort(left)
    quick_sort(right)
    a[:] = left + [pivot_dat] + right

소스코드 (인덱스 O : a의 데이터만 수정)

def quick_sort(a, start, end):
    if start >= end:
        return

    pivot_data = a[start]
    temp = a[start+1:end+1]
    left = [x for x in temp if x <= pivot_data]
    right = [x for x in temp if x > pivot_data]

    a[start:end+1] = left + [pivot_data] + right

    quick_sort(a, start, start+len(left)-1)
    quick_sort(a, end-len(right)+1, end)

수행 시간: 평균 $O(n \log{n})$, 최악 $O(n^2)$

(참고 : 투 포인터를 이용한 퀵 정렬)

투 포인터를 이용하면 메모리를 더 적게 사용하는 퀵 정렬도 구현할 수 있다.

quick_sort(a, start, end)는 [a[start], ..., a[end]] 를 다음과 같이 정렬한다.

pivot = start, i = start + 1, j = end 로 둔다.

반복:

i는 a[pivot] 보다 큰 값을 지목하거나 범위를 벗어날 때까지 1씩 증가한다.
j는 a[pivot] 보다 작은 값을 지목하거나 범위를 벗어날 때까지 1씩 감소한다.
여기서 범위란 [a[start+1], ..., a[end]] 를 말한다.
i $\leq$ j 일 경우 a[i]와 a[j]를 교환한다.
반복은 i > j 가 될 때 종료한다.

이 때, i = end 또는 j = pivot = start 가 되는 경우도 있다.

여기서 j는 항상 배열 안의 값을 지목하게 되므로 pivot이 지목하는 값과 교환이 가능하다.

a[j], a[pivot] 을 교환하고, pivot = j 로 바꿔준다.

결과 : (a[pivot] 보다 작거나 같은 값들) a[pivot] (a[pivot] 보다 크거나 같은 값들)

위 결과는 교환 직전 i 왼쪽에는 a[pivot] 보다 작거나 같은 값만 위치하고 j 오른쪽에는 a[pivot] 보다 크거나 같은 값만 위치한다는 사실을 이용해 입증할 수 있다.

이제, quick_sort(a, start, pivot-1), quick_sort(a, pivot+1, end) 를 각각 수행한다.

여기서 주의해야 할 점은 start $\leq$ pivot $\leq$ end 이기 때문에 2번째 인자가 3번째 인자보다 클 수 있다는 점이다.

따라서, quick_sort(a, start, end) 함수의 윗 부분에 start $\geq$ end 일 경우 아무런 처리도 하지 않는 코드를 추가해야 한다.

소스코드

def quick_sort(a, start, end):
    if start >= end:
        return

    pivot = start
    i, j = start+1, end
    while True:
        while i <= end and a[i] <= a[pivot]:
            i += 1

        while j >= start+1 and a[j] >= a[pivot]:
            j -= 1

        if i <= j:
            a[i], a[j] = a[j], a[i]
        else:
            a[pivot], a[j] = a[j], a[pivot]
            pivot = j
            break

    quick_sort(a, start, pivot-1)
    quick_sort(a, pivot+1, end)

4. 카운팅 정렬 ( Counting Sort )

0 이상 K 이하의 정수 값을 가지는 (혹은 비슷한 구조를 가진) 배열에 대해 수행할 수 있는 정렬 방법이다.

K = max(a) 로 두고

count = [0] * (K+1) 을 만든다.

다음으로 count[i]에 i의 count를 저장한다.

이제 인덱스 순서대로 (0 $\leq$ i $\leq$ K) i를 count[i]번 추출하면 정렬이 끝난다.

소스코드

def counting_sort(a, n, k):
    count = [0]*(k+1)

    for i in range(n):
        count[a[i]] += 1

    temp = []
    for i in range(k+1):
        temp.extend([i]*count[i])

    a[:] = temp

수행 시간: $O(n + K)$

5. 합병정렬 ( Merge Sort )

마찬가지로 divide and conquer 알고리즘을 사용해 재귀적으로 구현한다.

기본적인 아이디어는 매우 간단하다.

a를 반으로 나눠 각각 정렬하고 left, right 를 얻는다.

result = [] 를 만든다.

이제 left와 right를 왼쪽부터 포인터 2개를 사용해 비교하면서 더 작은 값을 result에 넣어주는 과정을 반복한다.

left의 포인터 혹은 right의 포인터가 범위 밖으로 나가면 반복을 종료한다.

비교하지 못한 나머지 부분은 result의 뒷쪽에 붙혀준다.