정렬(Sort)
정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.
그럼 정렬은 왜 하는 걸까??
내가 편의점에서 아르바이트할 때를 생각해 보면 음료 진열대 뒤쪽에서 음료들을 하나씩 넣어가면서 진열해야 된다. 여기서 중요한 것은 유통기한이 빠른 순서대로 넣는 것이다. 하지만 창고에 쌓인 음료들을 보면 유통기한이 빠른 순서대로 정렬되지 않은 경우를 많이 경험했다.
창고에 있는 음료들의 유통기한을 빠른 순서대로 정렬하면 진열대에 음료를 넣을 경우 더 빠르게 작업을 할 수 있을 것이다.
이러한 정렬 알고리즘에는 어떤 종류가 있는지 확인해 보면
| 종류 | 설명 | 시간복잡도 | 메모리 | 안정성 | ||
| 최고 | 평균 | 최악 | ||||
| 버블 정렬 (Bubble Sort) |
데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 | O(n) | O(n²) | O(n²) | 1 | Y |
| 선택 정렬 (Selection Sort) |
대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 | O(n²) | O(n²) | O(n²) | 1 | N |
| 삽입 정렬 (Insertion Sort) |
대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 | O(n) | O(n²) | O(n²) | 1 | Y |
| 쉘 정렬 (Shell Sort) |
삽입 정렬의 장점을 살린 정렬 방식 | O(nlogn) / O(nlog2n) |
depends on gap sequence |
O(nlog2n) / n2 | 1 | N |
| 힙 정렬 (Heap Sort) |
힙 자료구조를 활용하여 정렬하는 방식 | O(nlogn) | O(nlogn) | O(nlogn) | 1 | N |
| 퀵 정렬 (Quick Sort) |
pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 | O(nlogn) | O(nlogn) | O(n²) | log n | N |
| 병합 정렬 (Merge Sort) |
이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 | O(nlogn) | O(nlogn) | O(nlogn) | n | Y |
| 기수 정렬 (Radix Sort) |
데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 | O(kn) | O(kn) | O(kn) | n + 2k | Y |
이 외에도 여러 가지 정렬 알고리즘이 있다.
버블 정렬(Bubble Sort)
버블 정렬은 인접한 데이터 값을 비교하여 정렬하는 방식이다.
창고에 콜라가 위의 사진 처럼 되어 있으면 앞에 있는 콜라의 유통기한과 인접한 콜라의 유통기한을 확인하고 기한이 빠른 콜라와 자리를 바꾼다.
버블 정렬의 구현 순서
1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2~3번을 반복한다.
5. 정렬 영역을 설정하고 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5번을 반복한다.
※ 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 위에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.
코드로 보는 버블 정렬
public class BubbleSort {
public void bubbleSort(int[] arr) {
//배열의 size - 1회차 만큼 반복
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
//왼쪽 원소가 오른쪽 원소보다 크면 바꿔치기
if(arr[j]<arr[j-1]) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
//한 회전이 끝날 때마다 전체 배열 출력
System.out.print(i+1 + "회전: [ ");
for (int x = 0; x < arr.length; x++) {
System.out.print(arr[x] + " ");
}
System.out.println("]");
}
//최종 배열 출력
System.out.print("최종 배열 : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}버블 정렬을 코드로 구현하면 2중 for문이 핵심이다.
i가 배열의 크기만큼 반복하면서 j를 1부터 배열의 크기를 i만큼 빼면서 정렬하게 되는데 -i를 하는 이유는 첫 번째 정렬이 끝나면 마지막 데이터부터 정렬되게 되는데 이때 -i를 통해서 정렬이 완료된 부분을 설정할 수 있게 된다.
버블 정렬의 장단점
버블 정렬의 장점
추가적인 메모리 소비가 적다.
구현이 매우 쉽다.
안정정렬이 가능하다.
버블 정렬의 단점
다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.
선택 정렬(Selection Sort)
선택 정렬의 핵심은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap 하는 것이 핵심이다.
위의 사진처럼 가장 앞에 있는 콜라의 유통기한과 현재 보유하고 있는 콜라들 중에서 가장 짧은 유통기한을 비교하여 swap 한다. 해당 과정을 반복하여 정렬을 실시한다.
선택 정렬의 구현 순서
1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다.
3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.
코드로 보는 선택 정렬
public class Selection_Sort {
public static int[] selection_sort(int[] arr) {
return selection_sort(arr, arr.length);
}
private static int[] selection_sort(int[] arr, int length) {
for (int i = 0; i < length - 1; i++) {
// 현재 배열에서 최솟값을 찾기
int min = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 현재 i번째 값과 최솟값을 서로 교환하기
swap(arr, min, i);
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = new int[]{7, 3, 2, 8, 9, 4, 6, 1, 5};
int[] result = selection_sort(arr);
for (int i = 0; i < result.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
선택 정렬의 장단점
선택 정렬의 장점
추가적인 메모리 소비가 적다.
선택 정렬의 단점
시간복잡도가 높다.
안정 정렬이 아니다.
삽입 정렬(Insertion Sort)
이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 알고리즘이다.
시간 복잡도는 O(n²)으로 느린 편이지만 구현이 쉽다.
정렬된 범위가 정렬하고자 하는 데이터의 크기만큼 커지면 정렬을 종료한다.
삽입 정렬의 구현 순서
1. 현재 index에 있는 데이터 값을 선택한다. (유통 기한 5일은 이미 정렬된 데이터라고 가정)
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다. (위 사진에서 5일부터 마지막 데이터인 4일까지 연산을 수행한다.)
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.
5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.
코드로 보는 삽입 정렬
public class InsertSort {
public void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int targetValue = arr[i];
int previousIndex = i - 1;
while (previousIndex >= 0 && targetValue < arr[previousIndex]) {
arr[previousIndex+1] = arr[previousIndex];
previousIndex -= 1;
}
arr[previousIndex + 1] = targetValue;
System.out.print(targetValue + " 삽입 -> ");
printArray(arr);
}
}
private void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}삽입 정렬 코드를 살펴보면 인덱스를 0부터 시작하지 않고 1부터 시작하게 된다. 여기서 targetValue를 1번 인덱스에 위치한 값으로 선택하고 previousIndex를 이전 인덱스 위치로 설정한다.
그다음 비교를 통해서 targetValue가 previousIndex에 위치한 값보다 작을 경우 값을 바꾸면서 정렬을 진행하게 된다.
마지막으로 previousValue의 값에서 + 1 한 값의 인덱스 위치에 targetValue를 저장하여 정렬을 마무리하게 된다. (이전에 previousValue에 i - 1 값을 저장하기 때문에 마지막 인덱스 위치에 데이터를 저장하려면 +1이 필요하다.
삽입 정렬의 장단점
삽입 정렬의 장점
추가적인 메모리 소비가 적다.
거의 정렬이 된 경우 매우 효율적이다.
안정 정렬이 가능하다.
삽입 정렬의 단점
역순에 가까울 수록 매우 비효율적이다.
데이터의 상태에 따라서 성능 편차가 매우 크다.
퀵 정렬(Quick Sort)
퀵 정렬은 기준값(pivot)을 선정해 해당 값 보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.
평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n²)이 된다.
기준 값이 시간 복잡도에 많은 영향을 주기 때문에 기준 값 설정이 중요하다.
퀵 정렬의 구현 순서
1. 데이터를 분할하는 pivot을 설정한다.
2. pivot을 기준으로 다음 a ~ e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.
- a - start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.
- b - end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.
- c - start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap 하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다. (해당 사진에서 start와 end 인덱스가 이동하여 만나는 지점의 데이터는 15일이다.)
- d - start와 end가 만날 때까지 a ~ c를 반복한다.
- e - start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다. (만나는 지점의 데이터 값은 15일로 pivot 값인 17일 보다 작기 때문에 pivot 값은 15일 오른쪽에 위치하게 된다.)
3. 분리 집합에서 각각 다시 pivot을 선정한다.
4. 분리 집합이 1개 이하가 될 때까지 과정 1 ~ 3을 반복한다.
코드로 보는 퀵 정렬(왼쪽 피벗 기준)
public class LeftQuickSort {
public void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int low, int high) {
if (low >= high) { // 왼쪽 값이 오른쪽 값보다 크거나 같다면 서로 겹치는 부분이기 때문에 return
return;
}
int pivot = partition(arr, low, high); // 피벗을 기준으로 부분 리스트를 나눠준다.
quickSort(arr, low, pivot - 1); // 피벗을 기준으로 왼쪽 값들을 정렬
quickSort(arr, pivot + 1, high); // 피벗을 기준으로 오른쪽 값들을 정렬
}
}앞서 살펴본 개념을 통해서 퀵 정렬을 하기 위해 피벗이라는 값과 start, end 값이 필요하다는 것을 알았다. (여기서는 low, high)
하나씩 살펴보면 먼저 sort메서드에서 받아온 배열을 quickSort의 매개변수로 값을 넘겨주게 되는데 이때 low의 값은 0으로, high 값은 배열의 길이 - 1을 한 값으로 넘겨준다.
다음으로 quickSort 메서드를 살펴보면 매개변수로 받은 low와 high 값을 먼저 비교하게 되는데 두 개의 값이 같거나 low가 크다는 것은 부분 리스트의 값이 한 개일 때를 의미하기 때문에 다시 return 해주게 된다.
피벗 변수에는 partition 메서드를 통해서 반환되는 값을 저장하게 되고, 해당 피벗 값을 기준으로 왼쪽과 오른쪽으로 부분 리스트가 나눠지며 다시 정렬을 진행하게 된다.
private int partition(int[] arr, int left, int right) {
int low = left; // 가장 왼쪽의 위치
int high = right; // 가장 오른쪽의 위치
int pivot = arr[left]; // 왼쪽 기준이기 때문에 배열의 왼쪽 인덱스 값을 피벗으로 설정
while (low < high) { // 위치 이동
while (arr[high] > pivot) { // 피벗을 기준으로 오른쪽에 위치한 값이 클 경우
--high; // 오른쪽 위치를 감소
}
while (arr[low] <= pivot && low < high) { // 피벗을 기준으로 왼쪽에 위치한 값이 작은 경우
++low; // 왼쪽 위치를 증가
}
swap(arr, low, high); // 피벗을 기준으로 왼쪽의 값은 피벗보다 크고 오른쪽의 값은 피벗보다 작기 때문에 스왑 진행
}
swap(arr, left, low); // 왼쪽의 위치와 오른쪽의 위치가 같기 때문에 스왑을 진행
return low;
}partition 메서드는 먼저 low와 high 값을 받아온 매개변수를 통해서 저장하게 되고 왼쪽에 위치한 값으로 피벗을 설정한다.
그 후 while문을 통해서 피벗을 기준으로 오른쪽 값이 작아질 때까지 반복하게 되고, 왼쪽 값은 커질 때까지 반복하게 된다. 이때 low 값을 증가시켜 왼쪽 위치를 이동했는데 high보다 커질 경우 엇갈렸다고 판단하고 while문을 벗어나게 된다.
안쪽에 위치한 while문을 벗어나게 되면 이동한 low와 high 값을 swap 메서드의 매개 변수로 넘겨주게 된다.
바깥에 위치한 while문을 최종적으로 벗어나게 되면 low와 high값이 같아지거나 엇갈린 경우이기 때문에 현재 이동한 low와 처음 매개변수로 받아온 left 값을 다시 swap 하게 된다.
최종적으로 swap이 마무리되면 이동했던 low 값을 다시 quickSort 메서드로 반환하여 새로운 피벗 값을 설정하게 된다.
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}swap 메서드는 매개 변수로 받아온 i(low), j(high) 값을 인덱스로 줘서 해당 인덱스에 위치한 값을 바꾸게 된다.
퀵 정렬의 장단점
퀵 정렬의 장점
특정 사태가 아닌 이상 평균 시간 복잡도는 nlogn으로 같은 시간복잡도를 가지는 알고리즘에 비해 대체적으로 속도가 매우 빠르다.
추가적인 별도의 메모리를 필요로하지 않으며 재귀 호출 스택프레임에 의한 공간복잡도는 logn으로 메모리를 적게 소비한다.
퀵 정렬의 단점
특정 조건하에 성능이 급격하게 떨어진다.
재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.
병합 정렬(Merge Sort)
분할과 정복 방식을 사용하여 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
시간 복잡도는 O(nlogn)이다.
코딩 테스트에서 병합 정렬의 정렬 방식은 여러 문제에서 응용하므로 반드시 숙지해야 한다.
병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 한다.
2개의 그룹을 병합하는 과정
위 사진의 2개 그룹을 병합하여 정렬하면 아래의 사진과 같이 정렬할 수 있다.
투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
왼쪽포인터와 오른쪽포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
마지막으로 20일과 30일을 비교하여 값이 작은 20일을 결과 배열에 추가하면 왼쪽 그룹에 있는 데이터는 다 사용한 상태가 된다.
왼쪽 그룹에 속한 데이터가 다 사용될 경우 오른쪽 그룹에 남아있는 데이터는 자동으로 결과 배열에 추가된다.
코드로 보는 병합 정렬
public class BottomUpMerge {
private int[] sorted; // 합치는 과정에서 정렬하여 원소를 담을 임시배열
// TODO: 병합 정렬 시작
public void merge_sort(int[] a) {
sorted = new int[a.length];
merge_sort(a, a.length - 1);
sorted = null;
}
// TODO: 부분 리스트 병합
private void merge_sort(int[] a, int right) {
for(int size = 1; size <= right; size += size) {
for(int left = 0; left <= right - size; left += (2 * size)) {
int mid = left + size - 1; // 왼쪽 부분 리스트
int high = Math.min(left + (2 * size) - 1, right); // 오른쪽 부분 리스트, 배열의 인덱스 범위 문제로 둘 중 작은 값으로 병합
merge(a, left, mid, high);
}
}
}
// TODO: 부분 리스트 병합
private void merge(int[] a, int low, int mid, int high) {
int left = low; // 왼쪽 부분리스트 시작점
int right = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = low; // 채워넣을 배열의 인덱스
System.out.println("왼쪽 부분 배열 시작 : " + left + ", 오른쪽 부분 배열 시작 : " + right);
System.out.println("right = " + high);
while(left <= mid && right <= high) {
if(a[left] <= a[right]) {
sorted[idx] = a[left];
idx++;
left++;
} else {
sorted[idx] = a[right];
idx++;
right++;
}
}
if(left > mid) {
while(right <= high) {
sorted[idx] = a[right];
idx++;
right++;
}
} else {
while(left <= mid) {
sorted[idx] = a[left];
idx++;
left++;
}
}
for (int i = low; i <= high; i++) {
a[i] = sorted[i];
}
}
}위의 코드는 병합 정렬의 방법 중 Bottom-Up 방식을 사용한 코드이다.
병합 정렬은 분할하는 부분과 병합하는 부분을 중점으로 봐야한다.
// TODO: 부분 리스트 병합
private void merge_sort(int[] a, int right) {
for(int size = 1; size <= right; size += size) {
for(int left = 0; left <= right - size; left += (2 * size)) {
int mid = left + size - 1; // 왼쪽 부분 리스트
int high = Math.min(left + (2 * size) - 1, right); // 오른쪽 부분 리스트, 배열의 인덱스 범위 문제로 둘 중 작은 값으로 병합
merge(a, left, mid, high);
}
}
}먼저 merge_sort 메서드를 통해서 부분 리스트를 만들어 주는데 반복문을 통해서 왼쪽 부분 리스트와 오른쪽 부분 리스트를 나눠서 병합을 하는 merge() 메서드의 매개변수로 넘겨주게 된다.
merge() 메서드는 받아온 부분 리스트와 왼쪽, 중간, 오른쪽 위치를 통해서 데이터를 정렬하게 되고 sorted라는 임시 배열에 저장하여 다시 원본 배열에 저장하는 방식으로 병합이 이뤄지게 된다.
다른 병합 정렬 방식 중에서 Top-Down 방식과의 큰 차이는 재귀 호출 없이 반복문을 사용하기 때문에 메모리 사용을 줄일 수 있어 배열의 크기가 클 때 효율적으로 동작할 수 있다.
병합 정렬의 장단점
병합 정렬의 장점
항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(nlogn)으로 유지가 된다.
안정정렬이다.
병합 정렬의 단점
정렬 과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다.
보조 배열에서 원본배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에 데이터가 많을 경우 상대적으로 시간이 많이 소요된다.
기수 정렬(Radix Sort)
값을 비교하지 않는 특이한 정렬 알고리즘이다.
값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
시간 복잡도는 O(kn)으로 k는 데이터의 자릿수를 의미한다. (시간 복잡도가 정렬 알고리즘 중 가장 짧음)
10개의 큐(bucket)를 이용하고 각 큐는 값의 자릿수를 대표한다.
1의 자릿수를 먼저 비교하여 정렬한다. 여기서 큐를 사용하기 때문에 FIFO를 고려해야 한다.
1의 자릿수를 비교하여 정렬을 마치면 마찬가지로 10의 자릿수를 비교하여 데이터를 정렬한다.
여기서 핵심은 자릿수를 비교하여 더 적은 값을 큐에 삽입하기 때문에 큐에서 이미 정렬이 이루어진 상태가 된다.
시간 복잡도를 계산하면 전체 데이터의 양인 N은 8이 되며, 자릿수는 10의 자릿수까지 있기 때문에 k는 2가 된다.
O(2 x 8) 이므로 값은 16이 되며 실제로 위 사진에서 큐에서 발생하는 데이터 접근을 카운팅 하면 16개가 된다.
정렬해야 되는 데이터가 너무 많으면 고려해 볼 만한 알고리즘이다.
코드로 보는 기수정렬
import java.util.LinkedList;
import java.util.Queue;
public class Radix_Sort {
private static void radix_sort(int[] arr) {
// 10진수 큐 생성
Queue<Integer>[] queues = new LinkedList[10];
for (int i = 0; i < 10; i++) {
queues[i] = new LinkedList<>();
}
int maxLength = maxDigitCount(arr);
// 각 자리수의 숫자를 저장
int digitNumber = 0;
// 배열에 다시 저장할 때 필요한 변수
int index = 0;
// 자리수 만큼 반복
for (int i = 0; i < maxLength; i++) {
// 데이터의 개수만큼 반복
for (int j = 0; j < arr.length; j++) {
digitNumber = getDigit(arr[j], i);
queues[digitNumber].add(arr[j]);
}
// 큐에 들어간 데이터를 순서대로 꺼내 배열에 덮어씌운다.
for (int j = 0; j < arr.length; j++) {
while (!queues[j].isEmpty()) {
arr[index++] = queues[j].remove();
}
}
index = 0;
}
}
// 숫자의 자리수를 변환해준다.
private static int getDigit(int num, int index) {
return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// 숫자의 자리수를 구해준다.
private static int digitCount(int num) {
if (num == 0) return 1;
return (int) Math.floor(Math.log10(Math.abs(num))) + 1;
}
// 배열에 있는 데이터 중 가장 큰 자리수를 반환해준다.
private static int maxDigitCount(int[] arr) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, digitCount(arr[i]));
}
return max;
}
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 11, 20, 4, 15, 17, 30};
radix_sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
기수 정렬의 장단점
기수 정렬의 장점
비교 연산 없이 정렬을 수행할 수 있다.
안정 정렬이다.
기수 정렬의 단점
적용할 수 있는 범위가 제한적이다. (정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들만 가능)
기수만큼의 추가 저장 공간이 필요하다.
'CS > 알고리즘' 카테고리의 다른 글
| 알고리즘 - 벨만-포드(Bellman-Ford) (0) | 2023.08.15 |
|---|---|
| 알고리즘 - 다익스트라(Dijkstar) (0) | 2023.08.15 |
| 알고리즘 - 위상 정렬 (0) | 2023.08.14 |
| 알고리즘 - 유니온 파인드 (0) | 2023.08.14 |
| 알고리즘 - DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) (0) | 2023.08.08 |
