[Algorithm 기초] 기수 정렬, 계수 정렬, 셀 정렬
기수 정렬 (Radix Sort)
낮은 자리수 부터 정렬하는 방식. 각 원소 간의 비교 연산을 하지 않아 빠른 대신,
기수 테이블(queue)을 위한 메모리 필요
알고리즘 복잡도 : O(dn)
기수정렬구현 의사코드 (Pseudocode)
RadixSort(a[], n):
// Finding the maximum element
max=a[0]
For (i=1 to n-1):
If (a[i]>max):
max=a[i]
// Calling countingSort for
// k times using For loop.
For (div=1 to max/div>0):
countingSort(a, n, div)
div=div*10
계수 정렬(Counting Sort)
숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식. 카운트를 위한 메모리 필요
알고리즘 복잡도 : O(n + k)
계수정렬구현 의사코드 (Pseudocode)
// initialising array Aux[] with 0
for i = 0 to M + 1 do
Aux[ i ] = 0
// Storing count of each element
// in array Aux[]
for i in Arr[] do
Aux[ Arr[ i ] ] ++
for i from N-1 to 0 in Arr[] do
sortedArr[ Aux[ Arr[i] ] - 1] = Arr[i]
Aux[ Arr[i] ] --
return sortedArr[]
셸 정렬(shell Sort)
삽입정렬의 약점을 보완한 정렬 방식. 이전 모든 데이터와 비교하지 않고 일정 간격을 두어 비교
-> 삽입정렬의 약점 : 오름차순 정렬기준, 내림차순으로 구성된 데이터에 대해서는
앞의 데이터와 하나씩 비교하며 모두 교환해야 함
알고리즘 복잡도 : O(n제곱) = n(n-1)/2
셸정렬구현 의사코드 (Pseudocode)
Caculate gap size ($gap)
WHILE $gap is greater than 0
FOR each element of the list, that is $gap apart
Extract the current item
Locate the position to insert
Insert the item to the position
END FOR
Calculate gap size ($gap)
END WHILE
연습
public class algorithm03 {
/*
//Radix Sort 기수정렬
public static void radixSort(int[] arr){
ArrayList<Queue<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(new LinkedList<>());
}
int idx = 0;
int div = 1;
int maxLen = getMaxLength(arr);
for (int i = 0; i < maxLen; i++) {
for (int j = 0; j < arr.length; j++) {
list.get((arr[j] / div)% 10 ).offer(arr[j]);
}
for (int j = 0; j < 10; j++) {
Queue<Integer> queue = list.get(j);
while (!queue.isEmpty()){
arr[idx++] = queue.poll();
}
}
idx = 0;
div *= 10;
}
}
public static int getMaxLength(int[] arr){
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
int len = (int)Math.log10(arr[i]) + 1;
if(maxLen < len){
maxLen = len;
}
}
return maxLen;
}
*/
/*
//Counting Sort 계수정렬
public static void countingSort(int[] arr){
int max = Arrays.stream(arr).max().getAsInt();
int[] cntArr = new int[max + 1];
for (int i = 0; i < arr.length; i++) { //카운팅 테이블
cntArr[arr[i]]++;
}
int idx = 0;
for (int i = 0; i < cntArr.length; i++) { //정렬
while (cntArr[i] > 0){
arr[idx++] = i;
cntArr[i] -= 1;
}
}
// HashMap<Integer, Integer> map = new HashMap<>(); //하나의 데이터가 방대할 경우 사용
// for (int item : arr){
// map.put(item, map.getOrDefault(item, 0) + 1);
// }
//
// int idx2 = 0;
// ArrayList<Integer> list = new ArrayList<>(map.keySet());
// Collections.sort(list);
//
// for (int i = 0; i < list.size(); i++) {
// int cnt = map.get(list.get(i));
// while (cnt>0){
// arr[idx2++] = list.get(i);
// cnt--;
// }
// }
}
*/
//셀 정렬 Shell Sort
public static void shellSort(int[] arr){
int gap = arr.length / 2;
for (int g = gap; g > 0 ; g /= 2) {
for (int i = g; i < arr.length; i++) {
int tmp = arr[i];
int j = 0;
for (j = i - g; j >= 0; j -= g) { // 0 부터
if(arr[j] > tmp){ //tmp값보다 크면
arr[j + g] = arr[j]; //tmp쪽에 넣어줌
}else {
break;
}
}
arr[j + g] = tmp; //갭 간격으로 삽입정렬을 진행
}
}
}
public static void main(String[] args) {
//Test code
/*
//Radix Sort 기수정렬
int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
radixSort(arr);
System.out.println("기수 정렬 : " + Arrays.toString(arr));
*/
/*
//Counting Sort 계수정렬
int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
countingSort(arr);
System.out.println("계수 정렬 : " + Arrays.toString(arr));
*/
//셀 정렬 Shell Sort
int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
shellSort(arr);
System.out.println("셀 정렬 : " + Arrays.toString(arr));
}
}
관련link
https://brilliant.org/wiki/radix-sort/
Radix Sort | Brilliant Math & Science Wiki
Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by individual digits that share the same significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbe
brilliant.org
[정렬 알고리즘] 05 계수 및 기수 정렬(Counting Sort / Radix Sort) 이론 및 구현
1. 계수 및 기수 정렬 개념 1) 계수 정렬 각 원소를 사이에 비교하지 않는 정렬이며 안정성(stable)을 가짐 임시작업에 사용되는 메모리를 필요로 함 (각 숫자를 counting하여 누적시킬 배열과 정렬된
rninche01.tistory.com
https://www.interviewkickstart.com/learn/counting-sort
Counting Sort Algorithm
Sorting algorithms are a must-know for any software engineer preparing for a technical interview. They will help you crack many questions during your coding round. In this article, we’ll give you a refresher on the counting algorithm: What Is Counting
www.interviewkickstart.com
https://startutorial.com/view/data-structure-and-algorithm-shell-sort
StarTutorial: Data Structure And Algorithm Shell Sort
StarTutorial: Data Structure And Algorithm Shell Sort
startutorial.com