정렬(Sorting)
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬 알고리즘은 이진 탐색의 전처리 과정)
이번 글에서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 다뤄보자.
1. 선택 정렬(Selection Sort)
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
가장 원시적인 방법이며 매번 가장 작은 것을 선택하는 의미에서 선택 정렬이다.
소스코드
1
2
3
4
5
6
7
8
9
10
array = [ 9, 1, 6, 8, 4, 3, 2, 0 ]
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, 10]
예시
그림 출처 : 위키백과
선택 정렬 시간 복잡도
선택 정렬은 N-1번 반큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함. 2중 반복문이 사용되었기 때문에 따라서 시간 복잡도는 $O(N^2)$이다.
선택 정렬을 사용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다.
그림 출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬
선택 정렬은 다른 알고리즘과 비교했을 때 매우 비효율적임. 하지만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.
2. 삽입 정렬(Insertion Sort)
삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘이다.
선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 필요할 때만 위치를 바꾼다.
소스코드를 보면 삽입 정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
소스코드
1
2
3
4
5
6
7
8
array = [ 3, 7, 2, 5, 1, 4 ]
for i in range ( 1 , len ( array )):
for j in range ( i , 0 , - 1 ): # 인덱스 i 부터 0 까지 -1씩 감소하며 반복
if array [ j ] < array [ j - 1 ]: # 한 칸씩 왼쪽으로 이동
array [ j ], array [ j - 1 ] = array [ j - 1 ], array [ j ]
else : # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print ( array )
[1, 2, 3, 4, 5, 7]
참고) range의 매개 변수는 (start, end, step)이다.
삽입 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다.
이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.
예시
그림 출처 : 위키백과
예를 들어, step (c)를 보면 ‘5’는 한 칸씩 왼쪽으로 이동하다가 자신보다 작은 ‘3’을 만났을 때 그 위치에 삽입된다.
다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다.
삽입 정렬 시간 복잡도
삽입 정렬의 시간 복잡도는 $O(N^2)$인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다.
실제로 수행 시간은 선택 정렬과 흡사한 시간이 소요된다. 하지만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다.
최선의 경우 $O(N)$의 시간 복잡도를 가진다. 뒤의 퀵 정렬과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있느 상황에서는 퀵 정렬 보다 강력하다.
따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 다른 정렬 알고리즘을 사용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.
3. 퀵 정렬(Quick Sort)
지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 병합 정렬 알고리즘이 있다.
이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
퀵 정렬에서 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ‘기준’을 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 이번에는 호어 분할 (Hoare Partition) 방식을 사용한다.
호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다.
- 리스트에서 첫 번째 데이터를 피벗으로 정한다.
퀵 정렬은 아래와 같이 재귀 함수로 구현되는데, 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from typing import List
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array: List[int], start: int, end: int) -> List[int]:
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)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
예시
예시의 그림은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임.
다음과 같이 초기 데이터가 구성되어 있다고 가정해보자.
이제 퀵 정렬을 3개의 파트로 나눠서 보자.
Part 1.
step 0
리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 ‘5’이다. 이후에 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택되고, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다. 이제 두 데이터의 위치를 서로 변경한다.
step 1
그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데 현재 ‘9’와 ‘2’가 선택 되었으므로 위치를 서로 변경한다.
step 2
그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다(left > right). 이 경우에는 작은 데이터와 피벗의 위치를 서로 변경한다. 즉 ‘1’과 ‘5’의 위치를 서로 변경하여 분할을 수행한다.
step 3
분할 완료. 이제 ‘5’의 왼쪽에 있는 데이터는 모두 ‘5’보다 작고 오른쪽에 있는 데이터는 모두 ‘5’보다 크다.
이렇게 데이터가 위치하도록 하는 작업을 분할(Devide), 또는 파티션(Partition)이라고 한다.
이제 현재 피벗을 기준으로 왼쪽과 오른쪽 리스트에서 각각 피벗을 새로 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어 지게 된다.
Part 2.
Part 3.
퀵 정렬 시각 복잡도
선택 정렬과 삽입 정렬의 시간 복잡도는 $O(N^2)$ 이었다. 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 $O(N^2)$를 보장한다.
퀵 정렬의 시간 복잡도는 $O(NlogN)$이다. 앞서 나온 두 정렬 알고리즘에 비해 매우 빠른 편이다. 다만, 최악의 경우에는 시간 복잡도가 $O(N^2)$ 이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다.
예시에서처럼 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다. 삽입 정렬과는 반대된다고 할 수 있다.
4. 계수 정렬(Count Sort)
모든 데이터가 양의 정수인 상황에서, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능한 매우 빠른 정렬 알고리즘.
예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
0이상 100이하인 성적 데이터를 정렬할 때 계수 정렬이 효과적이다.
이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 ‘모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문이다.
가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화해야 한다.
계수 정렬 알고리즘은 앞서 다뤘던 것과는 다르게 비교 기반의 정렬 알고리즘이 아니다.
계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
예시
먼저, 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
정렬할 데이터의 범위는 0부터 9까지이므로 다시 말해 단순히 크기가 10인 리스트를 선언하면 된다.
그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
…
이 과정을 반복한다.
계수 정렬 시간 복잡도
데이터의 개수를 N, 데이터 중 최대값의 크기를 K라 할 때, 시간 복잡도는 $O(N+K)$ 이다.
계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.
따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
계수 정렬 공간 복잡도
예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정해보면 이럴 때에도 리스트의 크기가 100만개가 되도록 선언해야 한다. 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
퀵 정렬은 일반적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.
4. 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.
병합 정렬은 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다는 특징이 있다.
추가로, 리스트 객체의 내장 함수인 sort()를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.
1
2
3
array = [ 7 , 5 , 9 , 0 , 3 , 1 , 6 , 2 , 4 , 8 ]
result = sorted ( array )
print ( result )
[ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
1
2
3
array = [ 7 , 5 , 9 , 0 , 3 , 1 , 6 , 2 , 4 , 8 ]
array.sort()
print ( array )
[ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
key 매개 변수를 입력으로 받을 수 있는데, key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 람다 함수를 사용할 수도 있다.
1
2
3
4
5
6
7
array = [('바나나', 2 ), ('사과', 5 ), ('당근', 3 )]
def setting ( data ):
return data [ 1 ]
result = sorted ( array , key = setting )
print ( result )
[(‘바나나’, 2 ), (‘당근’, 3 ), (‘사과’, 5 )]
정렬 라이브러리 시간 복잡도
항상 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다.
문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하는 게 좋다.
코딩 테스트 정렬 알고리즘 유형은 다음과 같다.
- 정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
- 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.