Skip to content

Latest commit

ย 

History

History
99 lines (70 loc) ยท 3.37 KB

Sort_Radix.md

File metadata and controls

99 lines (70 loc) ยท 3.37 KB

Comparison Sort


N๊ฐœ ์›์†Œ์˜ ๋ฐฐ์—ด์ด ์žˆ์„ ๋•Œ, ์ด๋ฅผ ๋ชจ๋‘ ์ •๋ ฌํ•˜๋Š” ๊ฐ€์ง“์ˆ˜๋Š” N!์ž„

๋”ฐ๋ผ์„œ, Comparison Sort๋ฅผ ํ†ตํ•ด ์ƒ๊ธฐ๋Š” ํŠธ๋ฆฌ์˜ ๋ง๋‹จ ๋…ธ๋“œ๊ฐ€ N! ์ด์ƒ์˜ ๋…ธ๋“œ ๊ฐฏ์ˆ˜๋ฅผ ๊ฐ–๊ธฐ ์œ„ํ•ด์„œ๋Š”, 2^h >= N! ๋ฅผ ๋งŒ์กฑํ•˜๋Š” h๋ฅผ ๊ฐ€์ ธ์•ผ ํ•˜๊ณ , ์ด ์‹์„ h > O(nlgn)์„ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค. (h๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด,,, ์ฆ‰ Comparison sort์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„์ž„)

์ด๋Ÿฐ O(nlgn)์„ ์ค„์ผ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ Comparison์„ ํ•˜์ง€ ์•Š๋Š” ๊ฒƒ

Radix sort


๋ฐ์ดํ„ฐ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๊ธฐ๋ณธ ์š”์†Œ (Radix) ๋ฅผ ์ด์šฉํ•˜์—ฌ ์ •๋ ฌ์„ ์ง„ํ–‰ํ•˜๋Š” ๋ฐฉ์‹

์ž…๋ ฅ ๋ฐ์ดํ„ฐ์˜ ์ตœ๋Œ€๊ฐ’์— ๋”ฐ๋ผ์„œ Counting Sort์˜ ๋น„ํšจ์œจ์„ฑ์„ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•ด์„œ, Radix Sort๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Œ.

์ž๋ฆฟ์ˆ˜์˜ ๊ฐ’ ๋ณ„๋กœ (์˜ˆ) ๋‘˜์งธ ์ž๋ฆฌ, ์ฒซ์งธ ์ž๋ฆฌ) ์ •๋ ฌ์„ ํ•˜๋ฏ€๋กœ, ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ฐ’์˜ ์ตœ๋Œ€ ์‚ฌ์ด์ฆˆ๋Š” 9์ž„ (๋ฒ”์œ„ : 0 ~ 9)

  • ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(d * (n + b))

    -> d๋Š” ์ •๋ ฌํ•  ์ˆซ์ž์˜ ์ž๋ฆฟ์ˆ˜, b๋Š” 10 (k์™€ ๊ฐ™์œผ๋‚˜ 10์œผ๋กœ ๊ณ ์ •๋˜์–ด ์žˆ๋‹ค.)

    ( Counting Sort์˜ ๊ฒฝ์šฐ : O(n + k) ๋กœ ๋ฐฐ์—ด์˜ ์ตœ๋Œ“๊ฐ’ k์— ์˜ํ–ฅ์„ ๋ฐ›์Œ )

  • ์žฅ์  : ๋ฌธ์ž์—ด, ์ •์ˆ˜ ์ •๋ ฌ ๊ฐ€๋Šฅ

  • ๋‹จ์  : ์ž๋ฆฟ์ˆ˜๊ฐ€ ์—†๋Š” ๊ฒƒ์€ ์ •๋ ฌํ•  ์ˆ˜ ์—†์Œ. (๋ถ€๋™ ์†Œ์ˆซ์ )

    ์ค‘๊ฐ„ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•  bucket ๊ณต๊ฐ„์ด ํ•„์š”ํ•จ.

์†Œ์Šค ์ฝ”๋“œ

void countSort(int arr[], int n, int exp) {
	int buffer[n];
    int i, count[10] = {0};
    
    // exp์˜ ์ž๋ฆฟ์ˆ˜์— ํ•ด๋‹นํ•˜๋Š” count ์ฆ๊ฐ€
    for (i = 0; i < n; i++){
        count[(arr[i] / exp) % 10]++;
    }
    // ๋ˆ„์ ํ•ฉ ๊ตฌํ•˜๊ธฐ
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // ์ผ๋ฐ˜์ ์ธ Counting sort ๊ณผ์ •
    for (i = n - 1; i >= 0; i--) {
        buffer[count[(arr[i]/exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (i = 0; i < n; i++){
        arr[i] = buffer[i];
    }
}

void radixsort(int arr[], int n) {
     // ์ตœ๋Œ“๊ฐ’ ์ž๋ฆฌ๋งŒํผ ๋Œ๊ธฐ
    int m = getMax(arr, n);
    
    // ์ตœ๋Œ“๊ฐ’์„ ๋‚˜๋ˆด์„ ๋•Œ, 0์ด ๋‚˜์˜ค๋ฉด ๋ชจ๋“  ์ˆซ์ž๊ฐ€ exp์˜ ์•„๋ž˜
    for (int exp = 1; m / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);			// ์ข‹์€ ์Šต๊ด€
    radixsort(arr, n);
    
    for (int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

์งˆ๋ฌธ


Q1) ์™œ ๋‚ฎ์€ ์ž๋ฆฌ์ˆ˜๋ถ€ํ„ฐ ์ •๋ ฌ์„ ํ•ฉ๋‹ˆ๊นŒ?

MSD (Most-Significant-Digit) ๊ณผ LSD (Least-Significant-Digit)์„ ๋น„๊ตํ•˜๋ผ๋Š” ์งˆ๋ฌธ

MSD๋Š” ๊ฐ€์žฅ ํฐ ์ž๋ฆฌ์ˆ˜๋ถ€ํ„ฐ Counting sort ํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•˜๊ณ , LSD๋Š” ๊ฐ€์žฅ ๋‚ฎ์€ ์ž๋ฆฌ์ˆ˜๋ถ€ํ„ฐ Counting sort ํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•จ. (์ฆ‰, ๋‘˜ ๋‹ค ํ•  ์ˆ˜ ์žˆ์Œ)

  • LSD์˜ ๊ฒฝ์šฐ 1600000 ๊ณผ 1์„ ๋น„๊ตํ•  ๋•Œ, Digit์˜ ๊ฐฏ์ˆ˜๋งŒํผ ๋”ฐ์ ธ์•ผํ•˜๋Š” ๋‹จ์ ์ด ์žˆ์Œ. ๊ทธ์— ๋ฐ˜ํ•ด MSD๋Š” ๋งˆ์ง€๋ง‰ ์ž๋ฆฌ์ˆ˜๊นŒ์ง€ ํ™•์ธํ•ด ๋ณผ ํ•„์š”๊ฐ€ ์—†์Œ.
  • LSD๋Š” ์ค‘๊ฐ„์— ์ •๋ ฌ ๊ฒฐ๊ณผ๋ฅผ ์•Œ ์ˆ˜ ์—†์Œ. (์˜ˆ) 10004์™€ 70002์˜ ๋น„๊ต) ๋ฐ˜๋ฉด, MSD๋Š” ์ค‘๊ฐ„์— ์ค‘์š”ํ•œ ์ˆซ์ž๋ฅผ ์•Œ ์ˆ˜ ์žˆ์Œ. ๋”ฐ๋ผ์„œ ์‹œ๊ฐ„์„ ์ค„์ผ ์ˆ˜ ์žˆ์Œ. ๊ทธ๋Ÿฌ๋‚˜, ์ •๋ ฌ์ด ๋˜์—ˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๊ณผ์ •์ด ํ•„์š”ํ•˜๊ณ , ์ด ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋” ์‚ฌ์šฉ
  • LSD๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ผ๊ด€๋จ (Branch Free algorithm) ๊ทธ๋Ÿฌ๋‚˜ MSD๋Š” ์ผ๊ด€๋˜์ง€ ๋ชปํ•จ. --> ๋”ฐ๋ผ์„œ Radix sort๋Š” ์ฃผ๋กœ LSD๋ฅผ ์–ธ๊ธ‰ํ•จ.
  • LSD๋Š” ์ž๋ฆฟ์ˆ˜๊ฐ€ ์ •ํ•ด์ง„ ๊ฒฝ์šฐ ์ข€ ๋” ๋น ๋ฅผ ์ˆ˜ ์žˆ์Œ.