# ํ€ต ์ •๋ ฌ(Quick Sort)


# Goal


  • Quick Sort์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Quick Sort ๊ณผ์ •์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Quick Sort์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Quick Sort์˜ ์‹œ๊ฐ„๋ณต์žก๋„์™€ ๊ณต๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Quick Sort์˜ ์ตœ์•…์ธ ๊ฒฝ์šฐ๋ฅผ ๊ฐœ์„ ์‹œํ‚ฌ ์ˆ˜ ์žˆ๋‹ค.

# Abstract


Quick Sort์€ ๋ถ„ํ•  ์ •๋ณต(divide and conquer) ๋ฐฉ๋ฒ• ์„ ํ†ตํ•ด ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ ์ •๋ ฌํ•œ๋‹ค.

* [๋ถ„ํ•  ์ •๋ณต(divide and conquer) ๋ฐฉ๋ฒ•]
๋ฌธ์ œ๋ฅผ ์ž‘์€ 2๊ฐœ์˜ ๋ฌธ์ œ๋กœ ๋ถ„๋ฆฌํ•˜๊ณ  ๊ฐ๊ฐ์„ ํ•ด๊ฒฐํ•œ ๋‹ค์Œ, ๊ฒฐ๊ณผ๋ฅผ ๋ชจ์•„์„œ ์›๋ž˜์˜ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ์ „๋žต์ด๋‹ค.

Quick Sort์€ ๋ถˆ์•ˆ์ • ์ •๋ ฌ์— ์†ํ•˜๋ฉฐ, ๋‹ค๋ฅธ ์›์†Œ์™€์˜ ๋น„๊ต๋งŒ์œผ๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋น„๊ต ์ •๋ ฌ์— ์†ํ•œ๋‹ค. ๋˜ํ•œ Merge Sort์™€ ๋‹ฌ๋ฆฌ Quick Sort๋Š” ๋ฐฐ์—ด์„ ๋น„๊ท ๋“ฑํ•˜๊ฒŒ ๋ถ„ํ• ํ•œ๋‹ค.

# Process (Ascending)


  1. ๋ฐฐ์—ด ๊ฐ€์šด๋ฐ์„œ ํ•˜๋‚˜์˜ ์›์†Œ๋ฅผ ๊ณ ๋ฅธ๋‹ค. ์ด๋ ‡๊ฒŒ ๊ณ ๋ฅธ ์›์†Œ๋ฅผ ํ”ผ๋ฒ—(pivot) ์ด๋ผ๊ณ  ํ•œ๋‹ค.
  2. ํ”ผ๋ฒ— ์•ž์—๋Š” ํ”ผ๋ฒ—๋ณด๋‹ค ๊ฐ’์ด ์ž‘์€ ๋ชจ๋“  ์›์†Œ๋“ค์ด ์˜ค๊ณ , ํ”ผ๋ฒ— ๋’ค์—๋Š” ํ”ผ๋ฒ—๋ณด๋‹ค ๊ฐ’์ด ํฐ ๋ชจ๋“  ์›์†Œ๋“ค์ด ์˜ค๋„๋ก ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ๋ฐฐ์—ด์„ ๋‘˜๋กœ ๋‚˜๋ˆˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๋ฐฐ์—ด์„ ๋‘˜๋กœ ๋‚˜๋ˆ„๋Š” ๊ฒƒ์„ ๋ถ„ํ• (Divide) ์ด๋ผ๊ณ  ํ•œ๋‹ค. ๋ถ„ํ• ์„ ๋งˆ์นœ ๋’ค์— ํ”ผ๋ฒ—์€ ๋” ์ด์ƒ ์›€์ง์ด์ง€ ์•Š๋Š”๋‹ค.
  3. ๋ถ„ํ• ๋œ ๋‘ ๊ฐœ์˜ ์ž‘์€ ๋ฐฐ์—ด์— ๋Œ€ํ•ด ์žฌ๊ท€(Recursion)์ ์œผ๋กœ ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
  • ์žฌ๊ท€ ํ˜ธ์ถœ์ด ํ•œ๋ฒˆ ์ง„ํ–‰๋  ๋•Œ๋งˆ๋‹ค ์ตœ์†Œํ•œ ํ•˜๋‚˜์˜ ์›์†Œ๋Š” ์ตœ์ข…์ ์œผ๋กœ ์œ„์น˜๊ฐ€ ์ •ํ•ด์ง€๋ฏ€๋กœ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฐ˜๋“œ์‹œ ๋๋‚œ๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋‹ค.

# Java Code (Ascending)


ํ€ต ์ •๋ ฌ์€ ๋‹ค์Œ์˜ ๋‹จ๊ณ„๋“ค๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค.

  • ์ •๋ณต (Conquer)

    ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ์ •๋ ฌํ•œ๋‹ค. ๋ถ€๋ถ„ ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๊ฐ€ ์ถฉ๋ถ„ํžˆ ์ž‘์ง€ ์•Š์œผ๋ฉด ์ˆœํ™˜ ํ˜ธ์ถœ์„ ์ด์šฉํ•˜์—ฌ ๋‹ค์‹œ ๋ถ„ํ•  ์ •๋ณต ๋ฐฉ๋ฒ•์„ ์ ์šฉํ•œ๋‹ค.

    public void quickSort(int[] array, int left, int right) {
        if(left >= right) return;
        
        // ๋ถ„ํ•  
        int pivot = partition(); 
        
        // ํ”ผ๋ฒ—์€ ์ œ์™ธํ•œ 2๊ฐœ์˜ ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ๋Œ€์ƒ์œผ๋กœ ์ˆœํ™˜ ํ˜ธ์ถœ
        quickSort(array, left, pivot-1);  // ์ •๋ณต(Conquer)
        quickSort(array, pivot+1, right); // ์ •๋ณต(Conquer)
    }
    
  • ๋ถ„ํ•  (Divide)

    ์ž…๋ ฅ ๋ฐฐ์—ด์„ ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ๋น„๊ท ๋“ฑํ•˜๊ฒŒ 2๊ฐœ์˜ ๋ถ€๋ถ„ ๋ฐฐ์—ด (ํ”ผ๋ฒ—์„ ์ค‘์‹ฌ์œผ๋กœ ์™ผ์ชฝ : ํ”ผ๋ฒ—๋ณด๋‹ค ์ž‘์€ ์š”์†Œ๋“ค, ์˜ค๋ฅธ์ชฝ : ํ”ผ๋ฒ—๋ณด๋‹ค ํฐ ์š”์†Œ๋“ค) ๋กœ ๋ถ„ํ• ํ•œ๋‹ค.

    public int partition(int[] array, int left, int right) {
        /**
        // ์ตœ์•…์˜ ๊ฒฝ์šฐ, ๊ฐœ์„  ๋ฐฉ๋ฒ•
        int mid = (left + right) / 2;
        swap(array, left, mid);
        */
        
        int pivot = array[left]; // ๊ฐ€์žฅ ์™ผ์ชฝ๊ฐ’์„ ํ”ผ๋ฒ—์œผ๋กœ ์„ค์ •
        int i = left, j = right;
        
        while(i < j) {
            while(pivot < array[j]) {
                j--;
            }
            while(i < j && pivot >= array[i]){
                i++;
            }
            swap(array, i, j);
        }
        array[left] = array[i];
        array[i] = pivot;
        
        return i;
    }
    

# Quick Sort ๊ฐœ์„ 


partition() ํ•จ์ˆ˜์—์„œ ํ”ผ๋ฒ— ๊ฐ’์ด ์ตœ์†Œ๋‚˜ ์ตœ๋Œ€๊ฐ’์œผ๋กœ ์ง€์ •๋˜์–ด ํŒŒํ‹ฐ์…˜์ด ๋‚˜๋ˆ„์–ด์ง€์ง€ ์•Š์•˜์„ ๋•Œ, O(n^2)์— ๋Œ€ํ•œ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

์ฆ‰, ์ •๋ ฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฐฐ์—ด์ด ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ๋˜์–ด์žˆ์œผ๋ฉด O(n^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค. ์ด๋•Œ, ๋ฐฐ์—ด์—์„œ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ๊ฐ’๊ณผ ์ค‘๊ฐ„๊ฐ’์„ ๊ตํ™˜ํ•ด์ค€๋‹ค๋ฉด ํ™•๋ฅ ์ ์œผ๋กœ๋‚˜๋งˆ ์‹œ๊ฐ„๋ณต์žก๋„ O(nlogโ‚‚n)์œผ๋กœ ๊ฐœ์„ ํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, ์ด ๋ฐฉ๋ฒ•์œผ๋กœ ๊ฐœ์„ ํ•œ๋‹คํ•ด๋„ Quick Sort์˜ ์ตœ์•…์˜ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(nlogโ‚‚n)๊ฐ€ ๋˜๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค.


# GIF๋กœ ์ดํ•ดํ•˜๋Š” Quick Sort


img (opens new window)



# ์‹œ๊ฐ„๋ณต์žก๋„


# ์ตœ์„ ์˜ ๊ฒฝ์šฐ(Best cases) : T(n) = O(nlogโ‚‚n)

  • ๋น„๊ต ํšŸ์ˆ˜ (logโ‚‚n)

    ๋ ˆ์ฝ”๋“œ์˜ ๊ฐœ์ˆ˜ n์ด 2์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ์ด๋ผ๊ณ  ๊ฐ€์ •(n=2^k) ํ–ˆ์„ ๋•Œ, n=2^3์˜ ๊ฒฝ์šฐ, 2^3 -> 2^2 -> 2^1 -> 2^0 ์ˆœ์œผ๋กœ ์ค„์–ด๋“ค์–ด ์ˆœํ™˜ ํ˜ธ์ถœ์˜ ๊นŠ์ด๊ฐ€ 3์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

    img

    ์ด๊ฒƒ์„ ์ผ๋ฐ˜ํ™”ํ•˜๋ฉด n=2^k์˜ ๊ฒฝ์šฐ, k(k=logโ‚‚n) ์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

  • ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ ๋‹จ๊ณ„์˜ ๋น„๊ต ์—ฐ์‚ฐ (n)

    ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ์—์„œ๋Š” ์ „์ฒด ๋ฆฌ์ŠคํŠธ์˜ ๋Œ€๋ถ€๋ถ„์˜ ๋ ˆ์ฝ”๋“œ๋ฅผ ๋น„๊ตํ•ด์•ผ ํ•˜๋ฏ€๋กœ ํ‰๊ท  n๋ฒˆ ์ •๋„์˜ ๋น„๊ต๊ฐ€ ์ด๋ฃจ์–ด์ง„๋‹ค.

๋”ฐ๋ผ์„œ, ์ตœ์„ ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ์ˆœํ™˜ ํ˜ธ์ถœ์˜ ๊นŠ์ด * ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ ๋‹จ๊ณ„์˜ ๋น„๊ต ์—ฐ์‚ฐ = nlogโ‚‚n ๊ฐ€ ๋œ๋‹ค. ์ด๋™ ํšŸ์ˆ˜๋Š” ๋น„๊ต ํšŸ์ˆ˜๋ณด๋‹ค ์ ์œผ๋ฏ€๋กœ ๋ฌด์‹œํ•  ์ˆ˜ ์žˆ๋‹ค.


# ์ตœ์•…์˜ ๊ฒฝ์šฐ(Worst cases) : T(n) = O(n^2)

์ตœ์•…์˜ ๊ฒฝ์šฐ๋Š” ์ •๋ ฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฐฐ์—ด์ด ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ๋˜์–ด์žˆ๋Š” ๊ฒฝ์šฐ๋‹ค.

  • ๋น„๊ต ํšŸ์ˆ˜ (n)

    img

    ๋ ˆ์ฝ”๋“œ์˜ ๊ฐœ์ˆ˜ n์ด 2์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ์ด๋ผ๊ณ  ๊ฐ€์ •(n=2^k)ํ–ˆ์„ ๋•Œ, ์ˆœํ™˜ ํ˜ธ์ถœ์˜ ๊นŠ์ด๋Š” n ์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

  • ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ ๋‹จ๊ณ„์˜ ๋น„๊ต ์—ฐ์‚ฐ (n)

    ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ์—์„œ๋Š” ์ „์ฒด ๋ฆฌ์ŠคํŠธ์˜ ๋Œ€๋ถ€๋ถ„์˜ ๋ ˆ์ฝ”๋“œ๋ฅผ ๋น„๊ตํ•ด์•ผ ํ•˜๋ฏ€๋กœ **ํ‰๊ท  n๋ฒˆ ** ์ •๋„์˜ ๋น„๊ต๊ฐ€ ์ด๋ฃจ์–ด์ง„๋‹ค.

๋”ฐ๋ผ์„œ, ์ตœ์•…์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ์ˆœํ™˜ ํ˜ธ์ถœ์˜ ๊นŠ์ด * ๊ฐ ์ˆœํ™˜ ํ˜ธ์ถœ ๋‹จ๊ณ„์˜ ๋น„๊ต ์—ฐ์‚ฐ = n^2 ๋‹ค. ์ด๋™ ํšŸ์ˆ˜๋Š” ๋น„๊ต ํšŸ์ˆ˜๋ณด๋‹ค ์ ์œผ๋ฏ€๋กœ ๋ฌด์‹œํ•  ์ˆ˜ ์žˆ๋‹ค.


# ํ‰๊ท ์˜ ๊ฒฝ์šฐ(Average cases) : T(n) = O(nlogโ‚‚n)


# ๊ณต๊ฐ„๋ณต์žก๋„


์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜(swap)์„ ํ†ตํ•ด, ์ •๋ ฌ์ด ์ˆ˜ํ–‰๋˜๋ฏ€๋กœ **O(n)**์ด๋‹ค.


# ์žฅ์ 


  • ๋ถˆํ•„์š”ํ•œ ๋ฐ์ดํ„ฐ์˜ ์ด๋™์„ ์ค„์ด๊ณ  ๋จผ ๊ฑฐ๋ฆฌ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๊ตํ™˜ํ•  ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ, ํ•œ ๋ฒˆ ๊ฒฐ์ •๋œ ํ”ผ๋ฒ—๋“ค์ด ์ถ”ํ›„ ์—ฐ์‚ฐ์—์„œ ์ œ์™ธ๋˜๋Š” ํŠน์„ฑ ๋•Œ๋ฌธ์—, ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(nlogโ‚‚n)๋ฅผ ๊ฐ€์ง€๋Š” ๋‹ค๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋น„๊ตํ–ˆ์„ ๋•Œ๋„ ๊ฐ€์žฅ ๋น ๋ฅด๋‹ค.
  • ์ •๋ ฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜ํ•˜๋Š” ๋ฐฉ์‹์ด๋ฏ€๋กœ, ๋‹ค๋ฅธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ•„์š”๋กœ ํ•˜์ง€ ์•Š๋Š”๋‹ค.

# ๋‹จ์ 


  • ๋ถˆ์•ˆ์ • ์ •๋ ฌ(Unstable Sort) ์ด๋‹ค.
  • ์ •๋ ฌ๋œ ๋ฐฐ์—ด์— ๋Œ€ํ•ด์„œ๋Š” Quick Sort์˜ ๋ถˆ๊ท ํ˜• ๋ถ„ํ• ์— ์˜ํ•ด ์˜คํžˆ๋ ค ์ˆ˜ํ–‰์‹œ๊ฐ„์ด ๋” ๋งŽ์ด ๊ฑธ๋ฆฐ๋‹ค.

# Conclusion


ํ‰๊ท ์ ์œผ๋กœ ๊ฐ€์žฅ ๋น ๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ดค๋‹ค. JAVA์—์„œ Arrays.sort() ๋‚ด๋ถ€์ ์œผ๋กœ๋„ Dual Pivot Quick Sort๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์„ ์ •๋„๋กœ ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๊ณ , ๊ธฐ์ˆ  ๋ฉด์ ‘์—์„œ ์ •๋ง ๋นˆ๋ฒˆํ•˜๊ฒŒ ๋‚˜์˜ค๋Š” ์ฃผ์ œ์ด๋ฏ€๋กœ ๋ฐ˜๋“œ์‹œ ์ˆ™์ง€ํ•˜์ž


# [์ฐธ๊ณ  ์ž๋ฃŒ]

์ตœ์ข… ์ˆ˜์ • : 11/15/2021, 1:31:19 PM