🔍 정렬
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending.
📔 버블 정렬
버블정렬은 매번 인접한 인덱스의 값을 비교하여, 비교시마다 큰 값이 뒤로 교체되고, 그 다음 인덱스부터 비교를 반복한다. for문을 한바퀴 돌 때마다 가장 큰 값이 가장 마지막에 저장되기 때문에, 그 다음 반복에서는 마지막 인덱스는 제외하고 비교한다.
가장 첫번째 인덱스에 있는 값이 가장 클 경우 그 다음 인덱스 값과 계속 스왑하여 마지막 자리까지 가야하기 때문에 비효율적이다. 해당 정렬의 시간복잡도는 O(n^2)이다.
🔤 구현 코드
def bubblesort(lst):
iters = len(lst) - 1
# 처음부터 마지막 index까지 for문을 돌린다. (시작점)
for iter in range(iters):
# 가장 끝 지점에 벽을 세우고 그 벽을 한 칸씩 앞으로 당겨온다고 생각하면 쉽다.
wall = iters - iter
# index 값: 0 ~ wall 바로 앞까지 for문을 돌린다.
for cur in range(wall):
# 최종적으로 가장 큰 값들이 계속 wall의 위치로 가게 된다.
if lst[cur] > lst[cur + 1]:
lst[cur], lst[cur+1] = lst[cur+1], lst[cur]
return lst📔 선택 정렬
버블정렬과 정반대로 for문을 돌 때마다 현재 인덱스의 값보다 오른쪽에 더 작은 값이 있는지 찾고, 그 더 작은 값을 각 반복문 종료 시 가장 왼쪽에 위치시킨다. 하나씩 계속 해서 스왑해가며 반복문을 수행해 나가지는 않는다는 점, 가장 큰 값이 아니라 가장 작은 값을 기준으로 실행한다는 점이 버블 정렬과 다르다고 생각하면 된다.
버블정렬에 비해서는 보다 개선된 정렬 방식이기 때문에 속도는 2배정도 빠르다고 보면 된다. 하지만 여전히 시간복잡도는 O(n^2)이다.
🔤 구현 코드
def selectionsort(lst):
"""
1. 앞에 제일 작은 수를 놔두고 끝까지 반복한다
2. 뒤의 수가 더 작으면 그 값을 minimum으로 한다.
"""
iters = len(lst) - 1
for iter in range(iters):
minimum = iter
for cur in range(iter + 1, len(lst)):
if lst[cur] < lst[minimum]:
minimum = cur
if minimum != iter:
lst[minimum], lst[iter] = lst[iter], lst[minimum]
return lst📔 삽입 정렬
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾고 삽입함으로써 정렬을 완성하는 알고리즘이다. 최선의 경우 O(N)이라는 빠른 시간적 효율성을 가지고 있어 다른 정렬 알고리즘의 일부로 사용되기도 한다. 그 예시로는 Tim Sort가 있다.(부가적인 설명은 아래에 ⬇⬇)
구현 코드
def insertionsort(lst):
# 1번 index부터 시작해서 마지막 index까지 체크한다.
for cur in range(1, len(lst)):
for delta in range(1, cur + 1):
cmp = cur - delta
if lst[cmp] > lst[cmp + 1]:
lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
# 바로 전단계 요소가 더 작다면 바로 for문을 탈출
# 계속 swap 되고 있었다면 예를 들어, 딱 현재 요소보다 작은 요소를 만났을 때 else로 와서 for문 탈출
else:
break
return lst📔 퀵 정렬
분할 정복 알고리즘이며 피벗이라는 개념을 사용해서 피벗보다 작으면 왼쪽, 크면 오른쪽으로 파티셔닝을 하면서 쪼개 나간다. 그 중에서도 항상 맨 오른쪽의 피벗을 택하는 로무토 파티션을 직접 구현해보았다.
참고로 퀵 정렬의 평균 시간복잡도는 O(n * logN)이고 최악은 O(n^2)이다.
🔤 구현 코드
def quicksort(lst, start, end):
def partition(part, ps, pe):
pivot = part[pe] # 제일 오른쪽에 있는 값을 pivot으로 잡는다.
left = ps - 1 # 시작점보다 한칸 전을 가리키고 있다.
for right in range(ps, pe):
if part[right] <= pivot: # 만일 인덱스 right이 pivot 값보다 작으면,
left += 1 # 왼쪽에 공간을 하나 만들어주고
part[left], part[right] = part[right], part[left] # 왼쪽과 오른쪽 값을 서로 스왑한다.
part[left + 1], part[pe] = part[pe], part[left + 1]
return left + 1
if start >= end:
return None
p = partition(lst, start, end)
quicksort(lst, start, p - 1) # 피벗을 기준으로 바로 왼쪽까지
quicksort(lst, p + 1, end) # 피벗을 기준으로 바로 오른쪽부터
return lst🍒 알고나면 더 잘 이해되는 내용
- 퀵소트는 결국 마지막에 피벗을 중간으로 옮길 때 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 피벗보다 큰 값들이 모여있어야 한다. 근데! 여기서 왼쪽 오른쪽의 값들은 오름차순 or 내림차순으로 정렬되어있을 필요가 없다. 그냥 피벗보다 작거나 크기만 하면 되는 것이다.
- left의 값은 그냥 가리키는 것이다. 처음에는 아무 값도 넣지 않았기 때문에 늘 비어있다. 그러다가 pivot보다 작은 index right의 값을 만났을 때, 공간을 하나 만들어주고 (오른쪽으로 한칸 이동, 즉 left += 1) 거기에 right의 값을 넣어주는 것이다. 정리하면 left는 어디에 값을 넣을지 계속 그 자리(위치)를 가리키고 있다고 보면 되고, right은 해당 인덱스에 들어있는 값이 pivot보다 작은지 큰지만 확인하면 된다고 이해하면 아주 쉽다.
📔 병합 정렬
존 폰 노이만이 1945년 고안한 알고리즘이다. 최선과 최악 모두 O(N * logN)인 알고리즘으로 대부분의 경우 퀵 정렬보다 느리지만 일정한 실행속도와 안정정렬이라는 점에서 많은 라이브러리에서 쓰이고 있다. 참고로 파이썬에서 사용하는 정렬함수 sorted()와 list.sort()에 사용된 정렬 알고리즘은 팀소트(Tim Sort)라고 하는데, 이 팀소트는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)을 섞어서 구현된 것이라고 한다.
🔤 구현 코드
def merge(lst1, lst2):
# 빈 배열과 index 값 0에서 시작하는 i, j
arr = []
i = j = 0
while i < len(lst1) and j < len(lst2):
# lst1[i]의 값이 작으면 그 값을 arr에 넣어준다.
if lst1[i] < lst2[j]:
arr.append(lst1[i])
i += 1
else:
arr.append(lst2[j])
j += 1
# lst1 or lst2의 요소가 없어지면 그 뒤로는 the other list의 요소들을 다 arr에 넣어준다.
while i < len(lst1):
arr.append(lst1[i])
i += 1
while j < len(lst2):
arr.append(lst2[j])
j += 1
# merge sort가 끝난 arr를 return 해준다.
return arr
def mergeSort(lst):
if len(lst) <= 1:
return lst
# 리스트 중간을 기준으로 왼쪽/오른쪽의 리스트를 따로 변수에 할당한다.
# 리스트의 길이가 1 이하가 될 때까지 반복한다.
mid = len(lst) // 2
L_sorted = lst[:mid]
R_sorted = lst[mid:]
# 요소들을 다시 하나씩 병합(Merge)하면서 정렬한다.
return merge(mergeSort(L_sorted), mergeSort(R_sorted))
힙정렬
최대힙 혹은 최소힙 트리를 만들어서 정렬을 하는 방법을 말한다. 정렬해야 할 n개의 요소들로 최대힙(완전 이진트리 형태)을 만들고 내림차순으로 정렬하여 한번에 하나의 요소를 힙에서 꺼내 배열에 저장한다.
병합정렬과 다르게 추가적인 메모리가 필요없다는 점에서 굉장히 효율적이고, 시간복잡도가 항상 O(N * logN)를 보장해주기 때문에 매우 강력한 알고리즘으로 볼 수 있다. 하지만 실제로 단순히 속도만 놓고 비교했을 때 퀵정렬이 더 빠른 편이다.
🔤 구현 코드
먼저 최대힙을 구현한다.
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def __len__(self):
# len() 연산을 가능하게 하는 Magic Method
# 덮어쓰기(Override)
return len(self.items) - 1
def _percolate_up(self):
cur = len(self)
parent = cur // 2
while parent > 0:
if self.items[parent] < self.items[cur]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1
if left <= len(self) and self.items[biggest] < self.items[left]:
biggest = left
if right <= len(self) and self.items[biggest] < self.items[right]:
biggest = right
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
def insert(self, k):
self.items.append(k)
self._percolate_up()
def extract(self):
if len(self) < 1:
return None
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root그 다음, 구현된 최대힙의 자료구조를 바탕으로 주어진 리스트를 정렬한다.
def sorted_by_heap(lst):
maxheap = BinaryMaxHeap()
for elem in lst:
maxheap.insert(elem)
desc = [maxheap.extract() for _ in range(len(lst))]
return list(reversed(desc)) # 가장 뒤에 최대값이 위치하도록