정렬이란?
정렬은 다량의 데이터를 특정한 기준에 다라서 순서대로 나열하는 것을 말한다.
프로그램에서 데이터를 가공할 때 특정한 기준(주로 오름차순, 내림차순)에 따라 정렬한 후 가공하는 경우가 많기에 다량의 데이터를 다루기 위해서는 필수적으로 다룰 줄 알아야 하는 알고리즘이다.
또한 데이터를 정렬하게 되면 '이진 탐색'(Binary Search)이 가능해진다는 이점이 있다.
정렬 알고리즘의 종류는 셀 수 없이 많다. 데이터를 원하는 순서대로 정렬한다는 목적은 같지만, 그 방식이 완전히 다르기에 각각의 장단점을 가진다. 예를 들면, 버블 정렬(Bubble Sort)은 구현이 매우 간단하지만 비효율적이며, 계수 정렬(Count Sort)은 정렬하고자 하는 데이터가 특정 조건에 부합할 때만 사용할 수 있지만 속도가 매우 빠르다. 수많은 정렬 알고리즘 중 사용 빈도가 높은 몇 개만 알아보도록 하자.
선택 정렬(Selection Sort)
선택 정렬은 아직 정렬되지 않은 데이터 무더기 속에서 가장 작은 것(오름차순 정렬일 때)을 찾아 맨 앞의 데이터와 맞바꾸는 것을 반복하는 것으로 데이터를 정렬하는 알고리즘이다. 이 방법은 가장 원시적인 방법으로서 직관적으로 이해하기 쉽다는 장점이 있다. 하지만 모든 숫자와 비교를 해야 하므로 비효율적이라는 단점이 있고, 실제로 이 알고리즘은 O(N²)의 시간복잡도를 가진다.
선택 정렬을 파이썬으로 구현하면 다음과 같다.
array = [9, 2, 4, 0, 1, 5, 6, 3, 7, 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)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입 정렬(Insertion Sort)
삽입 정렬은 선택 정렬과 달리 필요할 때에만 위치를 바꾸는데, 따라서 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
아직 정렬되지 않은 무더기 속에서 데이터를 하나씩 골라 내어 정렬한다는 점에서 선택 정렬과 비슷하지만, 이번에는 이미 정렬된 데이터들과의 대소 비교를 통해 적절한 위치를 찾아 새로운 데이터를 삽입하게 된다. 삽입 정렬의 시간 복잡도는 O(N²)인데, 최선의 경우 O(N)의 시간 복잡도를 가진다.
삽입 정렬을 파이썬으로 구현하면 다음과 같다.
array = [9, 2, 4, 0, 1, 5, 6, 3, 7, 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, 2, 3, 4, 5, 6, 7, 8, 9]
퀵 정렬(Quick Sort)
퀵 정렬은 그 이름에 걸맞게 빠르고 효율적인 알고리즘으로, 여지껏 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 수 리스트를 반으로 나누는 식으로 동작한다. 퀵 정렬에는 피벗(Pivot)이 사용되는데, 이는 큰 수와 작은 수를 교환할 때의 기준이 된다. 퀵 정렬을 할 때에는 피벗을 어떻게 설정할 것인지 미리 명시해야만 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방법으로 퀵 정렬을 구분짓는다. 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 설정한다. 이 방식을 토대로 퀵 정렬의 절차에 대해 설명하겠다.
1. 리스트에서 첫 번째 데이터를 피벗으로 설정한다.
2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
3. 큰 데이터와 작은 데이터의 위치를 바꾼다.
4. 왼쪽에서부터 찾은 큰 값이 오른쪽에서부터 찾은 작은 값보다 오른쪽에 위치하게 될 때까지 2 - 3번을 반복한다.
5. 작은 값과 피벗의 위치를 바꾼다.
6. 피벗을 기준으로 왼쪽에는 피벗보다 작은 수, 오른쪽에는 피벗보다 큰 수만이 위치하게 된다. (이 때, 피벗을 파티션이라고 부르기도 한다.) 이 상태에서 왼쪽 리스트와 오른쪽 리스트에 대해 개별적으로 퀵 정렬을 다시 실행한다.
퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. O(N²)의 시간 복잡도를 가지는 선택 정렬과 삽입 정렬에 비해 아주 효율적이라고 할 수 있다.
퀵 정렬을 파이썬으로 구현하면 다음과 같다.
array = [2, 9, 4, 0, 1, 5, 6, 3, 7, 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[right]:
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)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
계수 정렬(Count Sort)
계수 정렬은 숫자들의 등장 횟수를 세어 리스트에 저장해뒀다가 그 횟수만큼 숫자를 출력하는 방식으로, 데이터의 값을 직접 비교하고 그 위치를 변경하는 방식으로 작동하는 기존의 정렬 알고리즘들과는 큰 차이가 있다.
계수 정렬은 아주 빠른 알고리즘이지만, 모든 데이터가 양의 정수인 상황에서만 사용할 수 있다.
데이터의 개수가 N, 데이터 중 최대값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 빠르고 효율적이라고 알려진 퀵 정렬조차 평균 시간복잡도가 O(NlogN)인것을 보면 계수 정렬은 분명히 막강한 정렬 알고리즘이다.
가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다. 계수 정렬을 사용할 때는 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다.
계수 정렬은 등장하는 모든 데이터를 인덱스로서 집어넣을 수 있을 만큼 충분히 큰 행렬을 선언하고, 데이터 별 등장 횟수를 기록하는 것으로 작동한다.
위 그림에서 Index - Value의 쌍으로 이루어진 리스트의 Index 부분은 등장한 데이터(값), Value 부분은 등장한 횟수이다.
모든 데이터를 읽어들인 후 각각의 Index를 Value만큼 출력하면 정렬되게 된다.
계수 정렬을 파이썬으로 구현하면 다음과 같다.
#모든 원소의 값이 0보다 크거나 같아야 함.
array = [6, 3, 1, 3, 2, 4, 3, 6, 5, 7, 2, 5, 1, 6, 4, 1, 2, 5, 1]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 1 증가
sorted_array = [] #정렬된 데이터를 저장할 빈 리스트 선언
for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
sorted_array.append(i) #리스트에 숫자 i를 등장한 횟수 만큼 추가
print(sorted_array)
[1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7]