๐Ÿšฉ[Algorithm] 1. ์ •๋ ฌ - ๊ณ„์ˆ˜ ์ •๋ ฌ

NtoZยท2023๋…„ 3์›” 28์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
3/3
post-thumbnail

๊ณ„์ˆ˜์ •๋ ฌ(counting sort)


1. ๊ณ„์ˆ˜์ •๋ ฌ์ด๋ž€?

  • ํŠน์ •ํ•œ ์กฐ๊ฑด์ด ๋ถ€ํ•ฉํ•  ๋•Œ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ๋™์ž‘ํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • <ํŠน์ •ํ•œ ์กฐ๊ฑด> ๊ณ„์ˆ˜ ์ •๋ ฌ์€ ๋ฐ์ดํ„ฐ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋˜์–ด ์ •์ˆ˜ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ ์‚ฌ์šฉ ๊ฐ€๋Šฅํ•˜๋‹ค.

  • ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜๊ฐ€ N, ๋ฐ์ดํ„ฐ(์–‘์ˆ˜) ์ค‘ ์ตœ๋Œ“๊ฐ’์ด K์ผ ๋•Œ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ โญ์ˆ˜ํ–‰ ์‹œ๊ฐ„ O(N+K)๋ฅผ ๋ณด์žฅํ•œ๋‹ค.

  • ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์˜ ๊ฐ’ ๋ฒ”์œ„๊ฐ€ ์ž‘์€ ๊ฒฝ์šฐ ๋น ๋ฅธ ์†๋„๋ฅผ ๊ฐ–๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. โญ์ตœ๋Œ€๊ฐ’๊ณผ ์ž…๋ ฅ ๋ฐฐ์—ด์˜ ์›์†Œ ๊ฐ’ ๊ฐœ์ˆ˜๋ฅผ ๋ˆ„์ ํ•ฉ์œผ๋กœ ๊ตฌ์„ฑํ•œ ๋ฐฐ์—ด๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

  • โญ๊ณ„์ˆ˜ ์ •๋ ฌ์€ ํŠน์ •ํ•œ ์กฐ๊ฑด์ด ๋ถ€ํ•ฉ๋  ๋•Œ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ๋ฐ์ดํ„ฐ ์ˆ˜๊ฐ€ ๋งŽ๋”๋ผ๋„ ์ค‘๋ณต๋œ ๊ฐ’์ด ๋งŽ์ด ๋ถ„ํฌ๋ผ์žˆ๋Š” ๋ฐฐ์—ด์„ ์ •๋ ฌํ•  ๋•Œ ํšจ๊ณผ์ ์ด๊ณ  ๋น ๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ตœ๋Œ€, ์ตœ์†Œ ๊ฐ’ ์ฐจ์ด๊ฐ€ 100๋งŒ ์ดํ•˜์ผ ๊ฒฝ์šฐ ํšจ๊ณผ์ ์ด๋‹ค. ์นด์šดํŒ… ์ •๋ ฌ์ด๋ผ๊ณ  ํ•˜๊ธฐ๋„ ํ•œ๋‹ค. ์„ ํƒ, ์‚ฝ์ž…, ํ€ต ์ •๋ ฌ์ฒ˜๋Ÿผ ๋ฐ์ดํ„ฐ๋ฅผ ๋น„๊ตํ•˜๋ฉฐ ์œ„์น˜๋ฅผ ๋ณ€๊ฒฝํ•˜๋Š” ๋น„๊ต ๊ธฐ๋ฐ˜์˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์•„๋‹ˆ๋‹ค.


2. ๊ณ„์ˆ˜์ •๋ ฌ์˜ ์กฐ๊ฑด

  1. ๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋œ ๊ฒฝ์šฐ
    • ex) 0 ~ 100 ๊นŒ์ง€์˜ ์ ์ˆ˜๋ฅผ ์ •๋ ฌํ•˜๋Š” ๊ฒฝ์šฐ
  2. ๋ฐ์ดํ„ฐ๊ฐ€ ์–‘์˜ ์ •์ˆ˜์ธ ๊ฒฝ์šฐ
    • ๋ฐ์ดํ„ฐ๊ฐ€ ์‹ค์ˆ˜์ธ ๊ฒฝ์šฐ ๋ฌดํ•œ์˜ ๋ฒ”์œ„๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ 1๋ฒˆ ์กฐ๊ฑด์— ๋ถ€ํ•ฉํ•˜์ง€ ๋ชปํ•จ
    • ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•œ๋‹ค๋Š” ๊ฒƒ์ด ํ•ต์‹ฌ์ด๋‹ค.
  3. ๊ฐ€์žฅ ํฐ ๋ฐ์ดํ„ฐ์™€ ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ์˜ ์ฐจ์ด๊ฐ€ 1,000,000(๋ฐฑ๋งŒ)์„ ๋„˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ
    • ํ•„์ˆ˜์ ์ธ ์กฐ๊ฑด์€ ์•„๋‹ˆ์ง€๋งŒ ์ฐจ์ด๊ฐ€ ํด ์ˆ˜๋ก ๋ฉ”๋ชจ๋ฆฌ์˜ ์‚ฌ์šฉ์ด ๋งŽ์•„์ง

3. ์ •๋ ฌ ๊ณผ์ •

โญโญ
1. ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ถ€ํ„ฐ ๊ฐ€์žฅ ํฐ ๋ฐ์ดํ„ฐ๊นŒ์ง€์˜ ๋ฒ”์œ„๊ฐ€ ๋ชจ๋‘ ๋‹ด๊ธธ ์ˆ˜ ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒ์„ฑ
2. ๋ฐ์ดํ„ฐ๋ฅผ ํ•˜๋‚˜์”ฉ ํ™•์ธํ•˜๋ฉฐ ๋ฐ์ดํ„ฐ์˜ ๊ฐ’๊ณผ ๋™์ผํ•œ ์ธ๋ฑ์Šค์˜ ๋ฐ์ดํ„ฐ๋ฅผ 1์”ฉ ์ฆ๊ฐ€
3. ์ฆ๊ฐ€๋œ ๋ฆฌ์ŠคํŠธ์—์„œ 0์ธ ๊ฐ’์„ ์ œ์™ธํ•˜๊ณ , ์ธ๋ฑ์Šค๋ฅผ ์ธ๋ฑ์Šค ๊ฐ’๋งŒํผ ์ถœ๋ ฅ

์ถœ์ฒ˜ : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

์ถœ์ฒ˜ : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

์ถœ์ฒ˜ : https://spagnuolocarmine.github.io/counting-sort.html

์ถœ์ฒ˜ : https://spagnuolocarmine.github.io/counting-sort.html


4. ์ฝ”๋“œ ๊ตฌํ˜„

1) ํŒŒ์ด์ฌ - ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒํ˜•(๋ฐฐ์—ด) ํ™œ์šฉ

def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)	#โญ ๋ฐฐ์—ด์ตœ๋Œ€๊ฐ’+1๋งŒํผ ์ธ๋ฑ์Šค ์š”์†Œ ๋งŒ๋“œ๋Š” ๋™์‹œ์— ๋ฐฐ์—ด ๊ฐ’ 0์œผ๋กœ ์ดˆ๊ธฐํ™”
    sorted_arr = list()	# โญ ๋ฐฐ์—ด๊ฐ์ฒด sorted_arr ์„ ์–ธ
    
    for i in arr:	# โญ์นด์šดํŒ… (๋ฐฐ์—ด์€ 0๋ถ€ํ„ฐ max_arr๊นŒ์ง€ ์กด์žฌํ•˜๋Š” ์ƒํƒœ)
        count[i] += 1

    for i in range(max_arr + 1): # โญ์กด์žฌํ•˜๋Š” ์ธ๋ฑ์Šค 0~max_arr+1๊นŒ์ง€ 
        for _ in range(count[i]):	# โญ ๋”๋ฏธ๋ณ€์ˆ˜ '_'ํ™œ์šฉํ•˜์—ฌ count[i]์— ์ €์žฅ๋œ ๊ฐ’๋งŒํผ ๋ฐ˜๋ณต
            sorted_arr.append(i) # โญ sorted_arr์— i ๋ถ™์ด๊ธฐ
    return sorted_arr # โญ sorted_arr ๋ฐ˜ํ™˜

2) ํŒŒ์ด์ฌ - ๋”•์…”๋„ˆ๋ฆฌ ์ž๋ฃŒํ˜• ํ™œ์šฉ

def counting_sort(arr):
    count = dict()
    sorted_arr = list()
    
    for i in arr:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr
    
 # ๐ŸŒŸ<collections> ๋ชจ๋“ˆ์˜ defaultdict๋ฅผ ํ™œ์šฉ

from collections import defaultdict


def counting_sort(arr):
    count = defaultdict(int)
    sorted_arr = list()
    
    for i in arr:
        count[i] += 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

3) Java - ๋ฐฐ์—ด, ๋ˆ„๊ณ„ ์ถœ๋ ฅ ๋“ฑ

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();
	}
 
}

โญJava - ๋‹จ์ˆœ ์ถœ๋ ฅ

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 + " ");
			}
		}
	}
 
}

<์‹คํ–‰๊ฒฐ๊ณผ>
0 1 6 6 9 10 14 14 16 16 19 21 23 25 25 27 31 36 39 40 40 42 43 46 46 48 49 53 54 55 55 63 66 67 67 68 74 76 76 77 78 79 79 89 91 92 93 96 97 98 

์ถœ์ฒ˜

profile
9์—์„œ 0์œผ๋กœ, ๋ฐฑ์—”๋“œ ๊ฐœ๋ฐœ๋ธ”๋กœ๊ทธ

0๊ฐœ์˜ ๋Œ“๊ธ€