다음 포스팅
정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
정렬 알고리즘은 굉장히 다양한데 이중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 알아보도록 하자.
오름차순을 내림차순으로, 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다. 우선 오름차순을 기준으로 알아보도록 하자.
선택 정렬
선택 정렬(Selection Sort) 알고리즘은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것이다. 원시적으로 매번 '가장 작은 것을 선택'한다는 것이다.
간단하게 보면 다음과 같다.
1. 가장 작은 데이터를 찾는다.
2. 맨 앞의 데이터와 위치를 바꾼다(swap)
이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 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-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하고 매번 가장 작은 수를 찾기 위한 비교 연산이 필요하다. 이를 빅오 표기법으로는 O(N^2)의 시간복잡도를 가진다고 표현할 수 있다.(2중 반복문을 쓴다고 생각하면 편함)
선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 비효율적이다. 다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다. 그러므로 선택 정렬 소스코드를 자주 작성해볼 것을 권장한다.
삽입 정렬
삽입 정렬(Insertion Sort)는 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 알고리즘이다. 선택 정렬에 비해 구현 난이도가 높은 편이지만 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하는 특징이 있다. 소스코드는 다음과 같다.
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): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)시간복잡도는 O(N^2)이다. 정렬이 거의 되어있는 상태라면 훨씬 빠르게 동작하므로 최선의 경우 O(N)의 시간 복잡도를 가진다.
퀵 정렬
퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 병합 정렬과 더불어 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 한다.
퀵 정렬에서는 피벗(Pivot)을 사용한다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작하는데 여기서 교환하기 위한 기준이 되는것이 피벗이다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분한다.
가장 대표적인 호어 분할(Hoare Partition) 방식을 기준으로 퀵 정렬을 설명하도록 하겠다.
호어 분할에서는 리스트에서 첫번째 데이터를 피벗으로 정한다. 과정은 다음과 같다.
1. 피벗을 정한다.
2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
3. 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
4. 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾고 위치를 교환하는 작업을 반복한다.
5. 왼쪽에서부터 찾는 값(피벗보다 큰 데이터)과 오른쪽에서부터 찾는 값(피벗보다 작은 데이터)의 위치가 서로 엇갈린 경우 '작은 데이터'와 '피벗'의 위치를 서로 변경한다.(이 작업 이후에 피벗의 왼쪽은 피벗보다 작고, 피벗의 오른쪽은 피벗보다 커진다. 이런 작업을 분할(Divide)혹은 파티션(Partition)이라고 한다.)
6. 그리고 피벗 왼쪽과 오른쪽에 대해 각각 퀵 정렬을 진행한다.
이는 재귀함수와 동작 원리가 같아 실제로 재귀함수 형태로 작성했을 때 구현이 매우 간결해진다. 퀵 정렬은 현재 리스트의 데이터 개수가 1개인 경우 더이상 분할이 불가능하므로 종료 조건이다. 다음은 소스코드이다.
# 일반적인 퀵 정렬
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(array, right + 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 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)
print(quick_sort(array))앞의 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N^2)을 보장한다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)으로 앞의 두 방법에 비해 빠른 편이다. 하지만 최악의 경우의 시간 복잡도는 O(N^2)이다.
퀵 정렬에서 최선의 경우는 피벗값의 위차가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할하는 경우이다.
데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높지만 '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.
계수 정렬
계수 정렬(Count Sort)는 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
특정 조건이란 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'를 말한다. 이러한 조건을 가지는 이유는 계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야하기 때문이다.
계수 정렬은 일반적ㅇ로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.
소스코드는 다음과 같다.
# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력모든 데이터가 양의 정수라고 가정했을 때 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다.
기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다. 일반적으로 데이터의 특성을 파악할 수 없다면 퀵 정렬을 이용하는 것이 유리하다.
계수 정렬의 공간 복잡도는 O(N+K)이다.
파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sroted() 함수를 제공한다. 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
array = [7,5,9,0,3,1,6,2,4,8]
result = sorted(array)
array.sort()sorted() 함수는 정렬된 결과를 출력하고, sort()는 리스트 객체의 내장 함수로 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.
코딩 테스트에서 정렬 알고리즘이 사용되는 경우는 일반적으로 3가지 문제 유형으로 나타낼 수 있다.
1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
