[알고리즘] 기타 정렬 알고리즘(계수, 기수, 외부)

알고리즘	최적 시간	평균 시간	최악 시간	제자리 정렬	안정 정렬
거품 정렬	O(n)	O(n²)	O(n²)	O	O
선택 정렬	O(n²)	O(n²)	O(n²)	O	X
삽입 정렬	O(n)	O(n²)	O(n²)	O	O
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O	X
병합 정렬	O(n log n)	O(n log n)	O(n log n)	X	O
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O	X
기수 정렬	O(nk)	O(nk)	O(nk)	X	O
계수 정렬	O(n + k)	O(n + k)	O(n + k)	X	O

 

In-place & Stable Sort

• 제자리 정렬(in-place sorting): 추가적인 메모리 공간을 거의 사용하지 않고, 입력 배열 자체에서 정렬을 수행하는 알고리즘을 의미
  • O(1) 또는 O(log n) 정도의 보조 메모리만 사용하며, 기존 데이터를 재배치하는 방식으로 작동
• 안정 정렬(Stable Sort): 동일한 값의 요소들이 정렬 전후의 순서가 바뀌지 않는 정렬 알고리즘을 의미
  • 즉, 값이 같은 데이터가 있을 때, 원래의 입력 순서가 보존

계수 정렬(Count Sort)

• 정의: 데이터의 크기를 기준으로 횟수를 세어 정렬하는 알고리즘
• 목적: 범위가 작고 데이터 분포가 균일한 경우에 적합
• 특징:
  • 비교 기반 아님: 데이터를 직접 비교하지 않고, 각 값의 빈도를 계산하여 정렬
  • 제자리 정렬 아님: 정렬을 위한 추가 공간 필요
  • 불안정 정렬: 동일한 값에 대해 초기 순서가 유지되지 않음

 

자바 코드

int arr[5]; 		// [5, 4, 3, 2, 1]
int sorted_arr[5];

// 과정 1 - counting 배열의 사이즈를 최대값 5가 담기도록 크게 잡기
int counting[6];	// 단점 : counting 배열의 사이즈의 범위를 가능한 값의 범위만큼 크게 잡아야 하므로, 비효율적이 됨.

// 과정 2 - counting 배열의 값을 증가해주기.
for (int i = 0; i < arr.length; i++) {
    counting[arr[i]]++;
}
// 과정 3 - counting 배열을 누적합으로 만들어주기.
for (int i = 1; i < counting.length; i++) {
    counting[i] += counting[i - 1];
}
// 과정 4 - 뒤에서부터 배열을 돌면서, 해당하는 값의 인덱스에 값을 넣어주기.
for (int i = arr.length - 1; i >= 0; i--) {
    sorted_arr[counting[arr[i]] - 1] = arr[i];
    counting[arr[i]]--;
}

 

 

 

기수 정렬(Radix Sort)

• 정의: 정수를 자릿수 별로 비교하여 정렬하는 알고리즘
• 목적: 자릿수 기반의 정수 데이터를 다룰 때 효율적이며, 범위가 작고 자릿수가 일정한 정수 데이터에 적합
• 특징:
  • 비교 기반 아님: 원소 간의 직접적인 비교 없이 자릿수에 따라 정렬
  • 제자리 정렬 아님 - 보조 배열을 사용하여 각 자릿수별 정렬을 하기 때문에 추가 공간이 필요
  • 안정 정렬(Stable Sort): 동일한 값의 순서가 유지됨

 

자바 코드

void radixSort(int[] arr) {
    int max = getMax(arr); // 배열에서 최대값 찾기
    for (int place = 1; max / place > 0; place *= 10) {
        countingSort(arr, place);
    }
}

 

외부 정렬

• 내부정렬: 입력이 주기억 장치(내부 메모리)에 있는 상태에서 정렬이 수행되는 정렬
• 외부정렬: 입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수밖에 없는 상태에서 수행되는 정렬
• 과정

1. 주 기억 장치에 수용할 만큼 블록으로 분할한 후, Read & 내부 정렬 진행

2. 정렬된 블록의 합병

• 정렬된 블록들을 반복적인 합병을 통해, 하나의 정렬된 거대한 블록으로 만듬
  • 블록들을 부분적으로 주 기억 장치에 읽어, 합병을 수행