먼저! 하나하나 알아보기에 앞서서 알면 좋은 '배열'과 '정렬'
세상 속 복잡한 문제들을 풀기 위해서 프로그래밍 언어들은 다양한 자료구조들을 사용하고 있다. 그 중에서 '자료구조'하면 가장 먼저 배우게 되는 '배열'을 다루는 정렬 알고리즘에 대해 알아보려고 한다. 정렬 알고리즘은 왜 필요할까? 이는 곧 배열을 왜 사용하냐는 질문에 같은 답변을 줄 수 있을 것이다. 배열은 필요한 요소를 인덱스를 통해 찾기 위해 사용한다. 그렇다면 자료구조 배열을 사용할 때 가장 중요한 것은 필요한 요소의 인덱스를 바로 찾아내는 것이며, 당연하게도 뒤죽박죽 엉켜있는 배열보다는 특정 기준에 맞춰서 정렬되어있는 배열을 만들어놓는다면 이를 사용하기에는 훨씬 더 편할 것이다.
그렇다면 앞으로 알아볼 정렬 알고리즘은 '왜' 여러 개나 있을까? 배열의 정렬에 가장 최적인 알고리즘 1개만 있을 수는 없는 걸까? 이때 우리는 배열에 다시 집중해 볼 필요가 있다. 배열에 들어갈 데이터는 정말 다양할 것이다. 단순하게 데이터의 양이 많을 수도, 적을 수도 있고, 이미 정렬된 정도가 다 달라서 부분별로 정렬되었거나 아예 정렬되지 않은 데이터가 있을 수 있고 혹은 이미 정렬된 형태의 데이터들이 있을 수 있다. 또한 데이터를 정렬하여 사용할 목적 또한 다를 것이다. 복잡한 현실 세계를 다루는 데이터인 만큼 그 종류나 형태, 특징, 정렬의 목적이 다 다르기에 이에 알맞은 정렬 알고리즘을 사용해야 한다. 이번에 볼 정렬 알고리즘은 총 6개이며 낱낱이 파헤쳐보기 전에 먼저 데이터의 특성과 목적에 따라 선택할 수 있는 정렬 알고리즘을 보고가 보자. 각자 어떤 과정을 거쳐 정렬을 하는지 알기 전에 각 정렬 방법의 대략적인 특징에 대해 알아볼 수 있다.
1. 데이터 크기
- 데이터가 많다면? 시간 복잡도가 낮은 알고리즘(ex. 병합 정렬, 퀵 정렬)이 적합하다.
- 데이터가 적다면? 단순한 알고리즘(ex. 선택 정렬, 삽입 정렬)이 효율적일 것이다.
2. 정렬된 정도
- 대부분 정렬되어있는 형태? 삽입 정렬이 효율적이다.
- 정렬되어있지 않은 형태? 퀵 정렬이 효율적이다.
3. 정렬의 목적
- 기본 정렬 : O(n²)
- 삽입 정렬 : 이미 정렬된 데이터에 새로운 데이터를 삽입할 때 최적화되어있다.
- 고급 정렬 : O(nlogn)
- 병합 정렬 : 대규모 데이터를 안정적으로 다룰 수 있을 때 적합하다.
- 힙 정렬 : 메모리를 절약하고 효율적으로 정렬하기에 대규모 데이터에 적합하다.
- 특수 목적 정렬
- 계수 정렬 : 제한적인 데이터 값의 범위를 다룰 때 효율적이다.
- 위상 정렬 : 이미 순서가 정해져있는 작업의 차례를 다룰 때 최적화되어있다.
정렬 알고리즘을 뿌셔보자!!!!!!
기본 정렬 알고리즘 : 시간 복잡도 O(n²)
1. 선택 정렬
- 제자리 정렬 알고리즘 : 공간 복잡도 (O(1))
선택된 값과 나머지 데이터를 모두 비교하여 가장 낮은 값을 고르는 방법이다. 맨 처음에 모든 값들 중에서 가장 낮은 값을 골라 1번으로 옮기고, 이를 제외한 값들 중 가장 낮은 값을 골라 2번으로 옮기고, 남은 값들 중에서 가장 낮은 값을 골라 3번으로 옮기고... 이렇게 모든 값을 정렬할 때까지 과정이 진행된다. 구현이나 방법은 단순하지만 비효율적이기에 데이터의 양이 적을 때 유리하다.
function selectionSort(arr) {
const n = arr.length;
// 배열의 모든 요소를 순회
for (let i = 0; i < n - 1; i++) {
let minIndex = i; // 현재 위치를 최소값의 인덱스로 설정
// 현재 위치 이후의 요소들 중 최소값 찾기
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 더 작은 값을 발견하면 최소값 인덱스 갱신
}
}
// 최소값을 현재 위치로 교환
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 구조 분해 할당
}
}
return arr; // 정렬된 배열 반환
}
// 사용 예시
const array = [64, 25, 12, 22, 11];
console.log("정렬 전:", array);
const sortedArray = selectionSort(array);
console.log("정렬 후:", sortedArray);
이중 for문을 사용하는 구조이기에 최선, 평균, 최악의 시간 복잡도 모두 O(n²)이다.
2. 삽입 정렬
- 제자리 정렬 알고리즘 : 공간 복잡도 (O(1))
정렬되어있지 않은 곳들 중에서 가장 첫번째 값만 뽑아내어서 정렬된 부분들 중 가장 적당한 곳에 삽입하는 방법이다. 맨 처음에 가장 첫 요소는 정렬되어있다고 확정짓고, 그 다음 두 번째 요소부터 뽑아서 정렬되어있는 부분들과 비교한다. 뽑아낸 현재 요소보다 큰 값들을 오른쪽으로 이동시키며 적당한 위치를 찾으면 그 곳에 삽입한다. 선택 정렬과 같이 구현이 간단하고, 데이터가 거의 정렬되어 있는 경우에 사용하면 효율적이다.
function insertionSort(arr) {
const n = arr.length;
// 배열의 두 번째 요소부터 시작
for (let i = 1; i < n; i++) {
let current = arr[i]; // 현재 삽입할 값
let j = i - 1;
// 현재 값보다 큰 값들을 오른쪽으로 이동
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
// 적절한 위치에 현재 값을 삽입
arr[j + 1] = current;
}
return arr; // 정렬된 배열 반환
}
// 사용 예시
const array = [7, 2, 4, 8, 3];
console.log("정렬 전:", array);
const sortedArray = insertionSort(array);
console.log("정렬 후:", sortedArray);
오른쪽으로 이동하는 while문이 얼마나 사용되냐가 관건이다. 즉, 정렬하고자하는 배열의 초기 상태가 얼마나 정렬되어있느냐에 따라 달라진다. [7, 2, 4, 8, 3]의 경우, [2, 3, 4, 7, 8]로 이미 정렬이 되어있다면 이는 곧 최선의 경우이므로 O(n)의 시간 복잡도를 가지고, 반대로 [8, 7, 4, 3, 2]로 정렬이 역순으로 되어있다면 비교할 때마다 모든 값들을 오른쪽으로 넘겨야하기때문에 최악의 경우이므로 O(n²)이다
3. 버블 정렬
- 제자리 정렬 알고리즘 : 공간 복잡도 (O(1))
인접한 두 요소를 비교하면서 순서가 맞지 않다면 서로 교환하는 방법이다. 이 과정이 반복되면서 가장 큰 값이 배열의 끝으로 이동하게 되며, 이러한 과정이 물 속의 거품이 위로 올라오는 모습과 비슷하여 '버블 정렬'이라는 이름으로 불리게 되었다. 맨 처음부터 끝까지 근접한 두 인덱스를 비교하며 가장 큰 값이 오른쪽으로 오도록 하는 과정을 거친다. 어느정도 정렬이 되어있는 상태에 사용하는 것이 가장 좋으며, 무작위로 섞여 있거나 데이터가 많지 않을 때 사용하는 것은 매우 비효율적이다.
다음 코드는 최적화된 버블 정렬의 코드인데, 한 번의 반복동안 교환이 발생하지 않았으면 이는 곧 정렬된 상태임을 이용하여 불필요한 반복을 줄이는 코드이다.
function optimizedBubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false; // 교환 여부 플래그
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true; // 교환 발생 시 플래그 설정
}
}
// 한 번의 반복에서 교환이 없으면 종료
if (!swapped) break;
}
return arr;
}
// 사용 예시
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", array);
const sortedArray = optimizedBubbleSort(array);
console.log("정렬 후:", sortedArray);
선택 정렬과 마찬가지로 이중 for문을 사용하기에 평균과 최악의 경우에 모두 O(n²)의 시간 복잡도를 가지지만, 이미 정렬이 되어있는 최선의 경우에는 O(n)의 시간 복잡도를 보인다. 위 코드처럼 첫 번째 반복문에서 교환이 일어나지 않을 경우 더 이상 반복을 진행하지 않기 때문에 이는 곧 for문을 한 번만 사용한 것과 같은 성능을 보인다.
고급 정렬 알고리즘 : 시간 복잡도 O(nlogn)
4. 병합 정렬
정렬하고자 하는 배열을 둘 이상의 부분집합으로 나누고(divide), 정렬하면서 합치는(conquer) 방법이다. 이는 분할 정복(divide and conquer)라고도 부른다. 해결하려는 문제를 작은 크기의 문제들로 분할하고, 각각의 작은 문제들을 해결하면서, 작은 문제들의 해(결과)를 병합하며 원래 문제를 푸는 방식을 사용한다. 작은 범위로 나누는 과정을 사용하기에 대규모 데이터를 다룰 때 효율적이고 외부에서 가져오지만 메모리에 모두 로드할 수 없는 데이터를 처리할 때 많이 사용한다.
function mergeSort(arr) {
// 배열의 길이가 1 이하이면 이미 정렬된 상태
if (arr.length <= 1) {
return arr;
}
// 배열을 중간 기준으로 분할
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// 재귀적으로 좌우 부분 배열 정렬 후 병합
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// 두 배열을 비교하여 작은 값을 결과 배열에 추가
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 남은 요소들을 결과 배열에 추가
return result.concat(left.slice(i)).concat(right.slice(j));
}
// 사용 예시
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("정렬 전:", array);
const sortedArray = mergeSort(array);
console.log("정렬 후:", sortedArray);
원래 문제를 나누면서 추가 메모리가 필요하고, 데이터 하나의 크기까지 나누므로 O(n)의 공간 복잡도를 가진다. 분할 단계에서 O(logn), 병합 단계에서 O(n)의 시간이 걸리기 때문에 최선, 평균, 최악의 경우 모두 O(nlogn)의 시간 복잡도를 보여준다. 즉, 데이터 분포도의 영향을 받지 않는다.
5. 퀵 정렬
- 제자리 정렬 알고리즘 : 공간 복잡도 (O(log n))
임의의 기준(pivot)을 정하여 해당 피벗을 기준으로 집합을 두 개의 부분 집합으로 나누는 방법이다. 한 쪽에는 피벗보다 작은 값들을, 다른 한 쪽에는 큰 값들만 넣는다. 이 과정에서 추가 메모리는 필요하지 않기때문에 그림에서 볼 수 있다싶이 제자리에서 정렬이 이뤄진다. 더불어 재귀 호출을 통해 재귀 호출 스택을 사용하기 때문에 O(1)이 아닌 O(log n)의 공간 복잡도를 보여준다. 병합 정렬과 같이 분할 정복(divide and conquer)을 사용한다. 하지만 병합 정렬과 다른 점이 있다면 병합 정렬은 무조건 반으로 균등하게 분할하는 반면에 퀵 정렬은 피벗 선택에 따라 분할이 균등하게 이뤄지지 않을 수도 있다. 따라서 퀵 정렬은 병합 정렬에 비해 데이터 분포도의 영향을 받는다. 오히려 데이터가 이미 정렬되어있는 경우에서는 성능이 저하될 수도 있다. 그럼에도 평균적으로 병합 정렬보다 빠르고, 메모리 사용량이 적다는 장점이 있다.
보다 더 쉽게 이해하기 위해 과정을 나열해보자면 다음과 같다.
1. 피벗 선택 : 배열에서 기준이 되는 요소인 pivot을 선택한다.
2. 분할 : 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동시켜서 두 개의 하위 배열로 나눈다.
3. 재귀 호출 : 분할된 해위 배열에 대해 퀵 정렬을 재귀적으로 호출하여 실행한다.
4. 병합 : 하위 배열이 모두 정렬되면 이를 합쳐서 최종적으로 정렬된 배열을 만든다.
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left < right) {
// 피벗을 기준으로 분할
const pivotIndex = partition(arr, left, right);
// 왼쪽과 오른쪽 부분 배열에 대해 재귀 호출
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right]; // 마지막 요소를 피벗으로 선택
let i = left - 1;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // 스왑
}
}
// 피벗을 올바른 위치로 이동
[arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
return i + 1;
}
// 사용 예시
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("정렬 전:", array);
const sortedArray = quickSortInPlace(array);
console.log("정렬 후:", sortedArray);
가장 실용적으로 널리 사용되는 알고리즘 중 하나이며, 병합 정렬과 같이 대규모 데이터에서 효율적으로 동작하지만 피벗 선택에서 최적화 기법이 필요할 수도 있다. 어떤 피벗이 선택되는지와 데이터 분포도에 따라 그 성능이 달라지지만 평균적으로는 O(nlogn)으로 매우 빠른 속도를 보여준다. 하지만 피벗 선택이 적절치않을 경우 모든 데이터에 대해 정렬이 매번 이뤄지는 O(n²)의 시간 복잡도를 가진다.
6. 힙 정렬
- 제자리 정렬 알고리즘 : 공간 복잡도 (O(1))
이름에서 알수있다싶이 힙을 사용하는 방법이다. 힙은 완전 이진 트리의 일종이며, 부모 노드가 자식 노드보다 크거나(최대 힙) 작도록(최소 힙) 유지되는 자료구조이다. 정렬하고자 하는 배열을 최대 힙이나 최소 힙으로 변환한 후 루트 노드(최댓값 혹은 최솟값)을 배열의 끝으로 이동시킨 뒤 배열의 크기를 줄이고 남은 요소들로 다시 힙을 구성하는 과정을 반복하며 정렬하는 과정을 거친다.
다음 코드는 최대 힙으로 변환하여 루트 노드를 최댓값으로 설정하며 정렬하는 방식을 사용하였다.
function heapSort(arr) {
const n = arr.length;
// 1. 배열을 최대 힙으로 변환
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 하나씩 요소를 추출하여 정렬
for (let i = n - 1; i > 0; i--) {
// 루트 노드와 마지막 노드를 교환
[arr[0], arr[i]] = [arr[i], arr[0]];
// 교환 후 남은 요소들로 최대 힙 재구성
heapify(arr, i, 0);
}
return arr;
}
// 힙 구성 함수
function heapify(arr, size, root) {
let largest = root; // 루트를 가장 큰 값으로 설정
const left = 2 * root + 1; // 왼쪽 자식 노드
const right = 2 * root + 2; // 오른쪽 자식 노드
// 왼쪽 자식이 루트보다 크면 largest 갱신
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 largest보다 크면 largest 갱신
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
// largest가 루트가 아니면 교환하고 재귀적으로 호출
if (largest !== root) {
[arr[root], arr[largest]] = [arr[largest], arr[root]];
heapify(arr, size, largest);
}
}
// 사용 예시
const array = [12, 11, 13, 5, 6, 7];
console.log("정렬 전:", array);
const sortedArray = heapSort(array);
console.log("정렬 후:", sortedArray);
특수 목적 정렬 알고리즘 : 시간 복잡도 O(nlogn)
7. 위상 정렬
8. 계수 정렬
정렬 알고리즘 누가누가 잘하나?
밑에 정리된 비교와 함께 위에 보았던 각 정렬 알고리즘의 대략적인 특징들을 한 번 더 본다면, 어떨 때 어떤 정렬 알고리즘을 사용하면 좋을 지 그 감이 잡힐 것이다.
시간 복잡도를 기준으로...
퀵 정렬 (최선) >= 병합 정렬 = 힙 정렬 (O(nlogn))
> 삽입 정렬(최선) = 버블 정렬(최선) (O(n))
> 퀵 정렬 (최악) = 삽입 정렬(최악) = 버블 정렬(최악) = 선택 정렬 (O(n²))
기본 정렬보다 고급 정렬 알고리즘의 시간 복잡도가 빠르며, 그 중 퀵 정렬의 최선의 경우에는 병합 정렬, 힙 정렬보다 빠른 시간 복잡도를 보여주지만 최악의 경우에는 기본 정렬 알고리즘들의 최악의 시간 복잡도와 같은 값을 가진다.
공간 복잡도를 기준으로...
선택 정렬 = 삽입 정렬 = 버블 정렬 = 힙 정렬 (O(1))
> 퀵 정렬 (최선, O(log n))
> 병합 정렬 (O(n)) = 퀵 정렬 (최악, O(n))
제자리 정렬을 사용하는 알고리즘 중 재귀 호출 스택을 사용하는 퀵 정렬은 최선의 경우 O(log n), 최악의 경우 O(n)의 공간 복잡도를 가진다. 제자리 정렬을 사용하는 다른 알고리즘은 모두 O(1)의 공간 복잡도가 필요하며, 병합 정렬은 분할 하는 과정에서 추가 메모리가 필요하므로 O(n)의 공간 복잡도를 가진다.
데이터 특징을 기준으로...
이미 정렬된 데이터?
효율 : 버블 정렬(한 번의 순회), 삽입 정렬(한 번의 순회)
비효율 : 선택 정렬, 퀵 정렬
영향 X : 병합 정렬, 힙 정렬
대규모/소규모 데이터?
대규모 : 병합 정렬, 퀵 정렬, 힙 정렬
소규모 : 선택 정렬, 삽입 정렬, 버블 정렬
구현 난이도를 기준으로...
쉬운 구현 : 버블 정렬, 선택 정렬, 삽입 정렬
어려운 구현 : 퀵 정렬(피벗 최적화), 힙 정렬(힙 구성), 병합 정렬(분할 정복 기법 사용)
[알고리즘]정렬 알고리즘의 선택과 종류 7가지
- 초안 작성 : 2020년 12월 27일 - 1차 수정 : 2023년 4월 3일 정렬 알고리즘이란? - 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘 - 입력데이터는 보통 배열과 같은 데이터 구조 (연
hyo-ue4study.tistory.com