정렬 알고리즘 입문하기
Sorting Algorithms
정렬 알고리즘의 선택과 구현은 개발 과정에서 중요한 부분입니다. 이는 코드의 성능을 고려할 때 불가피한 요소이며, 효율적인 해결책을 제안하는데 있어 필수적입니다. 우리의 코드가 이루려는 작업을 더 빠르게, 더 직관적으로 수행할 수 있도록 돕기 때문입니다.
이번 포스팅에서는 주요 정렬 알고리즘들의 특징과 성능, 그리고 적절한 활용 상황에 대해 알아보도록 하겠습니다.
Bubble Sort
버블 정렬(Bubble Sort)은 가장 간단하고 직관적인 정렬 알고리즘 중 하나입니다. 정렬 과정에서 큰 값이 마치 거품이 물 위로 떠오르는 것처럼 배열의 끝으로 이동하는 모습에서 버블 정렬이라는 이름이 붙었습니다.
이 알고리즘은 배열을 순회하면서 인접한 두 요소를 비교하고, 순서가 잘못되어있을 경우 두 요소의 위치를 바꿔줍니다. 이 과정을 전체 배열이 완전히 정렬될 때까지 반복적으로 수행합니다.
다음은 버블 정렬 알고리즘을 Java로 구현한 예시 코드입니다:
void bubbleSort(int[] arr) {
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
다음과 같이 주어진 배열을 버블 정렬 알고리즘에 돌려보겠습니다:
int[] arr = {5, 3, 8, 4, 2};
각 단계별로 배열의 변화는 다음과 같습니다:
inputs: [5, 3, 8, 4, 2]
+---+---+-----------------+
| i | j | array |
+---+---+-----------------+
| 0 | 0 | [3, 5, 8, 4, 2] |
| 0 | 1 | [3, 5, 8, 4, 2] |
| 0 | 2 | [3, 5, 4, 8, 2] |
| 0 | 3 | [3, 5, 4, 2, 8] |
| 1 | 0 | [3, 5, 4, 2, 8] |
| 1 | 1 | [3, 4, 5, 2, 8] |
| 1 | 2 | [3, 4, 2, 5, 8] |
| 2 | 0 | [3, 4, 2, 5, 8] |
| 2 | 1 | [3, 2, 4, 5, 8] |
| 3 | 0 | [2, 3, 4, 5, 8] |
+---+---+-----------------+
result: [2, 3, 4, 5, 8]
- 첫 번째 순회에서, 알고리즘은 첫 번째 요소
5와 두 번째 요소3를 비교하고,5가 더 크므로 두 요소의 위치를 바꿉니다. 동일한 과정을 나머지 쌍에 대해서도 반복합니다. 첫 번째 순회가 끝나면, 가장 큰 요소8이 배열의 맨 오른쪽으로 이동하게 됩니다:[3, 5, 4, 2, 8] - 두 번째 순회에서, 가장 큰 요소를 제외한 나머지 요소들 중에서 가장 큰 요소
5를 맨 오른쪽으로 이동시킵니다:[3, 4, 2, 5, 8] - 세 번째 순회에서, 이제 세 번째로 큰 요소
4를 맨 오른쪽으로 이동시킵니다:[3, 2, 4, 5, 8] - 네 번째 순회에서, 그 다음으로 큰 요소
3를 맨 오른쪽으로 이동시킵니다:[2, 3, 4, 5, 8]
모든 요소가 올바르게 정렬되었으므로, 더 이상 순회할 필요가 없습니다. 따라서 최종 정렬된 배열은 [2, 3, 4, 5, 8] 가 됩니다. 이렇게 버블 정렬 알고리즘은 배열의 각 요소를 적절한 위치로 버블링해 나가는 것을 볼 수 있습니다.
이러한 과정 속에서, 버블 정렬의 가장 큰 특징을 알 수 있습니다. 바로 같거나 더 큰 요소들이 배열의 뒷부분으로 이동한다는 사실입니다. 이렇게 하여 배열의 앞부분과 뒷부분을 사이에 명확한 경계가 생기게 되며, 이 경계는 각 순회마다 좌측으로 이동하게 됩니다. 결과적으로 이 경계의 왼쪽에 있는 모든 요소는 이 경계의 오른쪽에 있는 어떤 요소보다 작거나 같게 됩니다. 언제든 이렇게 주어진 배열을 정확하게 정렬할 수 있게 됩니다.
- Perf:
- 시간 복잡도:
O(n^2) - 공간 복잡도:
O(1)
- 시간 복잡도:
- Pros:
- 구현이 간단하고 코드가 직관적입니다. 버블 정렬의 알고리즘은 매우 단순하므로 구현이 쉽고 코드를 읽는 데 어려움이 없습니다. 이는 디버깅이나 코드 분석에서도 장점이 될 수 있습니다.
- 공간 효율이 좋습니다. 버블 정렬은 추가적인 배열을 사용하지 않고 주어진 배열 안에서 바로 정렬을 수행하므로 O(1)의 공간 복잡도를 가집니다.
- 안정적입니다. 동일한 값의 요소에 대해서는 원래의 순서가 유지됩니다.
- Cons:
- 시간 효율이 좋지 않습니다. 버블 정렬의 시간 복잡도는
O(n^2)로, 정렬해야 할 데이터의 양이 많아질수록 처리 시간이 기하급수적으로 증가합니다. - 대량의 데이터에는 적합하지 않습니다. 위의 단점으로 인해, 데이터의 양이 많은 경우에는 버블 정렬보다 더 효율적인 다른 정렬 알고리즘을 사용하는 것이 좋습니다.
- 시간 효율이 좋지 않습니다. 버블 정렬의 시간 복잡도는
버블 정렬은 애플리케이션의 요구 사항과 입력 데이터에 따라 적합할 수 있습니다. 그러나 대체로, 대규모의 데이터가 있는 경우에는 좀 더 효율적인 알고리즘을 사용하는 것이 이상적입니다.
Selection Sort
선택 정렬(Selection Sort)은 주어진 리스트에서 최솟값 혹은 최댓값을 선택하여 앞으로 옮기는 과정을 반복적으로 수행하여 전체 리스트를 정렬하는 알고리즘입니다.
선택 정렬은 알고리즘이 각 순간에서 가장 작은(또는 가장 큰) 요소를 선택하고, 해당 요소를 이미 정렬된 영역의 다음 위치와 교환하는 방법으로 동작합니다.
다음은 선택 정렬 알고리즘을 Java로 구현한 예시 코드입니다:
void selectionSort(int[] arr) {
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
다음과 같이 주어진 배열을 선택 정렬 알고리즘에 돌려보겠습니다:
int[] arr = {5, 3, 8, 4, 2};
각 단계별로 배열의 변화는 다음과 같습니다:
inputs: [5, 3, 8, 4, 2]
+---+---+-----------+-----------------+-----------------+
| i | j | min_index | array_before | array_after_swap|
+---+---+-----------+-----------------+-----------------+
| 0 | 0 | 0 | [5, 3, 8, 4, 2] | - |
| 0 | 1 | 1 | [5, 3, 8, 4, 2] | - |
| 0 | 2 | 1 | [5, 3, 8, 4, 2] | - |
| 0 | 3 | 1 | [5, 3, 8, 4, 2] | - |
| 0 | 4 | 4 | [5, 3, 8, 4, 2] | [2, 3, 8, 4, 5] |
| 1 | 1 | 1 | [2, 3, 8, 4, 5] | - |
| 1 | 2 | 1 | [2, 3, 8, 4, 5] | - |
| 1 | 3 | 3 | [2, 3, 8, 4, 5] | - |
| 1 | 4 | 3 | [2, 3, 8, 4, 5] | no swap |
| 2 | 2 | 2 | [2, 3, 8, 4, 5] | - |
| 2 | 3 | 3 | [2, 3, 8, 4, 5] | - |
| 2 | 4 | 4 | [2, 3, 8, 4, 5] | [2, 3, 4, 8, 5] |
| 3 | 3 | 3 | [2, 3, 4, 8, 5] | - |
| 3 | 4 | 4 | [2, 3, 4, 8, 5] | [2, 3, 4, 5, 8] |
| 4 | 4 | 4 | [2, 3, 4, 5, 8] | no swap |
+---+---+-----------+-----------------+-----------------+
result: [2, 3, 4, 5, 8]
- 첫 번째 순회에서, 알고리즘은 가장 작은 요소
2를 찾고 이를 배열의 첫 번째 위치와 교환합니다:[2, 3, 8, 4, 5] - 두 번째 순회에서, 두번째로 작은 요소
3를 찾아냅니다. 이 요소는 이미 적절한 위치에 있으므로 교환 없이 그대로 둡니다. - 세 번째 순회에서, 세 번째로 작은 요소
4를 찾고 이를 리스트의 세 번째 위치와 교환합니다:[2, 3, 4, 8, 5] - 네 번째와 다섯 번째 순회에서, 나머지 요소들
5,8도 적절한 위치로 이동시켜줍니다:[2, 3, 4, 5, 8]
선택 정렬의 가장 큰 특징은 이름에서도 알 수 있듯이 선택에 있습니다. 이 알고리즘은 특정 순번에서 정렬되지 않은 부분 중 가장 작은(또는 가장 큰) 요소를 선택하고, 이를 이미 정렬된 영역의 다음 위치와 교환합니다. 이로 인해 선택 정렬은 한 번의 순회에서 정확히 한 번의 교환만 이루어집니다.
- Perf:
- 시간 복잡도:
O(n^2) - 공간 복잡도:
O(1)
- 시간 복잡도:
- Pros:
- 단순성: 선택 정렬 알고리즘의 코드 구현이 간단하며, 이해하기 쉽습니다. 알고리즘이 비교적 직관적이라는 장점이 있습니다.
- 공간 효율성: 추가적인 메모리 공간을 거의 사용하지 않습니다. 즉, 원본 배열에서 직접 정렬을 수행하므로 공간 복잡성이
O(1)입니다. - 데이터 이동 최소화: 선택 정렬은 제자리 정렬 알고리즘이며, 최대
n - 1번의 스왑을 수행합니다. 이는 데이터의 이동을 최소화하는 데 이상적입니다.
- Cons:
- 속도: 선택 정렬은
O(n^2)의 시간 복잡도를 가집니다. 이는 작은 데이터 세트에 대해서는 문제가 되지 않지만, 데이터의 개수가 많아질수록 시간이 기하급수적으로 증가합니다. - 불안정: 같은 값의 원소가 입력에 나타날 경우, 선택 정렬은 원래의 순서를 유지하지 않을 수 있습니다. 즉, 안정성이 상대적으로 떨어집니다.
- 속도: 선택 정렬은
이런 장단점을 고려할 때, 선택 정렬 알고리즘은 작은 데이터 세트에 대해서는 빠르고 효율적이지만, 큰 데이터 세트에 대해서는 다른 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.
Insertion Sort
삽입 정렬(Insertion Sort)은 또 다른 간단하고 직관적인 정렬 알고리즘입니다. 삽입 정렬은 각 순회에서 하나의 데이터 요소를 적절한 위치에 삽입함으로써 동작합니다. 마치 카드를 정렬하는 방법과 비슷하며, 그래서 삽입 정렬이라는 이름이 붙었습니다.
이 알고리즘은 배열을 두 부분으로 나눕니다: 앞부분은 정렬된 상태이고, 뒷부분은 아직 정렬되지 않은 상태입니다. 매 순회마다, 아직 정렬되지 않은 부분에서 맨 앞의 요소를 선택하고, 이미 정렬한 부분에서 이 요소가 들어갈 적절한 위치를 찾아 삽입합니다. 이 과정을 계속 반복하면서 전체 배열을 정렬합니다.
다음은 삽입 정렬 알고리즘을 Java로 구현한 예시 코드입니다:
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertingElement = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > insertingElement) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = insertingElement;
}
}
다음과 같이 주어진 배열을 삽입 정렬 알고리즘에 돌려보겠습니다:
int[] arr = {5, 3, 8, 4, 2};
각 단계별로 배열의 변화는 다음과 같습니다:
inputs: [5, 3, 8, 4, 2]
+---+---+-----------------+
| i | j | array |
+---+---+-----------------+
| 1 | 0 | [3, 5, 8, 4, 2] |
| 2 | 1 | [3, 5, 8, 4, 2] |
| 3 | 2 | [3, 4, 5, 8, 2] |
| 4 | 3 | [2, 3, 4, 5, 8] |
+---+---+-----------------+
result: [2, 3, 4, 5, 8]
- 첫 번째 순회에서, 첫 번째 요소
5를 기준으로 나머지 요소들을 비교하며,5보다 작은 요소3을 발견하면 두 요소의 위치를 바꿉니다:[3, 5, 8, 4, 2] - 두 번째 순회에서는
5보다 큰 요소8을 마주치므로 요소의 위치를 바꾸지 않습니다:[3, 5, 8, 4, 2] - 세 번째 순회에서,
8보다 작은 요소4를 마주치므로4를 앞의 정렬된 부분에 삽입합니다:[3, 4, 5, 8, 2] - 네 번째 순회에서,
2를 앞의 정렬된 부분에 삽입하며 최종적으로 배열을 정렬합니다:[2, 3, 4, 5, 8]
모든 요소가 올바르게 위치에 삽입되었으므로, 더 이상 순회할 필요가 없습니다. 삽입 정렬 알고리즘은 각 요소를 적절한 위치에 삽입하여 배열을 정렬하는 과정을 볼 수 있습니다.
- Perf:
- 시간 복잡도: 최악의 경우
O(n^2), 최선의 경우O(n) - 공간 복잡도:
O(1)
- 시간 복잡도: 최악의 경우
- Pros:
- 단순성: 삽입 정렬은 코드 구현이 간단하며, 이해하기 쉽습니다. 알고리즘이 직관적이라는 장점이 있습니다.
- 공간 효율성: 추가적인 메모리 공간을 거의 사용하지 않습니다. 즉, 원본 배열에서 직접 정렬을 수행하므로 공간 복잡성이
O(1)입니다. - 효율성: 데이터가 거의 정렬된 상태에서는 알고리즘의 고유한 특성으로 인해
O(n)의 시간 복잡도를 보입니다. - 안정성: 삽입 정렬은 안정적인 정렬 알고리즘입니다. 즉, 같은 값의 원소가 입력에 나타날 경우, 원래의 순서를 유지합니다.
- Cons:
- 속도: 삽입 정렬은 최악의 경우
O(n^2)의 시간 복잡도를 가집니다. 이는 큰 데이터 세트에 대해서는 효율적이지 않습니다. - 데이터 종속성: 데이터의 초기 상태에 따라 성능이 크게 달라집니다. 데이터가 무작위로 배치되어 있거나 역순으로 정렬된 경우, 좋지 않은 성능을 보일 수 있습니다.
- 속도: 삽입 정렬은 최악의 경우
삽입 정렬은 애플리케이션의 요구 사항과 입력 데이터에 따라 적합할 수 있습니다. 그러나 대체로, 대규모의 데이터가 있는 경우에는 좀 더 효율적인 알고리즘을 사용하는 것이 이상적입니다.
Merge Sort
병합 정렬(Merge Sort)은 분할 정복 방식의 알고리즘 중 하나로, 데이터를 균등하게 두 개로 나누어 각각을 정렬한 후 이를 다시 합치는 방식으로 동작합니다.
입력 데이터를 더 이상 나눌 수 없을 때까지 계속 반으로 나눕니다. 이후에 각 분할된 데이터를 정렬하면서 합치는 과정을 반복합니다. 이러한 방식으로 전체 데이터를 정렬합니다.
다음은 병합 정렬 알고리즘을 Java로 구현한 예시 코드입니다:
void mergeSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex < rightIndex) {
int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort(arr, leftIndex, midIndex);
mergeSort(arr, midIndex + 1, rightIndex);
merge(arr, leftIndex, midIndex, rightIndex);
}
}
void merge(int[] arr, int leftIndex, int midIndex, int rightIndex) {
int leftAreaSize = midIndex - leftIndex + 1;
int rightAreaSize = rightIndex - midIndex;
int[] leftArea = partition(arr, leftIndex, leftAreaSize);
int[] rightArea = partition(arr, midIndex + 1, rightAreaSize);
mergeStep(arr, leftArea, rightArea, leftIndex, leftAreaSize, rightAreaSize);
}
private static int[] partition(int[] arr, int startIndex, int size) {
int[] leftArea = new int[size];
for (int i = 0; i < size; i++) {
leftArea[i] = arr[startIndex + i];
}
return leftArea;
}
private static void mergeStep(
int[] arr,
int[] leftArea,
int[] rightArea,
int arrIndex,
int leftAreaSize,
int rightAreaSize) {
int leftIndex = 0;
int rightIndex = 0;
while (leftIndex < leftAreaSize && rightIndex < rightAreaSize) {
if (leftArea[leftIndex] <= rightArea[rightIndex]) {
arr[arrIndex] = leftArea[leftIndex];
leftIndex++;
} else {
arr[arrIndex] = rightArea[rightIndex];
rightIndex++;
}
arrIndex++;
}
arrIndex = appendRemains(arr, leftArea, arrIndex, leftIndex, leftAreaSize);
arrIndex = appendRemains(arr, rightArea, arrIndex, rightIndex, rightAreaSize);
}
private static int appendRemains(int[] arr, int[] area, int arrIndex, int currentIndex, int areaSize) {
while (currentIndex < areaSize) {
arr[arrIndex] = area[currentIndex];
currentIndex++;
arrIndex++;
}
return arrIndex;
}
입력 배열이 다음과 같이 주어졌을때 병합 정렬 알고리즘의 처리 과정을 살펴보도록 하겠습니다:
int[] arr = {3, 5, 2, 4, 1, 7, 8, 6};
앞서 병합 정렬은 분할 정복 알고리즘의 한 종류라고 하였습니다. 분할 단계에서는 최소 단위까지 재귀적으로 계속 배열을 절반으로 나누는 과정을 반복합니다:
# 첫 번째 분할
[3, 5, 2, 4] [1, 7, 8, 6]
# 두 번째 분할
[3, 5] [2, 4] [1, 7] [8, 6]
# 세 번째 분할 (최소 단위까지 분할)
[3] [5] [2] [4] [1] [7] [8] [6]
정복 단계에서는 분할을 마친 결과를 병합하면서 정렬해 나갑니다. 같은 레벨의 배열 두 개를 추출하여 값들을 비교하면서 정렬된 배열을 만듭니다:
# 첫 번째 병합
[3, 5] [2, 4] [1, 7] [6, 8]
# 두 번째 병합
[2, 3, 4, 5] [1, 6, 7, 8]
# 세 번째 병합 (최종 결과)
[1, 2, 3, 4, 5, 6, 7, 8]
병합 정렬의 이러한 과정을 통해 주어진 입력 배열은 정렬된 배열로 변환됩니다.
- Perf:
- 시간 복잡도:
O(n log n) - 공간 복잡도:
O(n)
- 시간 복잡도:
- Pros:
- 병합 정렬는 모든 경우에 대해 일관성 있는 성능(O(n log n))을 제공하므로 대용량 데이터에 적합합니다.
- 병합 정렬은 안정적인 정렬 알고리즘이므로, 같은 값의 원소가 입력에 나타나더라도 원래의 순서를 유지합니다.
- Cons:
- 병합 정렬은 임시 배열을 사용하므로 메모리 사용이 큽니다. 이로 인해 공간 복잡도는 O(n)입니다.
- 병합 정렬은 재귀적으로 동작하므로 스택 오버플로우가 발생할 위험이 있습니다.
- 작은 크기의 배열에 대해 병합 정렬을 사용하는 것은 비효율적일 수 있습니다. 이러한 경우, 보통 삽입 정렬 같은 다른 알고리즘을 사용합니다.
병합 정렬은 대규모 데이터셋을 다루는 알고리즘, 또는 안정적인 정렬이 요구되는 경우에 매우 유용합니다. 그러나 메모리 사용이 많고, 때로는 오버헤드가 발생할 수 있기 때문에 항상 최선의 선택은 아닐 수 있습니다.
Quick Sort
Heap Sort
Radix Sort
Tree Sort
- Algorithm