정렬 알고리즘 개요
데이터를 특정 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.
정렬 알고리즘의 종류는 매우 다양하다. 이 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 정리한다.
[9, 4, 5, 3, 8, 7, 1, 3, 2, 6] 다음과 같은 뒤섞인 문자 리스트를 오름차순으로 정렬하는데.
다음과 같은 방식들이 있다.
선택 정렬
리스트 중 가장 작은 데이터를 선택해 리스트 맨 앞에 있는 데이터와 바꾼다. 그 다음 작은 데이터를 선택해 두번째 데이터와 바꾸는 과정을 반복한다.
<책과 코드가 완전히 다릅니다. 필자가 작성해본 코드>
import sys
import time
sys.stdin=open("input.txt", "r")
data = list(map(int, input().split()))
for i in range(0, len(data)):
tmp_list = data[i:]
// 최소값 구하기
min_value = min(tmp_list)
// 앞의 데이터와 최소값 서로 바꾸
tmp = data[data.index(min_value)]
data[data.index(min_value)] = data[i]
data[i] = tmp
print(data)
선택 정렬의 시간 복잡도
N + (N - 1) + (N - 2) + . . . + 2 = N X (N + 1) / 2
따라서 빅오 표기법에 따라 O(N^2)라고 할 수 있다. 따라서 데이터가 증가하면 매우 많은 시간이 걸릴 수 있다.
삽입 정렬
선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 다만 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있는 때 사용하면 훨씬 효율적이다. 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라 한다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 위에, 그 위치에 삽입한다.
import sys
import time
sys.stdin=open("input.txt", "r")
data = list(map(int, input().split()))
print("정렬 전 리스트 : ", data)
for i in range(1, len(data)):
for j in range(i, 0 , -1):
if data[j] < data[j-1]:
data[j], data[j-1] = data[j-1], data[j]
else:
break
print(data)
삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었기 때문이다.
데이터가 이미 거의 다 정렬되어진 상황에서는 그 어떠한 정렬 알고리즘보다 삽입 정렬이 빠를 수 있다. 따라서 데이터가 거의 정렬되어 있는 경우에는 삽입 정렬을 사용하는 것이 정답이 될 수 있다.
퀵 정렬
정렬 알고리즘 중 가장 많이 사용되는 알고리즘. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 이 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분한다.
import sys
import time
sys.stdin=open("input.txt", "r")
data = list(map(int, input().split()))
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 2
right = end
while left <= right:
while array[left] <= array[pivot] and left <= end:
left += 1
while array[right] >= array[pivot] and right >= 0:
right -= 1
if left > right:
array[pivot], array[right] = array[right], array[pivot]
else:
tmp = array[left]
array[left] = tmp_list[right]
array[right] = tmp
quick_sort(array, 0, right-1)
quick_sort(array, right + 1, end)
quick_sort(data, 0, len(data) - 1)
파이썬의 장점을 살린 퀵 정렬
import sys
import time
sys.stdin=open("input.txt", "r")
data = list(map(int, input().split()))
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)이다. 데이터가 많을 수록 앞의 선택 정렬, 삽입 정렬보다 훨씬 빠르게 동작한다.
다만 삽입 정렬과 반대로 데이터가 대부분 제대로 정렬되어 있는 경우에는 느리게 작동한다.
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 계수 정렬이 효과적이다. 이러한 특징을 가지는 이유는 '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'해야 하기 때문이다.
import sys
import time
sys.stdin=open("input.txt", "r")
data = list(map(int, input().split()))
min_value = min(data)
max_value = max(data)
array = [0] * (max_value - min_value + 1)
for i in range(len(data)):
x = data[i]
array[x] += 1
for i in range(len(array)):
for j in range(array[i]):
print(i, end = ' ')
계수 정렬의 시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다.
파이썬의 정렬 라이브러리
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)
array.sort()
print(result)
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)
정렬 라이브러리의 시간 복잡도
정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
[출처] 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 지음)