주로 많이 사용되는 정렬 7가지만 작성했으니 참고해주세요
# 시간복잡도 : O(N^2)
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
버블 정렬은 매번 연속된 두 인덱스를 비교합니다. 비교시마다 큰 값이 뒤로 교체되고 다음 인덱스로 이동합니다. 이후 계속 반복해서 비교하고 큰 값은 뒤로 교체됩니다. 한 바퀴 돌 때마다 가장 마지막에는 비교하는 수들 중 가장 큰 값이 저장되므로, 다음 바퀴를 돌 때에는 마지막 수는 제외하고 진행합니다.
# 시간복잡도 : O(N^2)
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[min_index], arr[i] = arr[i], arr[min_index]
배열을 선형 탐색해서 최소값의 인덱스를 찾습니다. 최소값의 인덱스를 이용해 왼쪽 끝 인덱스의 값과 스왑하고 정렬을 완료합니다. 버블정렬과 비슷하지만 연속된 두 값을 매번 비교하는게 아니라 인덱스를 이용하다보니 버블 정렬보다 2배 정도 빠르다고 합니다.
# 시간복잡도 : O(N^2)
def insertion_sort(arr):
for i in range(len(arr)):
key = arr[i]
j = i-1
# 오름차순 정렬 -> j인덱스의 값이 키보다 크면 계속 뒤로 넘기는 겁니다
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # while문에서 계속 j-1을 하므로 키값은 j+1에 넣어줘야합니다
이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입하는 경우에 최선의 알고리즘입니다. 가장 앞 쪽에 있는 원소는 이미 정렬되어 있다고 가정하고 시작합니다(첫 시작에 i보다 작은 인덱스에서 확인할 요소가 없습니다).
# 시간복잡도 : O(N * logN)
# 공간복잡도 : O(N)
def merge_sort(arr):
# 기저 조건
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# 재귀함수 실행
left_arr = merge_sort(arr[:mid])
right_arr = merge_sort(arr[mid:])
# 재귀가 끝난 후, 병합하는 과정에서 값을 비교해 정렬한 형태로 만들고 반환
merged_arr = []
l = r = 0
while l < len(left_arr) and r < len(right_arr):
if left_arr[l] > right_arr[r]:
merged_arr.append(left_arr[l])
l += 1
else:
merged_arr.append(right_arr[r])
r += 1
# 남은 값들 이어붙이기
merged_arr += left_arr[l:]
merged_arr += right_arr[r:]
return merged_arr
분할정복 & 재귀 알고리즘을 이용해 해결하는 정렬 알고리즘입니다. 배열을 두 개의 배열로 계속 분할하기 때문에 재귀의 기저 조건은 배열의 크기가 1보다 작거나 같은 경우입니다. mid 인덱스를 이용해 두 개의 배열로 분할하여 재귀함수를 실행합니다. 기저 조건에 의해 재귀가 종료되면, 병합하는 과정이 시작됩니다. 두 배열을 비교하며 작은 값을 앞쪽에 넣어주면 됩니다. 병합 과정도 끝나면 병합된 배열을 반환합니다.
예시를 하나 들어보자면, 이런 식으로 분할되고 병합됩니다 :
# 분할 과정
[2, 6, 9, 3, 9]
/ \\
[2, 6] [9, 3, 9]
/ \\ / \\=
[2] [6] [9] [3, 9]
/ \\
[3] [9]
# 병합 과정
- [2] + [6] → [2, 6]
- [3] + [9] → [3, 9]
- [9] + [3, 9] → [3, 9, 9]
- [2, 6] + [3, 9, 9] → [2, 3, 6, 9, 9]
# 시간복잡도 : 평균적으로는 O(N * logN), 최악의 경우엔 O(N^2)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
smaller_arr, equal_arr, bigger_arr = [],[],[]
for num in arr:
if num < pivot:
smaller_arr.append(num)
elif num == pivot:
equal_arr.append(num)
else:
bigger_arr.append(num)
return quick_sort(smaller_arr) + eqaul_arr + quick_sort(bigger_arr)
병합 정렬처럼 분할 정복 기법과 재귀 알고리즘을 이용하는 정렬 알고리즘입니다. 재귀의 기저 조건은 병합 정렬과 마찬가지로 배열의 크기가 1보다 작거나 같은 경우입니다. 그리고 퀵 정렬은 pivot이라는 임의의 기준값을 이용해 배열을 분할합니다. 이때, pivot 값을 중앙값, 평균값 등등 여러 방법으로 설정할 수 있습니다(임의니까요). pivot 값을 설정하고나면, pivot보다 작은 값과 큰 값으로 배열을 분리합니다. 분리한 두 배열은 다시 퀵 정렬을 재귀적으로 수행합니다.