1. 거품 정렬 (Bubble Sort)
기본 아이디어
첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해줍니다. 이런 절차를 정렬이 될 때 까지 반복합니다.
시간 복잡도
한 바퀴를 돌 때 마다 데이터가 한 개씩 제자리로 가게 되므로, 최악의 경우 N-1바퀴 배열을 순회합니다.
따라서, O(N^2)이라는 시간복잡도를 갖게 됩니다.
코드
// 일반적인 bubble sort
function bubble_sort(arr[])
set len = arr.size
for i = 0 ... i < len - 1
for j = 0 ... j < len - 1 - i
if arr[j] > arr[j + 1]
set tmp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tmp
return arr// 개선된 bubble sort (중간에 정렬된 상태라면 종료 가능)
function bubble_sort(arr[])
set len = arr.size
set sorted = true
do
sorted = true
for i = 0 ... i < len - 1
if arr[i] > arr[i + 1]
set tmp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = tmp
sorted = false
while(!sorted)
return arr2. 선택 정렬 (Selection Sort)
기본 아이디어
전체 값 중 가장 작은 값을 찾고, 해당 값을 맨 첫번째에 배치합니다. 이후 첫번째 값을 제외하고 가장 작은 값을 찾아 두번째에 배치합니다. 이를 두번째, 세번째, ... n-1번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치합니다.
시간 복잡도
선택 정렬의 경우 반드시 n-1, n-2, ..., 1번의 비교 연산을 수행해야하기 때문에 약 n*(n-1) / 2번의 연산을 필요로 합니다.
따라서, O(N^2)이라는 시간복잡도를 갖게 됩니다.
코드
function selection_sort(arr[])
set size = arr.size
for i = 0 ... i < size - 1
set minimum = i
for k = i+1 ... k < size
if arr[k] < arr[minimum]
minimum = k
set tmp = arr[i]
arr[i] = arr[minimum]
arr[minimum] = tmp
return arr3. 삽입 정렬 (Insertion Sort)
기본 아이디어
앞에서부터 순서대로 보면서, 앞 원소들은 모두 정렬된 상황에서 현재 원소의 위치를 적절하게 집어넣는 정렬입니다. 지금까지 진행한 곳까지의 원소들의 정렬 상태를 유지하며, 정렬된 부분의 크기를 1, 2, ... n개까지 늘려나게 됩니다.
현재 위치에 있는 원소를 앞에 원소와 비교하여, 앞에 있는 원소의 크기가 더 크다면 두 원소의 위치를 바꿔줍니다. 바꾼 이후에도, 앞에 있는 원소와 비교했을 때 앞에 있는 원소의 크기가 더 크면, 또 두 원소의 위치를 바꿔줍니다. 이런 절차를 계속 반복하다 앞에 있는 원소가 더 커지지 않는 경우에 도달한다면, 움직인 것을 멈춥니다.
시간 복잡도
n개의 원소에 대해 값 삽입을 수행해야 하는데, 2번째 원소의 경우엔 최대 1개의 원소를 이동, 3번째 원소의 경우엔 최대 2개의 원소를 이동, n번째 원소까지 삽입하는 경우엔 최대 개의 원소가 이동해야하기 때문에 약 개의 원소가 이동해야 합니다.
따라서, O(N^2)이라는 시간복잡도를 갖게 됩니다.
코드
function insertion_sort(arr[])
set size = arr.size
for i = 1 ... i < size
set j = i - 1
set key = arr[i]
while j>=0 && arr[j] > key
arr[j+1] = arr[j]
j--
arr[j+1] = key
return arr4. 기수 정렬 (Radix Sort)
기본 아이디어
버블 정렬, 선택 정렬, 삽입 정렬과는 다르게, 값을 비교하지 않고 정렬하는 알고리즘입니다.
맨 뒤에 있는 자릿수부터 해당 자리수를 기준으로 정렬한 뒤, 점점 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법입니다. 가장 작은 자리수에서부터 큰 자리수까지 숫자들을 0부터 9까지 숫자 단위로 모아서 적어주는 것을 반복하면 정렬된 결과를 얻을 수 있게 됩니다.
시간 복잡도
각각의 데이터에 대해 매 자릿수마다 분류작업을 하기 때문에 분류작업이 번(자릿수) 반복된다고 볼 수 있습니다.
따라서, 시간복잡도는 으로 는 자릿수를 의미합니다. 만약 k > N 이라면 버블, 선택, 삽입 정렬보다 빠릅니다.
코드
function radix_sort(arr[], k) // k는 자리수
for pos = k-1 ... pos >= 0: // pos는 현재 보고 있는 자리의 위치(맨 뒷자리부터 맨 앞까지 순서대로 보며 정렬)
set arr_new = [10][] // 0 ~ 9까지의 숫자들에 대해 각각 빈 리스트를 만듦
for i = 0 ... i < arr.size
set digit = posth digit of arr[i] // 각 원소의 pos번째 위치에 적혀있는 숫자(0~9)
arr_new[digit].append(arr[i]) // digit 위치에 해당 원소를 추가
set store_arr = []
// arr_new 내의 숫자들을 0 ~ 9번까지 순서대로 순회하며, 각각의 원소를 넣어줌
for i = 0 ... i < 10
for j = 0 ... j < arr_new[i].size
store_arr.append(arr_new[i][j])
arr = store_arr // 나온 결과(store_arr)를 다시 시작(arr)로 하여 그 다음 자릿수에 대해 반복 진행
return arr
예시 문제
n개의 원소가 주어졌을 때, 오름차순으로 정렬
- 1 ≤ 원소의 개수 n ≤ 100,000
- 1 ≤ 원소 값 ≤ 100,000
위와 같이 주어졌을 때는 O(N^2) = 10^10이므로 사용할 수 없습니다. 따라서 O(k*N) 혹은 O(NlogN)인 알고리즘을 사용해야 합니다.
5. 정렬 속도 비교
거품, 선택, 삽입 정렬 알고리즘의 시간복잡도는 O(N^2)라는 공통점이 있지만, 실제 소요되는 시간은 많이 다릅니다.
거품 정렬
일반적으로 셋 중 가장 느립니다. 그러나 정렬된 배열의 경우, 개선된 거품정렬 사용 시 sorted의 값이 계속 true이기 때문에 시간이 매우 빨라집니다.
선택 정렬
배열의 상태와 상관없이, 1번째로 작은 원소를 찾고, 2번째로 작은 원소를 찾고, ... 하는 과정을 거칩니다. 따라서, 어떠한 상황이던 동일한 시간을 보여줍니다.
삽입 정렬
일반적으로는 가장 빠르나, 값이 반대로 정렬되어 있는 경우 성능이 많이 떨어진다는 단점이 있습니다. 이미 정렬된 배열에 추가적으로 값을 몇개 추가하여 정렬하는 경우에 좋은 성능을 보여줍니다.
6. 병합 정렬 (Merge Sort)
기본 아이디어
분할정복 이용!! (배열의 길이가 1개가 될 때 까지 재귀적으로 두개의 배열로 쪼개기 → 쪼갠 배열을 합쳐가며 정렬된 배열로 만들기)
- 배열 쪼개기 (분할)
- 길이가 N짜리인 배열을 N/2 길이의 배열 두개로 나눕니다. 이후 길이가 N/2짜리인 배열을 N/4 길이의 배열 두개로 나눕니다. ... 이렇게 배열의 길이를 줄여나가게 되면 언젠가는 길이가 1이 됩니다. 이 길이가 1인 배열은 정렬된 배열이라고 할 수 있습니다.
- 배열 합치기 (병합)
- 정렬된 두 배열이 있을 때, 두개의 배열의 처음부터 시작하여, 두개의 값 중 더 작은 값을 배열에 넣고, 다시 남은 값을 비교하는 방식으로 채워나갑니다.
- 길이가 1짜리인 두개의 배열을 합쳐 정렬된 길이가 2인 배열로 만듭니다. 이후 길이가 2짜리인 두개의 배열을 합쳐 정렬된 길이가 4인 배열로 만듭니다. ... 이렇게 배열의 길이를 늘려나가게 되면 언젠가는 길이가 N이 됩니다.
시간 복잡도
분할하는 과정에서는 별다른 비교연산이나 이동연산이 수행되지 않습니다. 따라서, 분할된 결과들이 합병되는 과정에서의 비교, 이동 횟수를 살펴보면됩니다.
각 병합 단계마다 O(N) 시간이 소요되고(각 단계에서 각 원소는 한 번만 비교 및 이동을 하기 때문), 이러한 병합 단계는 logN번 반복됩니다. 따라서 시간복잡도는 O(NlogN)이 됩니다.
단점
정렬된 결과를 저장하기 위한 추가적인 공간이 필요합니다. (아래의 merged_arr)
코드
// arr 리스트 내의 원소들 중 low번째 원소부터 high번째 원소까지 정렬
function merge_sort(arr[], low, high)
if low < high // 원소의 개수가 2개 이상인 경우에만 진행
set mid = (low + high) / 2 // 가운데 원소의 위치
merge_sort(arr, low, mid) // 왼쪽 부분에 대해 병합정렬 진행
merge_sort(arr, mid+1, high) // 우측 부분에 대해 병합정렬 진행
merge(arr, low, mid, high) // 정렬된 두 리스트를 하나로 병합
set merged_arr = [] // 병합 이후의 결과를 담아줍니다.
// 정렬된 다음 두 구간 [low, mid], [mid+1, high] 내의 리스트에 대해 합치는 작업
function merge(arr[], low, mid, high)
set i = low, j = mid + 1 // 각 리스트 내(i:왼쪽, j:오른쪽)의 원소 위치를 잡습니다.
set k = low // 병합 시 원소를 담을 위치를 유지합니다.
while i <= mid && j <= high // 두 리스트 내의 원소가 아직 남아있다면
if arr[i] <= arr[j] // 첫 번째 리스트 내의 원소가 더 작다면
merged_arr[k] = arr[i] // 해당 원소를 옮겨줍니다.
k += 1; i += 1
else
merged_arr[k] = arr[j] // 그렇지 않다면 두 번째 리스트 내의
k += 1; j += 1 // 원소를 옮겨줍니다.
while i <= mid // 아직 첫 번째 리스트 내 원소가 남아있다면
merged_arr[k] = arr[i] // 남은 원소들을 전부 옮겨줍니다.
k += 1; i += 1
while j <= high // 아직 두 번째 리스트 내 원소가 남아있다면
merged_arr[k] = arr[j] // 남은 원소들을 전부 옮겨줍니다.
k += 1; j += 1
for k = low ... k <= high // 병합된 리스트를 다시
arr[k] = merged_arr[k] // 원본 리스트에 옮겨줍니다.
return arr7. 퀵 정렬 (Quick Sort)
기본 아이디어
분할정복 이용!! (서브리스트의 크기가 1이 될 때까지 재귀적으로 피벗 값을 기준으로 그 값 이상과 미만인 두 부분으로 나누기)
- 기준점(피벗 : pivot) 잡기
- 일반적으로는 맨 왼쪽 값 / 맨 오른쪽 값 / 가운데 값 중에 선택합니다.
- 피벗을 무엇으로 잡느냐에 따라 퀵 정렬의 성능이 결정됩니다.
- 배열을 피벗 값 기준 나누기
- 피벗 값을 기준으로 왼쪽(그 값 미만), 오른쪽(그 값 이상) 2개의 서브리스트로 분류합니다. 이렇게 나뉘어진 두개의 서브리스트에 대해 마찬가지로 앞에서 했던 로직을 반복합니다. 만약 서브리스트의 크기가 1이여서 더이상 분할할 수 없다면, 해당 서브리스트는 정렬된 상태라고 할 수 있습니다.
시간 복잡도
N개의 값이 있을 때, 이 값들을 특정 값 이상, 미만으로 분류하는데는 O(N)이 소요됩니다. 또한 분할은 평균적으로 logN회 수행됩니다. 따라서 평균 시간복잡도는 O(NlogN)이 됩니다. 일반적인 상황에서 퀵 정렬은 다른 정렬들보다 월등히 빠릅니다.
단점
최악의 경우(피벗을 잘못 고르게 되면)에는 분할이 N번 수행되어, 시간복잡도가 O(N^2)이 됩니다.
이를 해결하기 위해 개선된 피벗을 선택할 수 있습니다.
- 데이터가 3개 이하면 피벗은 반드시 마지막 값
- 데이터가 4개 이상이면 맨 왼쪽, 오른쪽, 가운데 (나머지 버림) 값 중 중간 값을 선택\
- 피벗이 선택되면 먼저 구간의 맨 끝 원소와 꼭 교환해야함
코드
파란색 화살표를 설정하여 이 화살표는 pivot보다 같거나 큰 원소를 계속 가리키게 합니다.
빨간색 화살표의 경우 모든 원소들을 순회하며, 해당 원소가 pivot보다 작은 순간에 파란색 화살표 그 다음 위치에 있는 원소와 교환해준 뒤, 파란색 화살표를 한칸 뒤로 옮겨줍니다. 이를 계속 반복하다가 최종적으로 빨간색 화살표가 끝에 도달하는 순간, 파란색 화살표가 있는 위치 바로 오른쪽에 있는 원소와 pivot을 바꿔줍니다.
// 특정 pivot 값을 기준으로 왼쪽(해당 값 미만)과 오른쪽(해당 값 이상)으로 분할
function partition(arr[], low, high)
set pivot = select_pivot(arr, low, high) // pivot을 고릅니다.
set i = low - 1 // 파란색 화살표 위치를 정해줍니다.
// 파란색 화살표는 pivot보다 같거나 큰 원소를 가리킵니다.
for j = low ... j <= high - 1 // 빨간색 화살표를 움직입니다.
if arr[j] < pivot // 빨간색 화살표가 가리키는 원소가 pivot보다 작다면,
i += 1
swap (arr[i], arr[j]) // 왼쪽으로 가야하므로, 두 원소의 위치를 바꿔줍니다.
swap (arr[i + 1], arr[high]) // 최종적으로 pivot을 경계에 있는 원소와 교환해줍니다.
// 이때 경계는 마지막 파란색 화살표 위치에 1을 더한 위치입니다.
return i + 1 // pivot의 최종 위치를 반환해줍니다.
// arr 리스트 내의 원소들 중 low번째 원소부터 high번째 원소까지 정렬
function quick_sort(arr[], low, high)
if low < high // 원소의 개수가 2개 이상인 경우에만 진행
pos = partition(arr, low, high) // pivot 기준으로 좌우로 분할 한 후
// 해당 pivot의 위치를 pos에 넣어줍니다.
quick_sort(arr, low, pos - 1) // pivot의 왼쪽 구간에 있는 원소들을 정렬합니다.
quick_sort(arr, pos + 1, high) // pivot의 오른쪽 구간에 있는 원소들을 정렬합니다.
새로운 배열을 만들지 않고, 빨간색 및 파란색 화살표를 쓰는 이유는 In-Place하게 하기 위함입니다.
8. 힙 정렬 (Heap Sort)
트리와 이진트리 개념
- 노드: 각 지점을 의미합니다.
- 루트 노드: 트리에서 맨 꼭기를 의미합니다.
- 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부릅니다.
- 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미합니다.
- 깊이: 루트 노드와 얼마나 떨어져 있는지를 가리키는 말입니다.
- 높이: 트리에서 깊이가 가장 깊은 노드의 깊이를 의미합니다.
- 리프 노드: 자식을 갖고 있지 않은 노드를 의미합니다.
이진 트리란, 모든 노드에 자식이 최대 2개씩만 있는 트리를 말합니다. 이진트리는 배열로 구현이 가능(루트 노드 1부터 시작)하며, 특정 노드의 위치가 i라고 하면, 왼쪽 자식의 위치는 i*2, 오른쪽 자식의 위치는 i*2+1이 됩니다.
Max-Heap의 개념과 생성 과정
Max-Heap은 모든 노드에 대해 부모 노드 ≥ 자신의 자식 노드 값을 만족하는 완전이진트리(왼쪽으로 가득 채워짐)이며, 루트 노드에는 항상 전체 숫자 중 최댓값이 들어있는 자료구조입니다.
n/2 번째 원소부터 거꾸로 1번째 원소까지 순서대로 보면서 heapify 과정을 거칩니다. heapify란 현재 노드를 기준으로 이 노드가 heap 특성에 맞을 때까지 계속 밑으로 내려주는 과정을 말합니다.
- 현재 노드 위치를 i라고 한다면, 현재 노드, 왼쪽 자식(i * 2번째) 노드, 그리고 오른쪽 자식(i * 2 + 1번째) 노드 중 가장 큰 노드가 무엇인지 판단합니다. 이 세 노드 중 가장 큰 노드를 편의상 largest 노드라고 하겠습니다.
- 만약 largest 노드가 현재 노드 i가 아닌 자식 노드라면, 현재 노드(i)와 해당 자식 노드(largest)의 값을 교환합니다. 교환 이후에는 다시 largest 위치에서 heapify를 진행합니다. 이렇듯 현재 노드가 heap 조건을 만족하도록 계속 내려주는 것을 재귀적으로 반복해줍니다.
- 만약 현재 노드 i의 자식 노드가 없거나 largest 노드가 현재 노드 i라면, 종료합니다.
기본 아이디어
처음 Max-Heap을 구성한 뒤, 최댓값(루드 노드)을 마지막 원소(n번 노드)와 교환하고 남은 원소 n-1개로 다시 heapify(1)을 통해 Max-Heap을 만드는 과정을 남은 원소가 1개가 될때까지 반복합니다.
- 처음 Max-Heap을 구성합니다.
- 루트 노드(1번)와 배열의 마지막 노드(n번)를 교환하여, 최댓값을 배열의 맨 뒤로 보냅니다. (n번째 노드 값 확정)
- 남은 원소 n-1개로 다시 max-heap을 만듭니다. 이때 앞의 교환에 의해 max-heap이 깨졌으므로, heapify(1)을 통해 다시 max-heap을 만족하도록 만듭니다.
- n이 1이 될때까지, 그 다음 최댓값을 찾는 과정(2~3)을 재귀적으로 반복합니다.
시간 복잡도
처음 max-heap을 만들 때 총 n/2개의 원소에 대해 heapify 과정을 거치게되며, 엄밀히 계산했을 때 시간은 O(N)이 소요됩니다.
max-heap을 구성한 이후 Heapify 과정은 한 번 일어날 때 최대 트리의 높이인 logN번 수행됩니다.
또한, 최댓값(루트 노드)을 마지막 원소(n번 노드)와 교환하고 다시 heapify를 진행하는 것을 n번 반복하게 되므로, N개의 원소를 정렬하는 데 걸리는 시간은 O(NlogN)입니다.
코드
// i번째 노드가 max-heap 조건을 만족하도록,
// 자식 노드와 비교하여 더 큰 노드가 현재 노드가 아니라면 계속 밑으로 내려가 주는 함수
function heapify(arr[], n, i)
set largest = i // 최대 노드가 i번이라고 가정합니다.
set l = i * 2 // 왼쪽 자식 노드 번호입니다.
set r = i * 2 + 1 // 오른쪽 자식 노드 번호입니다.
if l <= n && arr[l] > arr[largest] // 왼쪽 자식이 크다면, 최대 번호를 수정합니다.
largest = l
if r <= n && arr[r] > arr[largest] // 오른쪽 자식이 크다면, 최대 번호를 수정합니다.
largest = r
if largest != i // 최대 노드가 자식 노드라면
swap(arr[i], arr[largest]) // 해당 자식과 현재 노드를 교환해준 뒤
heapify(arr, n, largest) // 내려간 위치에서 다시 heapify를 진행합니다.
function heap_sort(arr[], n)
// 1. 처음 max-heap을 만들어 줍니다.
for i = n / 2 ... i >= 1 // n / 2번째 원소부터 1번째 원소까지 돌며
heapify(arr, n, i) // heapify 과정을 진행하여 max-heap을 만들어줍니다.
// 2. 정렬을 진행합니다.
for i = n ... i > 1 // n을 하나씩 줄여나가며
swap(arr[1], arr[i]) // 현재 최댓값(1번 노드)과 가장 끝에 있는 노드를 교환해주고
heapify(arr, i - 1, 1) // 1번 노드를 기준으로 heapify를 진행하여 max-heap 상태를 계속 유지해줍니다.9. Stable Sort
만약 같은 값을 넣어 정렬을 했을 때, 먼저 들어간 값이 반드시 앞쪽에 있음이 보장된다면(원래의 순서를 유지), 이런 정렬을 "Stable"하다고 합니다.
- Stable한 알고리즘 : 거품 정렬, 삽입 정렬, 병합 정렬, 기수 정렬
- Unstable한 알고리즘 : 선택 정렬, 퀵 정렬, 힙 정렬
- 선택 정렬 : 최소값을 선택하고 교환하는 과정에서, 앞에 있는 값이 갑자기 맨 뒤로 이동할 수 있습니다.
- 퀵 정렬 : 동일한 값 중 하나의 값이 피벗으로 설정된다면, 순서가 뒤집힐 수 있습니다.
- 힙 정렬 : 최댓값(루트)과 마지막 노드를 교환하는 과정에서, 같은 값 사이에 순서가 뒤바뀔 수 있습니다.
이러한 특성을 고려하여, 안정성이 필요한 경우에는 Stable한 알고리즘을, 안정성이 불필요하고 성능이 중요한 경우에는 효율적인 정렬 알고리즘을 선택하면 됩니다.
10. In-Place Sort
추가적인 메모리 사용 없이 정렬이 가능한 경우 "In-Place"라 할 수 있습니다.
- In-Place한 알고리즘 : 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬
- In-Place하지 않은 알고리즘 : 기수 정렬, 병합 정렬
- 기수 정렬 : 각 자릿수에 대해 정렬을 수행할 때 추가적인 메모리(0 ~ 9까지의 숫자들에 대한 각각의 리스트)가 필요합니다.
- 병합 정렬 : 정렬된 두 배열을 합치기 위해 새로운 배열(merged_arr)이 필요합니다.
이러한 특성을 고려하여, 메모리 사용을 최소화해야 하는 경우에는 In-Place Sort 알고리즘을 선택하면 됩니다.
'Data Structure & Algorithm > 알고리즘(Algorithm)' 카테고리의 다른 글
| 04. 이진탐색 (0) | 2024.06.18 |
|---|---|
| 02. 배열, 연결 리스트 (0) | 2024.06.10 |
| 그래프 문제 및 최단경로 문제 (2) | 2023.12.18 |