정렬 알고리즘

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 이진탐색의 전처리 과정이기도 하고, PS(Problem Solving)에서 빠지지 않는 유형의 알고리즘이다. 나는 선택 정렬은 검색 없이도 구현할 수 있었지만 삽입, 퀵, 계수 정렬은 직접 코딩하기엔 애매한 지식을 갖고 있었다. (항상 구글링해서 써먹었다) 난 알고리즘 대회 입상자가 목표가 아니라, 어느정도의 PS 실력을 갖춰 기업 코딩 테스트에 통과하는 것을 목표로 하기 때문에 각 정렬에 대한 기본적인 코드 작성, 평균 시간복잡도 정도만 인지하고 문제 풀이에 집중했다.

선택 정렬

시간복잡도 - O(N^2)

가장 원시적인 방법으로, 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 모든 요소에 대해 반복하면 전체 데이터의 정렬이 이루어진다. 가장 무식한 방법이라고 하지만 PS를 하다보면 특정 리스트에서 가장 작은 데이터를 찾는 일이 흔하므로 선택 정렬 코드에 익숙해져야 한다.

선택정렬 1

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

for i in range(len(array)):
    min_index=i
    for j in range(i+1,len(array)):
        if array[j]<array[min_index]:
            min_index=j
    array[i], array[min_index] = array[min_index], array[i]

print(array)

선택정렬 2

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

for i in range(len(array)):
    for j in range(i+1,len(array)):
        if array[i]>array[j]:
            array[i], array[j] = array[j], array[i]

print(array)

삽입 정렬

시간복잡도 - 최선(정렬된 상태): O(N), 최악: O(N^2)

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입정렬이라고 한다. 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬된 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

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

for i in range(1,len(array)):
    for j in range(i,0,-1):
        if array[j] < array[j-1]:
            array[j], array[j-1]=array[j-1], array[j]
        else: break

print(array)

일반적인 경우(위 처럼)에 인덱스 0인 요소를 기준으로 잡아 1부터의 요소부터 적절한 위치를 판단한다.

퀵 정렬

시간복잡도 - 평균: O(NlogN), 최악: O(N^2)

퀵 정렬은 가장 많이 사용되는 알고리즘이다. 병합정렬과 속도는 비슷하다. 퀵 정렬에는 피벗(pivot)이 사용된다. 큰 숫자, 작은 숫자를 교환할 때 교환하기 위한 기준이 바로 피벗이다. 사실 퀵 정렬을 글로만 이해하기는 쉽지 않고, 나는 위 영상을 참고했다.

퀵 정렬 1 - 호어 분할 방식 (정석)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
array = [7,5,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)
print(array)

recursive 함수를 사용하는데 피벗을 기준으로 왼쪽(피봇보다 작은 데이터), 오른쪽(피봇보다 큰 데이터)로 나눠 재귀를 반복해서 하나의 정렬된 리스트로 만들어낸다.

퀵 정렬 2 - 파이썬스러운 방식

파이썬스럽게 바꾼 퀵 정렬 코드도 있다.

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

def quick_sort2(array):
    if len(array)<=1: return array
    pivot=array[0]
    tail=array[1:] # list excludes the pivot
    left_=[x for x in tail if x<=pivot] # left divided part
    right_=[x for x in tail if x>pivot] # right divided part
    return quick_sort2(left_)+[pivot]+quick_sort2(right_)

print(quick_sort2(array))

이 코드는 [퀵 정렬 1]보다는 시간 면에서 조금 비효율적이지만 더 직관적이고 기억하기 쉽다는 장점이 있다.

계수정렬

시간복잡도 - O(N+K)

계수 정렬 알고리즘은 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘이다. 간단하게 무작위로 배치된 정수 0~100까지의 데이터가 주어지면 101까지의 0으로 초기화한 배열을 만들고 정렬해야할 리스트를 순회하며 카운트하여 새로 만든 카운트용 배열의 숫자를 1씩 증가시킨다.

1
2
3
4
5
6
7
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count=[0]*(max(array)+1)
for i in array:
    count[i]+=1
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

데이터의 범위가 한정되어 있다면 효과적으로 사용할 수 있으며 모든 알고리즘 중에서 가장 빠른 수준으로 동작한다. (비슷한 정렬 알고리즘으로 기수 정렬이 있다) 그러나 시간복잡도 면에서는 효율적이지만 같은 배열 크기 만큼의 카운트 배열을 하나 더 만들어야 하므로 공간복잡도 면에서는 비효율성을 초래할 수도 있으니 상황에 맞게 사용하자.

파이썬 기본 정렬 알고리즘 sort()

시간복잡도 - O(NlogN)

파이썬의 기본 정렬 라이브러리인 sort()는 병합 정렬을 기반으로 만들어졌고, 시간복잡도는 O(NlogN)을 보장한다.

기본적인 사용법은 sort(배열)이며 배열 요소가 2개 이상인 경우 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)]

b=sorted(a)
print(b)

c=sorted(a, key=lambda x:x[0])
print(c)

d=sorted(a, key=lambda x:x[1])
print(d)

e=sorted(a, key=lambda x:(x[0],x[1]))
print(e)

lambda를 이용하면 배열 요소의 특정 인덱스를 기준으로 정렬 기준을 정할 수 있다. 마지막 e는 인덱스 0을 기준으로 정렬하고, 인덱스 1인 기준으로 정렬하는 lambda 사용의 예시이다.