Algorithm/Learning
정렬 알고리즘 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 버블정렬, 합병정렬, 힙정렬, 정렬 라이브러리)
앵도라지
2023. 1. 31. 17:46
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다.
정렬 알고리즘은 상당히 다양한 종류가 있고, 파이썬에서는 기본 정렬 라이브러리를 사용해서 효과적으로 정렬할 수 있다.
1. 선택 정렬
1-1. 선택 정렬 개념
💡 선택 정렬 - “가장 작은 것을 선택”
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
1-2. 선택 정렬 구현(Python)
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-3. 선택 정렬 시간복잡도
- 시간복잡도 : O(N^2)
- N + (N-1) + (N-2) + … + 2
- N(N+1) ⇒ O(n^2) 시간 복잡도
- 반복문 2번이 중첩되어 있음
- N + (N-1) + (N-2) + … + 2
2. 삽입 정렬
2-1. 삽입 정렬 개념
💡 삽입 정렬 - “특정한 데이터를 적절한 위치에 삽입함”
- 데이터가 거의 정렬되어 있을 때 효율적임
- 삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정함
2-2. 삽입 정렬 구현(Python)
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):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)
2-3. 삽입 정렬 시간복잡도
- 시간 복잡도 : O(N**2)
- 현재 리스트가 어느정도 정렬되어 있는 상태라면 매우 빠르게 동작함
- 최선의 경우 O(N)
- 반복문 2번 중첩되어 있음
- 현재 리스트가 어느정도 정렬되어 있는 상태라면 매우 빠르게 동작함
3. 퀵 정렬
3-1. 퀵 정렬 개념
💡 퀵 정렬 - “기준 설정, 기준보다 큰 데이터와 작은 데이터 위치 변경”
- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식
- 가장 많이 사용되는 정렬 알고리즘
- 언어에서 제공하는 정렬 라이브러리의 근간이 되는 알고리즘
- “피벗”(기준)이 사용됨
- 피벗의 설정 기준은 미리 명시해야 함
3-2. 퀵 정렬 구현
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
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)
3-3. 파이썬 최적화 (시간면에서 조금 비효율적이나, 더 직관적이고 기억하기 쉬움)
array = [7, 5, 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))
3-4. 퀵 정렬 시간 복잡도
- 시간복잡도 : O(NlogN)
- 최악의 경우 O(N^2) 만큼의 시간이 소요됨
- 퀵 정렬은 삽입 정렬과 다르게 이미 데이터가 정렬되어 있는 경우 매우 느리게 동작함
4. 계수 정렬
4-1. 계수 정렬 개념
💡 계수 정렬 - “별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음”
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 데이터 크기가 범위가 제한 되어 정수 형태로 표현할 수 있을 때에만 사용
- 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어려움
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 사용 하는 것이 일반적임
- 직접 데이터 값을 비교한 뒤에 위치를 변경하여 정렬하는 방식의 비교 기반 정렬 알고리즘이 아님
4-2. 계수 정렬 구현 (Python)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
#모든 범위를 포함하는 리스트 선언 (모든 값은 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=' ')
4-3. 계수 정렬 시간 복잡도 / 공간 복잡도
- 시간 복잡도 = O(N +K)
- 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)
- 현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 할 수 있음
- 공간복잡도 = O(N + K)
- 때에 따라서 심각한 비효율성을 초래할 수 있음
- 항상 사용할 수 있는 알고리즘은 아니고, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합함
5. 버블 정렬
5-1. 버블 정렬 개념
💡 버블 정렬 - “서로 인접한 두 원소를 검사하여 정렬하는 알고리즘”
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환함
- 선택 정렬과 기본 개념이 유사
- 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
5-2. 버블 정렬 구현(Python)
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
5-3. 파이썬 최적화
def bubble_sort(arr):
end = len(arr) - 1
while end > 0:
last_swap = 0
for i in range(end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
last_swap = i
end = last_swap
5-4. 버블 정렬 시간 복잡도
- 시간 복잡도 : O(N^2)
- 효율적인 알고리즘은 아니나, 구현이 간편함
- 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
6. 합병 정렬
6-1. 합병 정렬 개념
💡 합병 정렬 - “주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합침”
- 분할 정복과 재귀 알고리즘을 이용한 정렬 알고리즘
- 항상 일정한 시간 복잡도를 갖음
- 안정성이 높기 때문에 대부분의 경우에 좋은 성능을 내는 편
- 인접한 값들 간의 자리 교환(swap)이 발생하지 않음
6-2. 합병 정렬 구현
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
low_arr = merge_sort(arr[:mid])
high_arr = merge_sort(arr[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
return merged_arr
6-3. 파이썬 최적화
def merge_sort(arr):
def sort(low, high):
if high - low < 2:
return
mid = (low + high) // 2
sort(low, mid)
sort(mid, high)
merge(low, mid, high)
def merge(low, mid, high):
temp = []
l, h = low, mid
while l < mid and h < high:
if arr[l] < arr[h]:
temp.append(arr[l])
l += 1
else:
temp.append(arr[h])
h += 1
while l < mid:
temp.append(arr[l])
l += 1
while h < high:
temp.append(arr[h])
h += 1
for i in range(low, high):
arr[i] = temp[i - low]
return sort(0, len(arr))
6-4. 합병 정렬 시간 복잡도
- 시간 복잡도 = O(NlogN)
- 배열을 분할하면서 반복의 횟수는 점점 절반으로 줄어들기 때문에 O(NlogN)의 시간이 소모됨
- 배열을 병합하는 과정에서 배열의 모든 원소를 비교해야 하므로 O(N) 만큼의 시간이 필요
- 따라서 합병 정렬의 시간 복잡도는 O(NlogN)
7. 힙 정렬
7-1. 힙 정렬 개념
💡 힙 정렬 - “어떤 부모 노드의 두 자식 노드 중 크기가 더 큰 자식을 부모와 바꾸는 알고리즘”
- 힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됨
- 힙에는 최대 힙과 최소 힙이 존재
- 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리
- 힙 정렬은 힙 생성 알고리즘을 사용함
7-2. 힙 정렬 구현
def heapify(unsorted, index, heap_size):
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < heap_size and unsorted[right] > unsorted[largest]:
largest = left
if right < heap_size and unsorted[right] > unsorted[largest]:
largest = right
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
7-3. 힙 정렬 시간 복잡도
- 시간복잡도 : O(NlogN)
- 힙 구조 생성시 연산 수는 힙의 높이와 동일
- 힙 생성(Heapify)알고리즘 시간 복잡도 : O(log N) * 전체 데이터 수 N
- O(N * logN) = O(NlogN)
8. 정렬 라이브러리
위의 내용을 종합하여 봤을 때, 정렬 알고리즘은 매우 많은 종류가 존재한다.
따라서, 코딩테스트에서 정렬 문제를 만난다면 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제 유형에 속한다.
파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬 보다 느리지만 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장한다.
또, sorted()나, sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬의 기준이 된다. 혹은 람다 함수를 사용할 수 있다.
문제 풀이 팁
- 파이썬 정렬 라이브러리는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용한다.
- 문제에서 별도의 요구가 없는 단순 정렬 상황 : 정렬 라이브러리 사용
- 데이터 범위가 한정되어 있고 빠르게 동작해야 할 때 : 계수정렬 사용
9. 정렬 알고리즘이 사용되는 경우
코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.
- 정렬 라이브러리로 풀 수 있는 문제
- 단순히 정렬 기법을 알고 있는지 물어보는 문제
- 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
- 정렬 알고리즘의 원리에 대해서 물어보는 문제
- 선택정렬, 삽입정렬, 퀵정렬 등의 알고리즘 동작 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제
- 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
10. 연관 문제
이제 정렬 알고리즘에 대한 개념 학습은 끝났다. 바로 실제 문제를 풀어보자!
[백준]
- 나이순정렬(10814) - https://www.acmicpc.net/problem/10814
- 국영수(10825) - https://www.acmicpc.net/problem/10825
[프로그래머스]
- K번째 수 - https://school.programmers.co.kr/learn/courses/30/lessons/42748
- 가장 큰 수 - https://school.programmers.co.kr/learn/courses/30/lessons/42746
[SWEA]