[알고리즘] 정렬 - Counting sort

한호성·2022년 5월 16일

알고리즘

정렬 알고리즘 - Counting sort

개념 및 원리

[3,2,4,5,6,1,2] 라는 배열이 있을 때, 각
1 : 1개
2 : 2개
3 : 1개
4 : 1개
5 : 1개
6 : 1개

이것을 순서대로 작성해주면 sort가 된다 [1,2,2,3,4,5,6]

이게 기본 개념이다.
(기본 개념이 뭔지 모르고 코드를 봤을 때는, 어떤 정렬인지 감조차 오지 않았다.)

*Counting Sort 정렬 알고리즘 중 시간복잡도 O(n) 으로 성능이 좋다.
대표적인 정렬 알고리즘으로 퀵 정렬, 힙 정렬, 합병 정렬 등이 있다. 이들의 시간복잡도는 O(NlongN) 이다.

알고리즘 과정

기본 알고리즘 구현방식

계수 정렬은 정렬되지 않은 배열(ary)의 수들이 몇번 나왔는지 적어둔다

몇 번 나왔는지 기록한 배열을 (count) 배열이라고 하고, (count) 배열을 앞부터 누적합으로 표현하여, (count) 배열의 idx 값 (정렬 되어야하는 값) 이 몇번 째에 나와야 하는지 기록한다.

그 후 , (ary)의 각 값을 누적합으로 표현한 (count) 배열을 통해 몇번째에 나와야하는지 (result) 배열에 대입한다. 이때, 누적합으로 표현한 (count)값의 -1을 한 결과값을 (result)배열의 index 값으로 넣고, (ary) 값을 value로 넣는다.

해당 알고리즘의 한계

데이터 값은 양수여야 한다.
값의 범위가 너무 크지 않아야 한다. ( 메모리 사이즈를 넘으면 안된다)

간단하게 생각해봐도 수의 범위가 커지면 커질수록 counting 할 배열을 수의 범위에 따라 하나 더 만들어야 한다. 메모리 낭비가 될 수 있다.

기본코드예제


public class CountingSort {
	public static void main(String[] args) {
		
		int[] array = new int[100];		// 수열의 원소 : 100개
		int[] counting = new int[31];	// 수의 범위 : 0 ~ 30
		int[] result = new int[100];	// 정렬 될 배열 
		
		for(int i = 0; i < array.length; i++) {
			array[i] = (int)(Math.random()*31);	// 0 ~ 30
		}
 
		
		// Counting Sort
		// 과정 1 
		for(int i = 0; i < array.length; i++) {
			// array 의 value 값을 index 로 하는 counting 배열 값 1 증가 
			counting[array[i]]++;			
		}
		
		// 과정 2 
		for(int i = 1; i < counting.length; i++) {
			// 누적 합 해주기 
			counting[i] += counting[i - 1];
		}
		
		// 과정 3
		for(int i = array.length - 1; i >= 0; i--) {
			/*
			 *  i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤 
			 *  counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
			 */
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;
		}
		
		
		
		/* 비교 출력 */
		
		// 초기 배열 
		System.out.println("array[]");
		for(int i = 0; i < array.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(array[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// Counting 배열 
		System.out.println("counting[]");
		for(int i = 0; i < counting.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(counting[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// 정렬된 배열
		System.out.println("result[]");
		for(int i = 0; i < result.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(result[i] + "\t");
		}
		System.out.println();
	}
 
}

더 나아가서 , counting sort 간단하게 하는법

public class counting_sort {
	public static void main(String[] args) {
 
		int[] arr = new int[101]; // 수의 범위 : 0 ~ 100
 
		for (int i = 0; i < 50; i++) {	// 수열의 크기 : 50 
			arr[(int) (Math.random() * 101)]++;	// 0 ~ 100
		}
		
		for(int i = 0; i < arr.length; i++) {
			
			while(arr[i]-- > 0) {	// arr 값이 0보타 클 경우 
				System.out.print(i + " ");
			}
		}
	}
 
}