[파이썬 알고리즘] 정렬 알고리즘 개요
업데이트:
정렬 알고리즘
정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미한다.
정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나로, 이 알고리즘을 알아야 이진 탐색이 가능해진다고 한다.
정렬 알고리즘을 배우며 알고리즘의 효율성을 이해할 수 있기에 매우 중요하다고 한다.
아래 이미지에 나와있는 카드를 기준으로 선택, 삽입, 퀵, 계수 정렬이 각각 어떤 방식으로 정렬이 되는지 설명하겠다.
선택 정렬
선택 정렬은 매번 가장 작은 것을 선택하는 알고리즘으로, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이다.
💻 파이썬 코드
1
2
3
4
5
6
7
8
9
10
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)
위 코드에서 스와프란 주석이 보일 것이다.
파이썬에서는 따로 임시 저장용 변수 없이 간단히 두 원소의 위치를 변경할 수 있다.
1
2
3
arr = [1, 2]
arr[0], arr[1] = arr[1], arr[0] # 인덱스 0과 1의 원소 교체
print(arr) # [2, 1]
🕒 시간 복잡도
반복문이 얼마나 중첩되었는지를 기준으로 간단히 시간 복잡도를 판단할 수 있기에, 선택 정렬의 시간 복잡도는 O(N^2)이다.
데이터의 개수가 많아지면 많아질수록 수행 시간은 그 제곱으로 늘어나게된다.
아래 정렬 수행 시간을 비교한 표를 확인해보자.
| 데이터의 개수 | 선택 정렬 | 퀵 정렬 | 기본 정렬 라이브러리 |
|---|---|---|---|
| 100 | 0.0123s | 0.00156s | 0.00000753s |
| 1,000 | 0.354s | 0.00343s | 0.0000365s |
| 10,000 | 15.475s | 0.0312s | 0.000248s |
컴퓨터마다 조금씩 시간이 다를 수는 있지만, 선택 정렬이 매우 많은 시간을 잡아먹는다는 것을 알 수 있다.
그렇다면 왜 비효율적인 선택 정렬을 배운 것일까?
특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 많기 때문에 익숙해질 필요가 있다고 한다..
삽입 정렬
선택 정렬은 위에서 매우 비효율적이라는 것을 알게됐다.
데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입한다면 조금 더 빨라지지 않을까?
즉, 이미 정렬되어있는 데이터는 손대지 않는 것이다.
현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 선택 정렬과 달리 삽입 정렬은 필요할 때만 위치를 바꾸는 알고리즘이다.
따라서 데이터가 거의 정렬되어 있을 때 더욱 효과적이라고 한다.
삽입 정렬은 다시 말해 특정한 데이터를 적절한 위치에 삽입하는 알고리즘이고, 삽입하기 전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
따라서 삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하여 두 번째 데이터부터 시작한다.
💻 파이썬 코드
1
2
3
4
5
6
7
8
9
10
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
호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다.
피벗을 정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
그 다음 찾은 데이터들의 위치를 교환해준다.
자세한 과정은 아래와 같다.
- 리스트의 첫 번째 데이터 피벗 설정
- 왼쪽에서부터 피벗보다 큰 데이터 탐색, 오른쪽에서부터 피벗보다 작은 데이터 탐색
- 위치 교환
- 2~3의 과정 반복
- 피벗보다 큰 데이터(오른쪽) 리스트와 작은 데이터(왼쪽) 리스트로 분할
- 각각의 리스트에 1~5의 과정을 수행
피벗 설정 - 정렬 수행 - 왼쪽/오른쪽 리스트에서 정렬 수행 - … 의 과정인것을 보아, 퀵 정렬은 재귀 함수와 동작 원리가 같다는 것을 알 수 있다.
이 말은 즉, 종료 조건이 필요하다는 뜻이다.
퀵 정렬의 종료 조건?
퀵 정렬은 현재 리스트의 데이터 개수가 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
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)
두번째 방법
파이썬의 장점을 살려 짧게 작성할 수도 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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(NlogN)이다. 선택 정렬과 삽입 정렬에 비해 굉장히 빠르다.
어떻게
O(NlogN)의 시간 복잡도를 가지게 되는 것일까?
설명하기 조금 어렵지만 쉽게 설명하자면, 리스트 분할이 정확히 절반씩 수행되었을때의 그림을 그려보자.
여기서 주의할 점은 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다고 한다.
따라서 N = 1,000 일 때, logN = 약 10 으로 매우 작은 수이다.
아래 표는 앞서 배운 두 정렬과 퀵 정렬의 평균 시간 복잡도를 비교한 것이다.
데이터의 개수 N |
선택/삽입 정렬 N^2 |
퀵 정렬 Nlog2N |
|---|---|---|
N = 1,000 |
약 1,000,000 |
약 10,000 |
N = 1,000,000 |
약 1,000,000,000,000 |
약 20,000,000 |
다만, 퀵 정렬의 경우 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 O(N^2)이 나오게 된다.
여기서 최악의 경우란?
이미 데이터가 정렬되어 있는 경우를 말하며 이 경우 매우 느리게 동작한다.
삽입 정렬과 반대된다고 말할 수 있겠다.
따라서 C++과 같이 퀵 정렬 기반의 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다고 한다.
파이썬 또한 마찬가지로 기본 정렬 라이브러리 이용시에 O(NlogN)을 보장해주기 때문에 마음 놓고 사용해도 된다.
계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
특정한 조건?
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때라는 특정한 조건이 부합할 때만 사용할 수 있다.
값이 무한한 범위를 가지지 않고, 최댓값과 최솟값의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다고 한다.
도대체 얼마나 빠른걸까?
현재 존재하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 볼 수 있다.
모든 데이터가 양의 정수인 상황일 때, 데이터의 개수가 N이고 데이터 중 최댓값이 K라면 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
기수 정렬 Radix Sort 계수 정렬에 비해 동작은 느리지만 처리할 수 있는 정수의 크기가 큰 정렬 방식으로 알고리즘 원리나 소스코드가 더 복잡하다.
계수 정렬의 특징은 속도 뿐만 아니라 원리도 매우 간단하다.
다만 앞서 다뤘던 정렬 알고리즘처럼 데이터의 값을 비교하는 방식이 아닌 별도의 리스트에 정렬에 대한 정보를 담는 방식을 사용한다.
별도의 리스트의 경우 정렬 할 리스트 데이터의 범위를 모두 포함하는 인덱스를 가져야 한다.
아래 예시 상황을 통해 계수 정렬은 데이터의 개수가 많아도 빠르게 동작한다는 것을 알아보자.
데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
데이터의 범위는 0부터 9까지 이므로 크기가 10인 리스트를 생성해주고 0으로 초기화한다.
그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시켜주면 된다.
최종적으로 아래와 같은 리스트가 생성이 될 것이다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 값 | 2 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1 | 2 |
각 데이터가 몇 번 등장했는지 그 횟수가 기록되었다는 것을 알 수 있다.
정렬된 결과를 확인하고 싶다면 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력해주면 되겠다.
정렬 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
💻 파이썬 코드
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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
🕒 시간 복잡도
앞에서 이미 말했지만 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다.
데이터를 하나씩 확인(N)하며 인덱스를 증가시킬 뿐만 아니라, 리스트의 각 인덱스에 해당하는 값들을 확인하는 것을 최댓값의 크기(K)만큼 반복하기 때문이다.
따라서 데이터의 범위만 한정되어 있다면 효과적이고 항상 빠르게 사용할 수 있다.
📊 공간 복잡도
공간 복잡도란 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다.
일반적인 코딩 테스트에서는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 계수 정렬의 공간 복잡도는 O(N+K)이다.
정리하자면…
만약 데이터가 0과 999,999로만 이루어져 있다면 리스트의 크기가 100만이 되도록 선언해야 한다.
위의 상황으로 보아 계수 정렬은 항상 사용할 수 있는 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다는 것을 알아두자.
계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며, 항상 사용할 수는 없다.
정렬 알고리즘 비교
| 정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|
| 선택 정렬 | O(N^2) |
O(N) |
원리가 매우 간단 |
| 삽입 정렬 | O(N^2) |
O(N) |
데이터가 거의 정렬되어 있을 경우 매우 빠름 |
| 퀵 정렬 | O(NlogN) |
O(N) |
대부분의 경우에 가장 적합, 충분히 빠름 |
| 계수 정렬 | O(N + K) |
O(N + K) |
데이터의 크기가 한정되어 있는 경우 매우 빠름 |
파이썬 정렬 라이브러리
파이썬에서는 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
sorted()는 퀵 정렬과 비슷한 병합 정렬을 기반으로 만들어졌고, 병합 정렬은 일반적으로 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
정확히 말하자면 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.
리스트, 딕셔너리 등의 자료형을 입력 받아 정렬된 결과를 리스트 자료형으로 반환한다.
1
2
3
4
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)
리스트 변수의 경우, 리스트 객체의 내장 함수인 sort() 함수를 이용하는 방법도 있다.
sort()는 별도의 리스트 반환 없이 기존 리스트의 원소가 바로 정렬된다.
1
2
3
4
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array)
sorted()나 sort()를 이용할 때 key 매개변수를 입력할 수 있다.
key 값으로는 정렬의 기준이 되는 하나의 함수(람다 함수도 가능)가 들어가야 된다.
1
2
3
4
5
6
7
8
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
# 각 데이터의 두 번째 원소 기준
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)
🕒 시간 복잡도
위에서 말했듯이 최악의 경우에도 O(NlogN)을 보장한다.
사실 직접 퀵 정렬을 구현하는 것보다 이미 잘 작성된 정렬 라이브러리를 사용하는 것이 더욱 효과적이다.
따라서 문제에서 별도의 요구가 없다면 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 경우 계수 정렬을 사용하면 된다.
문제 유형
정렬 알고리즘이 사용되는 문제 유형으로 아래 3가지를 들 수 있다.
-
정렬 라이브러리로 풀 수 있는 문제
정렬 기법을 알고 있는가? + 기본 정렬 라이브러리 사용 방법을 숙지하고 있는가?
-
정렬 알고리즘의 원리에 대해 물어보는 문제
선택/삽입/퀵 정렬 등의 원리를 알고 있는가?
-
더 빠른 정렬이 필요한 문제
퀵 정렬 기반의 정렬 기법으로는 풀 수 없고, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 한다.
Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 교재를 참고하였습니다.
댓글남기기