Python 알고리즘 공부 (5: 정렬)

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다고 한다. 정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 아주 많은 종류가 있다. 

 

 

 

1. 선택정렬

 

선택정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 방법이다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어지게 되는 것이다. 아래와 같은 이중 반복문, 스와프 코드로 간단하게 구현해볼 수 있다.

 

 

 

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

 

 

 

선택정렬의 시간 복잡도는 N^2 로 표현할 수 있다.

 

 

 

2. 삽입정렬

 

선택정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이라고 한다. 이 대신 삽입정렬을 고려해볼 수 있는데, 삽입정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 것이다. 조금 더 풀어 설명하자면, 숫자로 이루어진 리스트에서 왼쪽부터 순서대로 삽입정렬을 시작한다고 하였을 때, 왼쪽에 있는 수가 자기자신보다 작거나 같아질 때까지 위치를 찾아가는 것이다. 선택정렬에 비해 구현 난이도가 있긴 하지만, 시간 측면에서 더욱 효율적인 알고리즘으로 알려져있다. 아래와 같은 코드로 구현해볼 수 있다.

 

 

 

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
            else:
            	break

 

 

 

삽입정렬 또한 반복문이 두 개 중첩되어 있어 시간 복잡도가 N^2 이긴 하지만, 삽입정렬을 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 장점이 있다. 최선의 경우 N 의 시간복잡도를 가지게 된다.

 

 

 

3. 퀵 정렬

 

퀵 정렬을 지금까지 알아본 정렬 알고리즘 중 가장 많이 사용되는 알고리즘으로, 이는 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식을 사용한다. (병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이라고 한다) 가장 기본적인 퀵 정렬을 첫 번째 데이터를 기준데이터, Pivot 으로 설정한다. 피벗을 설정한 뒤, 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다. 이 작업을 계속 반복하게 되는데, 이 때 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈리게 되면 그 두 수의 위치를 바꾸는 것이 아니라 작은 데이터와 피벗의 위치를 서로 변경한다.

 

 

이 작업을 수행하면 본래 피벗 값의 위치를 기준으로 왼쪽에는 피벗보다 작은 값만, 오른쪽에는 피벗보다 큰 값만 남게 된다. 이를 분할이라고 한다. 분할을 한 뒤, 본래 피벗을 기준으로 왼쪽, 오른쪽을 2 개의 다른 리스트로 나누어 다시 정렬을 수행하게 되는 것이다. 이러한 방식으로 재귀적으로 정렬이 이루어지게 되는 것이고, 이 과정을 반복하면 전체 데이터에 대해서 정렬이 수행되게 된다. (시간복잡도는 N * log N 이다. 하지만 최악의 경우 N^2 의 시간복잡도를 갖는다(이미 정렬된 배열에 대해서 퀵 정렬을 수행하게될 때))

 

 

 

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

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)
quick_sort(array, 0, len(array) - 1)

 

 

 

아래와 같이 파이썬의 장점을 살려 작성할 수도 있다고 한다.

 

 

 

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0] 
    tail = array[1:] 

    left_side = [x for x in tail if x <= pivot] 
    right_side = [x for x in tail if x > pivot] 

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

 

 

 

4. 계수정렬

 

계수정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 알고리즘이다. (데이터의 개수가 N, 데이터 중 최대값이 K 일 때 최악의 경우에도 수행시간 N+K 를 보장한다) 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하다. 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수정렬을 사용하기 어렵다고 한다. 

 

 

계수정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트(모든 값이 0인)를 생성한다. 그 후, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1 씩 증가시킨다. 결과를 확인할 때는, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력하는 것이다. 코드를 보면 이해가 쉽다.

 

 

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)): 
    for j in range(count[i]):
        print(i, end=' ')

 

 

 

 

대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 N log N 을 보장하도록 설계되어있다. 파이썬의 경우에는 list, dictionary 에 sort() 메서드를 지원한다. Dictionary 자료형에 sort 를 구현하는 방식은 아래와 같다.

 

 

def setting(data):
	return data[1]

result = sorted(dic, key=setting)