해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️
정렬
정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
정렬 알고리즘은 다음에 포스팅할 이진 탐색의 전처리 과정이라고 할 수 있다.
많은 정렬 알고리즘들 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자.
이 정렬 알고리즘들을 공부하면서 알고리즘의 효율성의 중요성을 자연스럽게 깨닫게 될 수 있다.
선택 정렬
선택정렬은 맨 앞의 데이터부터 가장 작은 데이터를 맨 앞으로 보내면서 데이터를 정렬하는 방식이다. 이렇게 가장 작은 데이터가 맨 앞에 오게 되면, 그 다음 두 번째 자리부터 이를 다시 반복하게 된다.
이를 파이썬 코드로 표현하면 다음과 같다.
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)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]이때 주석에 쓰인 스와프는 특정한 리스트가 있을 때, 두 변수의 위치를 변경하는 작업을 의미한다. 이는 파이썬이 아닌 다른 대부분의 프로그래밍 언어에서는 직관적으로 시행되지 않는 경우가 많으니 참고하자.
선택 정렬의 시간 복잡도
선택 정렬의 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다.
따라서 이의 근사치는 N x (N+1) / 2 라고 할 수 있다. 이의 빅오 표기법으로는 O(N2)이다.
그러므로 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 속도가 급격히 느려지는 것을 확인할 수 있다. 실제로 대부분의 정렬 알고리즘과 비교했을 때, 매우 비효율적이지만 이 선택 정렬의 방식은 특정 리스트에서 가장 작은 데이터의 값을 찾는 때 자주 쓰이므로 익숙해져야 한다.
삽입 정렬
삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입하는 알고리즘이다. 따라서 이는 데이터가 거의 정렬이 되어 있을 경우 더욱 효율적이다.
첫번째의 데이터는 정렬이 되어있다고 보고 두번째의 데이터부터 정렬이 되어있는 데이터들 사이에 적절히 삽입하면서 (선택정렬과는 달리) 한 턴에 정렬이 완료되는 알고리즘이다.
이를 파이썬 코드로 표현하면 다음과 같다.
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까지 감소하면서 반복
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 데이터가 있을 때, 해당 위치에 멈춤
break
print(array)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]삽입 정렬의 시간 복잡도
선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었으므로, 삽입 정렬의 시간 복잡도는 O(N2)이다. 여기서 기억해두어야 할 점은 삽입 정렬은 거의 정렬이 되어 있는 데이터의 경우, 매우 빠르게 동작한다는 점이다. 이 경우에는 O(N)의 시간복잡도를 가질 수도 있게 된다. 심지어는 거의 정렬이 되어있는 경우에는 다음에 배울 퀵 정렬보다 삽입 정렬이 더 효율적인 알고리즘이다.
퀵 정렬
퀵 정렬은 지금까지의 정렬 알고리즘 중 가장 보편적으로 사용되는 알고리즘이다. 대부분의 상황에서 효율적인 알고리즘이기 때문이다. 퀵 정렬은 기준값을 정한 후, 이를 기준으로 큰 수들은 오른쪽으로 작은 수들은 왼쪽으로 정렬하면서 동작한다. 이때 기준이되는 값을 '피벗'이라고 한다. 이때 피벗을 설정하는 방식은 다양한데, 여기서는 첫번째 데이터를 피벗으로 정하는 것으로 설정하자.
이미지 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
일반적으로 사용되고 있는 퀵 정렬의 소스코드는 다음과 같다.
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)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]시간 면에서 조금 비효율적이지만, 이보다 더 직관적인 코드는 다음과 같다.
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))[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]퀵 정렬의 시간 복잡도
앞에서 배웠던 선택 정렬과 삽입 정렬의 시간 복잡도는 O(N2)이었다. 이에 반해 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 그러나 이때 주의할 점은 최악의 경우에 대한 시간 복잡도는 O(N2)라는 점이다. 무작위로 입력된 데이터의 경우 퀵 정렬은 효율적이지만, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작된다. 즉, 삽입 정렬은 데이터가 거의 정렬되어 있는 경우 효율적이라고 하였는데, 이와 반대의 경우라고 생각하면 된다.
계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합하는 경우에만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다.
계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있는 경우'에만 사용할 수 있다. 즉, 데이터의 범위가 무한한 실수형 데이터인 경우 계수 정렬을 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
계수 정렬이 이러한 조건을 가지는 이유는, 계수 정렬 이용 시 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문이다. 즉, 가장 큰 데이터와 가장 작은 데이터의 차이가 N 이라면 총 N+1개의 데이터가 들어갈 수 있는 리스트를 초기화해야 한다.
계수 정렬은 이전의 설명했던 정렬 알고리즘들처럼 직접 데이터의 값들을 비교한 후, 위치를 변경하며 정렬하는 방식이 아니다. 계수 정렬은 별도의 리스트를 선언하고 그 안에 데이터들의 정보를 저장하는 식으로 정렬된다.
- 데이터 배열을 처음부터 끝까지 돌면서 각 요소가 몇번 나왔는지 count배열에 저장한다.
- count 배열의 누적합을 구한다. (카운트 된 숫자들 간의 빈 공간이 있을 때, 이에 대한 비효율성을 줄이기 위하여 필요하다.)
- 원래 데이터 배열과 카운트 누적 리스트를 비교하며, 정렬된 리스트를 생성한다.
이를 파이썬 코드로 표현하면 다음과 같다.
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]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력0 0 1 1 2 2 3 4 5 5 6 7 8 9 9계수 정렬의 시간 복잡도
데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라 하면 계수 정렬의 시간 복잡도는 O(N+K)이다. 따라서 데이터의 범위만 한정되어 있다면 매우 빠르게 동작한다. 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠르다고 볼 수 있다. 그러나, 계수정렬은 특정 범위내에서 반복되는 숫자가 많은 데이터의 경우에 효율적인 알고리즘이므로, 만약 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.
++ 참고
파이썬 기본 정렬 라이브러리인 sorted()는 퀵정렬과 비슷한 병합 정렬을 기반으로 만들어졌다. 이는 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다. 리스트 객체의 내장함수인 sort() 또한 이와 마찬가지이다.
따라서 코딩 테스트의 문제에서 별도의 요구가 없이 단순히 정렬을 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 하는 경우에는 계수 정렬을 사용하도록 하자.
