🌏 Sorting 정렬
정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.
정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘이며 코딩테스트에서도 자주 출제되는 알고리즘 중 하나이기 때문에 확실하게 정리하고 넘어가보자!
👽 Bubble Sort 거품 정렬
정렬의 과정에서 데이터의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이라 한다고 함!
서로 인접한 두 데이터의 크기를 비교하여 데이터의 위치를 바꾸는 과정을 반복하는 알고리즘
def bubbleSort():
for i in range(len(arr)):
for j in rnage(len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
👽 Selection Sort 선택 정렬
데이터가 무작위로 여러개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것 ➡️ 다시말해, 매번 가장 작은 데이터값을 선택한다!
def selectionSort():
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]
👽 Insertion Sort 삽입 정렬
특정한 데이터를 적절한 위치에 삽입하는 알고리즘 ➡️ 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하며. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 그 위치에 데이터를 삽입한다!
def insertionSort():
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
👽 Quick Sort 퀵 정렬
퀵 정렬은 가장 많이 사용되는 정렬 알고리즘으로, 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
- 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
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)
👽 Merge Sort 병합 정렬 / 합병 정렬
병합 정렬은 데이터를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식 ➡️ 쪼개는 방식은 퀵정렬과 유사하다!
- 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다.
- 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * (n1)
R = [0] * (n2)
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = l + (r - l) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
mergeSort(arr, 0, len(arr) - 1)
👽 Heap Sort 힙 정렬
- n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
- 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 2와 3을 반복한다.
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
(arr[i], arr[largest]) = (arr[largest], arr[i])
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
heapSort(arr)
👽 Radix Sort 기수정렬
기수 정렬은 자릿수 별로 비교 없이 수행하는 정렬 알고리즘
➡️ 비교 연산을 하지 않기 때문에 정렬 속도가 빠르지만 기수 테이블의 크기만한 메모리가 더 필요하다는 단점이 있다! ➡️ 또한 각 자릿수를 이용하여 정렬을 수행하기 때문에 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다!
def countingSort(arr, exp1):
n = len(arr)
output = [0] * (n)
count = [0] * (10)
for i in range(0, n):
index = arr[i] // exp1
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp1
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
i = 0
for i in range(0, len(arr)):
arr[i] = output[i]
def radixSort(arr):
max1 = max(arr)
exp = 1
while max1 / exp >= 1:
countingSort(arr, exp)
exp *= 10
radixSort(arr)
👽 Counting Sort 계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘. ➡️ 배열의 데이터 개수가 배열 내의 최대 값의 길이보다 작을때 매우 유용한 알고리즘!
def countSort(arr):
output = [0 for i in range(len(arr))]
count = [0 for i in range(256)]
for i in arr:
count[ord(i)] += 1
for i in range(256):
count[i] += count[i-1]
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
return output
💫 알고리즘 별 시간복잡도 및 공간복잡도
정렬 알고리즘 | 시간복잡도 | 공간복잡도 | |
Bubble Sort | O(n^2) | O(1) | |
Selection Sort | O(n^2) | O(1) | |
Insertion Sort | O(n^2) | O(1) | |
Quick Sort | O(nlogn) | O(logn) | |
Merge Sort | O(nlogn) | O(n) | |
Heap Sort | O(nlogn) | O(1) | |
Radix Sort | O(nk) | O(n+k) | k는 최대 자릿수 |
Counting Sort | O(n+k) | O(k) | k는 배열 내 최댓값의 길이 |
'📓STUDY > 알고리즘' 카테고리의 다른 글
이진 탐색 | Binary Search (1) | 2023.06.06 |
---|---|
[python | 파이썬] Greedy Algorithm | 그리디 알고리즘 (1) | 2023.04.25 |
Deque(데크)란 무엇일까 | 파이썬 자료구조 큐(Queue) (0) | 2023.04.17 |
[python] Stack과 Queue (0) | 2023.04.05 |