Sort(정렬) 알고리즘

정렬(sorting)이란?
정렬(sorting)은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나로써 이진탐색(binary search)를 수행하기 위해 필요한 알고리즘이다.
어떠한 자료들을 정렬할 때 인간과 달리 컴퓨터는 데이터의 규칙성을 직관적으로 알 수 없어 정렬을 수행하는 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

1. 선택 정렬

가장 원시적인 방법의 정렬로써 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 한다.(오름차순으로 정렬을 진행한다고 가정하였다.)

N개의 데이터를 정렬한다고 할때 선택 정렬은 데이터들 중 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하여 정렬을 한다.

다음은 파이썬을 작성한 선택 정렬의 예시코드이다.

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[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프
    
print(array)
 

선택 정렬 알고리즘의 시간 복잡도

이와 같은 선택 정렬은 N개의 데이터를 정렬할 때 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내는 과정을 수행한다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산을 수행한다. 사소한 오차를 무시한다면 연산 횟수는 N + (N-1) + (N-2) .... + 2이다. 이는 N*(N+1) / 2로 나타낼 수 있고 빅오 표기법으로 나타내면 선택정렬 알고리즘은 O(N^2)의 시간복잡도를 가진다.

선택 정렬 알고리즘의 효율성

선택 정렬 알고리즘은 다른 정렬 알고리즘에 비해 비효율적인 부분이 존재한다. 하지만 코딩테스트에서는 특정한 리스트에서 가장 작은 데이터를 찾는 경우가 잦기 때문에 선택 정렬 알고리즘은 숙지해야한다.

2. 삽입 정렬

삽입 정렬(Selection Srot)는 특정한 데이터를 적절한 위치에 삽입한다는 의미이다. 이 알고리즘은 선택 정렬보다는 구현 난이도가 높지만 그보다 더 효율적인 방법이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬되어 있는 경우'에 더 효과적이다.

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

다음은 삽입정렬을 파이썬 코드로 구현한 예제이다.

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)

삽입 정렬의 경우 데이터가 거의 정렬되어 있는 경우에는 굉장히 빠르게 작동하며 시간복잡도가 거의 O(N)에 수렴한다. 코딩테스트때 참고하면 시간적인 부분에서 유리하게 적용할 수 있다.

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 마찬가지고 반복문이 2번 중첩되어 사용되었기 때문이다.

3. 퀵 정렬

퀵 정렬은 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 이름 그대로 굉장히 빠른 속도를 자랑하는 정렬 알고리즘이며 병합 정렬 알고리즘이 이와 비교될 정도로 빠르다.

퀵 정렬은 특정한 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
이때 교환하기 위한 기준을 바로 '피벗'이라 말한다. 퀵 정렬을 수행하기 전에는 이 '피벗'을 어떻게 설정할 것인지 미리 명시해야 한다. 이 '피벗'을 설정하는 방식에는 여러가지가 있는데 대표적으로 '호어 분할' 방식이 있다. 이 방식에서는 리스트에서 가장 첫 번째 데이터를 기준으로 삼는다.

퀵 정렬의 동작 방식은 다음과 같다.
1. 피벗을 설정한다.
2. 피벗을 기준으로 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
3. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
4. 이 때 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값이 교차 되는 경우 그 중 작은 데이터와 피벗의 위치를 교환해 준다.
5. 피벗을 기준으로 나뉜 양쪽에도 위의 과정을 똑같이 수행한다.

위의 과정을 반복하면 피벗에 대하여 정렬이 수행된다. 이때 피벗만 남게 되는 경우 즉, 데이터가 하나만 남는 경우 반복을 종료하면 된다.

다음은 퀵 정렬을 파이썬으로 구현한 것이다.

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

def quick_sort(array, start, end):
	if start >= end: # 원소가 1개인 경우 종료
   	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(arrya, left + 1, end)
       
       
quick_sort(array, 0, len(array) -1)
print(array)

다음의 코드는 퀵 정렬을 파이썬의 장점을 좀 더 살려 작성한 코드이다. 전통적인 분할 방식과는 다르고, 비교 연산 횟수가 증가 시간적인 면에서는 비효율 적이지만 좀 더 코드가 간결해 직관적이고 기억하기 쉽다.

# 파이썬의 장점을 살린 퀵 정렬 코드

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 in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for in tail if x > pivot] # 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
   
print(quick_sort(array))

퀵 정렬의 시간 복잡도

퀵 정렬읠 평균 시간 복잡도는 O(NlogN)이다. 하지만 최악의 경우에는 O(N^2) 이 경우는 데이터가 이미 정렬되어 있는 경우에 해당하는데 삽입정렬은 이 경우에 매우 빠르게 동작하는 것과 대비된다.

4. 계수 정렬

계수 정렬 알고리즘은 직접 데이터를 비교하며 위치를 변경하는 다른 정렬 알고리즘들과는 다른 특징을 가지고 있다. 계수정렬 방식은 특정한 조건이 부합할 때만 사용 가능하다는 제약이 있지만 조건이 부합한다면 매우 빠른 수행 속도를 보여준다. 데이터의 개수가 N, 그 중 최대값의 크기를 K라 하였을 때, 계수 정렬은 최악의 경우에도 O(N+K)의 시간 복잡도를 보장한다. 이런 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로만 표현할 수 있을 때만 사용가능하다. 즉, 실수와 같이 값의 범위가 무한하다면 계수정렬은 사용할 수 없다.
계수정렬이 위와 같은 특징을 가지는 이유는 계수정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 데이터 리스트 선언을 해야하기 때문이다.

예를 들면 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000 이라면 총 1,000,001 개의 데이터르 넣을 수 있는 리스트를 선언해야한다. 이유는 0~1,000,000의 수의 개수는 1,000,001이기 때문.

계수정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 예시를 들자면 다음과 같다.

입력값이 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
로 주어졌을 때 계수정렬을 진행하면 별도로 선언한 리스트는

위와 같이 채워진다.
간단하게 원리를 설명하면 가장 작은 데이터부터 가장 큰 데이터까지를 인덱스로 갖는 리스트를 선언 한 뒤 주어진 입력값을 순차적으로 탐색해가며 입력값에 해당하는 인덱스의 값을 1씩 증가시키면 된다.
이를 정렬된 데이터로 출력하면 각 인덱스의 값만큼 인덱스를 출력하면 되는데 출력값은
'0 0 1 1 2 2 3 4 5 5 6 7 8 9 9' 가 된다.

계수정렬 소스코드는 다음과 같다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 시간 복잡도

위에서 언급했듯이 계수정렬의 시간복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트의 인덱스 값을 1씩 증가 시킬 뿐 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다. 데이터의 범위만 한정되어 있다면 현존하는 알고리즘들 중에서는 기수 정렬과 더불어 가장 빠른 속도를 자랑한다.

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있는데 예를 들어 데이터가 0과 1,000,000만 존재한다고 하면 데이터는 2개밖에 없는것에 비해 리스트는 1,000,001 만큼의 크기를 가지게 선언해야 한다. 이 경우 쓸데없이 리스트를 크게 만들어야 하므로 비효율적이다.
계수 정렬이 가장 효과적인 경우는 입력값에 동일한 값이 여러개 존재하는 경우이다. 반대로 데이터의 개수가 적은 위의 사례에는 퀵 정렬이나 병합 정렬을 사용하는 것이 더 적합하다.

출처
이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 나동빈

이 글은 위 서적을 바탕으로 학습하기 위해 작성되었습니다.