개요
정렬이란 데이터를 특정한 기준에 따라 순서대로 나열 하는 것이다. 이러한 정렬은 이진 탐색의 필수 조건이기도 하다. 정렬 알고리즘은 다양한데, 그중에서 선택, 삽입, 퀵, 계수 정렬에 대해서 알아보도록 하자.
선택 정렬
데이터가 무작위로 여러개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다고 해보자. 이 방법은 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다.
- 위 그림처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1 번 반복하면 정렬이 완료된다. 매 과정에서 가장 작은 숫자를 찾기 위한 비교 연산이 필요하다. 따라서 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2로 볼 수 있다. 따라서 시간 복잡도는 O(N^2) 라고 할 수 있다.
삽입 정렬
삽입 정렬은 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 알고리즘이다. 그래서 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 아래 예시를 참고해보자.
- 앞서 얘기했다시피, 앞의 데이터는 정렬되어 있다고 가정하기 때문에,
5부터 삽입 정렬을 시작한다.5는7의 왼쪽, 오른쪽 중에 왼쪽에 위치한다. - 다음으로
9는57사이 사이에 총 3군데에 들어갈 공간이 있는데, 이중7오른쪽으로 삽입한다. - 위 과정을 반복하면 정렬이 완료된다.
#소스코드
array = [7, 5, 3, 9]
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) # [3, 5, 7, 9]- 삽입 정렬 시간 복잡도는 (2중 반복문을 사용했으므로) O(N^2) 인데, 데이터가 거의 정렬되어 있는 상태라면 O(N) 의 시간 복잡도를 가진다.
퀵 정렬
퀵 정렬은 기준 데이터(pivot) 을 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘이다.
피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬의 종류가 다르지만, 본 포스팅에서는 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 이해해보도록 하자.
- 퀵 정렬은 크게 3단계로 나뉘어진다.
- 1단계는 첫번째 데이터를 피벗(
5)으로 설정하고, 왼쪽에서부터5보다 큰 숫자를 탐색하고 오른쪽에서부터5보다 작은 숫자를 탐색한다. 그리고 이 둘의 위치를 바꿔 준다. - 2단계는 만약에 피벗인
5보다 큰 숫자와,5보다 작은 숫자의 위치가 엇갈린 경우 작은데이터인1과 피벗인5를 바꾸어 준다. - 마지막 3단계는 분할이다. 피벗과 작은 숫자를 바꾸면, 왼쪽은 피벗보다 작은 숫자들의 모음이고, 오른쪽은 피벗보다 큰 숫자들의 모음이다. 따라서 왼쪽과 오른쪽으로 분할 하여 각각 다시 퀵정렬을 수행한다.
ex)1 4 2 0 3(1을 피벗 삼아서 다시 퀵정렬) /6 9 7 8(6을 피벗 삼아서 다시 퀵정렬)
퀵정렬 소스 코드
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)
#실행결과: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(quick_sort(array))퀵 정렬 시간 복잡도
시간복잡도가 O(N^2) 인 선택 정렬과 삽입 정렬과 달리, 퀵 정렬의 평균 시간복잡도는 O(NlogN) 이다. 최선의 경우를 생각해보자. 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 어떨까? 데이터 개수가 8개인 경우 아래와 같다.
- 최선의 경우에는 분할이 이루어지는 횟수가 기하급수적으로 감소한다.
- 다만 평균적으로 시간복잡도가 O(NlogN)이지, 데이터가 이미 정렬되어 있는 경우에는 O(N^2) 이다.
- 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작하지만, 퀵 정렬은 반대이다.
계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황에서, 데이터 개수가 N 데이터 중 최대값이 K일때 시간복잡도 O(N + K) 를 보장한다. 계수 정렬은 모든 범위를 담을 수 있는 크기의 리스트를 선언 하여 사용한다.
일반적으로 가장큰 데이터와 가장 작은 데이터 차이가 100만을 넘지 않을 때 효과적으로 사용할 수 있다. 또한 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다
소스코드
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]):
#실행결과: 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
print(i, end=' ')- 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인하는 과정을 거치기에 시간복잡도는 O(N + K)이다.
- 계수정렬은 때에 따라서 심각한 비효율성을 초래할 수도 있다. 예를 들어 데이터가 0과 999999 단 2개만 존재할 때 리스트의 크기가 100만개가 되도록 선언해야하기 때문이다.
- 즉, 계수정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을 수록 유리하다.
