[자료구조와 알고리즘 스터디] 5주차 - 정렬

팔랑이·2023년 12월 3일

python 알고리즘 자료구조

자료구조/알고리즘

목록 보기

7/19

5주차: 정렬 알고리즘

출처
📚 쉽게 배우는 자료구조 with 파이썬
💻 https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

정렬

정렬은 원소들을 순서대로 배열하는 것이다.
정렬 알고리즘에는 여러가지가 있는데, 수행 시간에 따라 다음과 같이 세 그룹으로 나눌 수 있다.

기본적으로, 정렬하고자 하는 원소들은 리스트 A에 담겨 있다고 가정한다.

기본 정렬 알고리즘

기본 정렬 알고리즘들은 정보처리기사 공부할 때 학습했던 내용이라 짧게 정리하고 넘어간다.

1. 선택 정렬

: 리스트 안에서 가장 큰 수를 찾고 맨 뒤 원소와 자리를 바꾼다. 그 다음 큰 수를 찾고 맨 뒤에서 한 칸 앞의 원소와 자리를 바꾸는 과정 반복.

2. 버블 정렬

: 첫 번째와 두 번째 원소를 비교해 큰 원소를 뒷자리에 놓는다. 두 번째와 세 번째 원소를 비교해 큰 원소를 뒷자리에 놓는다. 이를 마지막 원소까지 반복하면 1회전.

3. 삽입 정렬

: 두 번째 원소부터 시작, 그 앞의 원소들과 비교해 자기의 자리를 찾는다. 한 원소가 그 앞의 원소들과 자신을 하나씩 비교해 자리를 찾는 것 까지 1회전. 리스트가 어느정도 정렬되어 있을 경우에 수행시간이 매우 빠르기 때문에 이를 다른 고급 정렬 알고리즘과 섞어 쓰기도 한다.

고급 정렬 알고리즘

앞의 기본 정렬 알고리즘들보다 소요 시간이 많이 짧은 알고리즘들이다.

1. 병합 정렬 (merge sort)

분할-정복 알고리즘을 이용하는 정렬 방법 중 하나이다.

분할: 입력 리스트를 같은 크기의 리스트로 나눈다.
정복: 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할한다.

리스트 A[0...n-1]을 정렬하고자 할 때 최초의 호출은 mergeSort(A, 0, n-1) 이다.

mergeSort(A[], p, r):
	if (p<r)
    	q = (p+r)/2
        mergeSort(A, p, q)
        mergeSort(A, q+1, r)
        merge(A, p, q, r)

같은 크기로 나눈 배열을 병합 정렬로써 재귀적으로 정렬한다.

병합 정렬의 수행 시간은 최악, 평균, 최선의 모든 경우에 O(nlogn)이다.
이론적으로 보면 완벽한 O(nlogn)을 보장하는 알고리즘이지만, 분할-정복 과정에서 주어진 리스트 A[]에 더하여 보조 리스트 tmp[]가 필수적이기 때문에 추가 공간이 필요해진다는 단점이 있다.

python 구현 코드는 다음과 같다.

def mergeSort(A, p, r):
    if p<r:
        q = (p+r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q+1, r)
        merge(A,p,q,r)
        
def merge(A, p, q, r):
    i = p ; j = q+1 ; t = 0
    tmp = [0 for i in range(len(A))]
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp[t] = A[i]; t += 1; i += 1
        else:
            tmp[t] = A[j]; t += 1; j += 1
    
    while i<=q:
        tmp[t] = A[i]; t += 1; i += 1
    while j<=r:
        tmp[t] = A[j]; t += 1; j += 1
    
    i = p ; t = 0
    while i <= r:
        A[i] = tmp[t]
        t += 1
        i += 1

2. 퀵 정렬 (quick sort)

기준 원소를 하나 잡고, 기준 원소보다 작은 원소 그룹과 큰 원소 그룹으로 나누어 분할한 다음 각각을 정렬한다.
합병 정렬은 두 작은 정렬을 합병하는 과정에서 정렬이 한번 더 필요하지만, 퀵 정렬은 양쪽의 정렬이 마무리되면 그대로 절차가 끝난다.

다음은 퀵 정렬 알고리즘이다.

quickSort(A[], p, r):
	if (p<r)
    	q <- partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)

기준 원소 q를 중심으로 양쪽으로 나누고, 2개의 퀵 정렬을 재귀적으로 호출한다.

다음은 기준 원소를 중심으로 분할하는 알고리즘이다.

partition(A[], p, r):
	x <- A[r]
    i <- p-1
    for j <- p to r-1
        if (A[j]<x)
            A[++1] <-> A[j]
    A[i+1] <-> A[r]
    return i+1

퀵정렬의 수행시간은 평균 O(nlogn)이다. 매우 빨라 필드에서 가장 선호하는 정렬 알고리즘 중 하나이지만, 최악의 경우가 발생하는 두 가지 조건이 있다.

하나는 한쪽이 아예 없는 경우로, 이 경우 수행시간은 O(n^2)가 된다. 한쪽이 완전히 비거나 이에 근접한 상태가 반복되면 이런 비효율적 시간이 나온다.

다른 하나는 동일한 원소가 많이 존재하는 경우다. 퀵 정렬을 진행하다 보면 같은 원소가 덩어리로 모이는데, 이 덩어리를 부분 정렬하는 데 상당한 시간이 소요된다. 이 문제는 분할 알고리즘에서, 기준 원소와 동일한 원소를 만나면 양쪽에 골고루 나누어 주도록 설정하면 된다.

python 으로 구현한 코드는 다음과 같다.

def quickSort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
    return A
        
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] < x :
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

3. 힙 정렬 (heap sort)

이전까지는 원소를 저장하고 있는 리스트를 대상으로 정렬했다면, 힙 정렬은 말 그대로 힙 자료구조를 사용하여 정렬한다.

힙(heap): 최댓값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리의 일종

최악의 경우 수행시간은 O(nlogn)이고, 가장 운이 좋은 경우 O(n) 시간 안에 끝난다. 예를 들어, 모든 원소가 동일한 경우이다.

4. 셸 정렬 (shell sort)

앞서 설명한 경우들과 달리, 셸 정렬은 평균 O(n^2)의 시간이 들고, 운이 좋으면 O(n)의 시간이 든다는 점에서 매력이 있다.

이미 정렬되어 있거나 거의 정렬되어 있는 경우, 삽입 정렬은 O(n)의 시간이 든다. 삽입 정렬을 할 때, 끼워 넣고자 하는 자리와 원래 있던 자리의 거리가 멀 때 삽입 정렬의 시간이 짧아진다.

셸 정렬은 이를 잘 활용한 정렬이다. 셸 정렬의 마지막은 삽입 정렬로 끝나는데, 이 전에 각 원소가 들어가고자 하는 자리와 멀리 떨어져 있을 가능성을 현저히 줄이는 작업을 하고, 이를 통해 효율성을 찾는다.

그 작업의 방법은 다음과 같다.

shellSort(A[]):
	for h
    	for k
        	stepInsertionSort(A, k, h)
stepInsertionSort(A[], k, h):
	for i in range(k+h, len(A), h)
    	newItem <- A[i]
        j = i - h
        while 0<=j and newItem < A[j]
        	A[j+h] <- A[j]
        A[j+h] <- newItem

10만 개짜리 리스트로 셸정렬과 삽입 정렬을 돌렸을 때, 100배정도의 수행시간 차이가 있다.

특수 정렬 알고리즘

평균 또는 최악의 경우 O(n)의 시간이 드는 알고리즘들이 있다.
두 원소간 비교를 기본으로 하는 작업에서는, 원소 비교 횟수가 최악의 경우 O(nlogn)의 시간이 드는 사실은 증명되었다. 따라서 O(n)의 수행시간이 가능하게 하려면 '두 원소간 비교'를 기본으로 하지 않아야 한다. 예를 들어, 자신의 값으로 '분류'하면 된다.

특수 정렬 알고리즘도 일단 간단하게만 하고 넘어가기로 한다.

1. 계수 정렬

계수 정렬은 정렬하고자 하는 원소들의 값이 -n ~ n 의 범위에 있는 정수인 경우에 사용할 수 있다. 예를 들어, 리스트 A[0...n-1]에 있는 원소들의 값이 0~2n, -n~3n 등의 범위에 있는 정수인 경우다.

계수 정렬을 간단히 설명하면, 정수 0부터 k까지 각 원소가 리스트 안에 몇 개 들어있는지 세 준다. 그리고 그 개수만큼 정수 0부터 k까지의 원소를 나열한다.

2. 기수 정렬

원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수와 같은 특수한 경우에 사용할 수 있다. 자연수가 아닌 제한된 길이를 가진 알파벳 배열 등도 해당한다.

첫 번째 자리수로 재배열 하고, 두 번째 자리수로 재배열, 세 번째, 네 번째 자릿수로 재배열 하면 된다. 여기서 '재배열'하는 데에 기존의 비교하는 정렬을 사용하면 안되고, 간단한 방법을 써서 이 부분을 O(n)시간 안에 끝내는 것이 핵심이다. 이런 일을 k번 반복하므로 시간은 O(kn)이 된다.