๐Ÿ“Š ํŒŒ์ด์ฌ์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” Quick-Sort

(history)
Table of Contents

    quick sort๋Š” ๋ง ๊ทธ๋Œ€๋กœ ๋น ๋ฅธ ์ •๋ ฌ์„ ์˜๋ฏธํ•œ๋‹ค. ํฐ ๋ฌธ์ œ๋ฅผ ์ชผ๊ฐœ ์ž‘์€ ๋ฌธ์ œ๋กœ ๋งŒ๋“ค์–ด์„œ ์ •๋ณตํ•˜๋Š” divide-and-conquer ํŒจ๋Ÿฌ๋‹ค์ž„์— ๋ฐ”ํƒ•์„ ๋‘๊ณ  ์žˆ์–ด ํผํฌ๋จผ์Šค๊ฐ€ ์ข‹๋‹ค.

    ํ€ต ์†ŒํŠธ ๋งค์ปค๋‹ˆ์ฆ˜. ํฌ๊ฒŒ 5๋‹จ๊ณ„. https://idea-instructions.com/quick-sort/

    ๊ธฐ๋ณธ์ ์ธ ๋งค์ปค๋‹ˆ์ฆ˜์€ ๊ทธ๋ฆฌ ์–ด๋ ต์ง€ ์•Š๋‹ค.

    1. ๋ฆฌ์ŠคํŠธ์—์„œ ๊ฐ’ ํ•˜๋‚˜๋ฅผ ๊ณจ๋ผ pivot์œผ๋กœ ์ •ํ•œ๋‹ค.
    2. pivot๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ pivot์˜ ์™ผ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค.
    3. pivot๋ณด๋‹ค ํฐ ๊ฒƒ์€ pivot์˜ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค.
    4. pivot์˜ ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ๋˜ pivot์„ ์ •ํ•˜๊ณ , pivot๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ ์™ผ์ชฝ, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ์ด๋™ํ•˜๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
    5. pivot์˜ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ๋˜ pivot์„ ์ •ํ•˜๊ณ  pivot๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ ์™ผ์ชฝ, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ์ด๋™ํ•˜๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

    ์œ„ ๊ณผ์ •์„ ์žฌ๊ท€์ ์œผ๋กœ ๋ฐ˜๋ณตํ•˜๋ฉด ๋ฆฌ์ŠคํŠธ์˜ ๊ฐ’๋“ค์ด ์ •๋ ฌ๋œ๋‹ค. ๋‹จ๊ณ„์ ์œผ๋กœ ์‚ดํŽด๋ณด๋ฉด ์ด๋ ‡๋‹ค.

    # input
    [85, 24, 63, 45, 17, 31, 96, 50]
    
    # 50์„ pivot์œผ๋กœ ์ •ํ•œ๋‹ค.
    [85, 24, 63, 45, 17, 31, 96, "50"]
    
    # pivot(50)๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ pivot์˜ ์™ผ์ชฝ์œผ๋กœ, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค. 
    [24, 45, 17, 31, "50", 85, 63, 96]
    
    # pivot(50)์˜ ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค๊ณ , 31์„ pivot์œผ๋กœ ์ •ํ•œ๋‹ค.
    [_, _, _, _, "50", 85, 63, 96]
    [24, 45, 17, "31"]
    
    # pivot(31)๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ pivot(31)์˜ ์™ผ์ชฝ์œผ๋กœ, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค.
    [_, _, _, _, "50", 85, 63, 96]
    [24, 17, "31", 45]
    
    # pivot(31)์˜ ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค๊ณ , 17์„ pivot์œผ๋กœ ์ •ํ•œ๋‹ค.
    [_, _, _, _, "50", 85, 63, 96]
    [_, _, "31", 45]
    [24, "17"]
    
    # pivot(17)๋ณด๋‹ค ์ž‘์€ ๊ฒƒ์€ pivot(17)์˜ ์™ผ์ชฝ์œผ๋กœ, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ณด๋‚ธ๋‹ค.
    [_, _, _, _, "50", 85, 63, 96]
    [_, _, "31", 45]
    ["17", 24]
    
    # pivot(17)์˜ ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ ๋‹ค. (์™ผ์ชฝ์— ๊ฐ’์ด ์—†์œผ๋ฏ€๋กœ ํŒจ์Šค)
    [_, _, _, _, "50", 85, 63, 96]
    [_, _, "31", 45]
    ["17", 24]
    []
    
    # pivot(17)์˜ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ ๋‹ค. (๊ฐ’์ด ํ•˜๋‚˜์ด๋ฏ€๋กœ ํŒจ์Šค)
    [_, _, _, _, "50", 85, 63, 96]
    [_, _, "31", 45]
    ["17", _]
    [] [24]
    
    # ๋ฆฌ์ŠคํŠธ๋ฅผ pivot(17) ์˜ค๋ฅธ์ชฝ์— ๋„ฃ๋Š”๋‹ค. (ํ˜ธ์ถœํ•œ ๊ฐ’์ด return๋˜๋Š” ๊ณผ์ •)
    [_, _, _, _, "50", 85, 63, 96]
    [_, _, "31", 45]
    ["17", 24]
    [] [_]
    
    # ๋ฆฌ์ŠคํŠธ๋ฅผ pivot(31) ์™ผ์ชฝ์— ๋„ฃ๋Š”๋‹ค. (ํ˜ธ์ถœํ•œ ๊ฐ’์ด return๋˜๋Š” ๊ณผ์ •)
    [_, _, _, _, "50", 85, 63, 96]
    [17, 24, "31", 45]
    [_, _]
    [] [_]
    
    # pivot(31)์˜ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋“ค๋กœ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ ๋‹ค. (๊ฐ’์ด ํ•˜๋‚˜์ด๋ฏ€๋กœ ํŒจ์Šค)
    [_, _, _, _, "50", 85, 63, 96]
    [17, 24, "31", 45]
    [_, _] [45]
    [] [_]
    
    # ๋ฆฌ์ŠคํŠธ๋ฅผ pivot(31) ์˜ค๋ฅธ์ชฝ์— ๋„ฃ๋Š”๋‹ค. (ํ˜ธ์ถœํ•œ ๊ฐ’์ด return๋˜๋Š” ๊ณผ์ •)
    [_, _, _, _, "50", 85, 63, 96]
    [17, 24, "31", 45]
    [_, _] [_]
    [] [_]
    
    # ๋ฆฌ์ŠคํŠธ๋ฅผ pivot(50) ์™ผ์ชฝ์— ๋„ฃ๋Š”๋‹ค. (ํ˜ธ์ถœํ•œ ๊ฐ’์ด return๋˜๋Š” ๊ณผ์ •)
    [17, 24, 31, 45, "50", 85, 63, 96]
    [_, _, _, _]
    [_, _] [_]
    [] [_]
    
    # ์œ„ ๊ณผ์ •์„ pivot(50)์˜ ์˜ค๋ฅธ์ชฝ ๋ฆฌ์ŠคํŠธ์— ๋Œ€ํ•ด ๋ฐ˜๋ณตํ•œ๋‹ค.
    [17, 24, 31, 45, "50", 63, 85, 96]
    [_, _, _, _]   [_, _, _]
    [_, _] [_] [_, _] []
    [] [_] [_] []
    
    # output
    [17, 24, 31, 45, 50, 63, 85, 96]
    

    ์—ฌ๊ธฐ์„œ๋Š” ๋ฆฌ์ŠคํŠธ์˜ ๋งˆ์ง€๋ง‰ ๊ฐ’์„ ํ•ญ์ƒ pivot์œผ๋กœ ์ •ํ–ˆ์ง€๋งŒ, randomํ•˜๊ฒŒ pivot์„ ์ •ํ•  ์ˆ˜๋„ ์žˆ๊ณ , ์ค‘์•™๊ฐ’์„ pivot์œผ๋กœ ์ •ํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ์ค‘์•™๊ฐ’์„ pivot์œผ๋กœ ์ •ํ•˜๋Š” ์ •๋ ฌ ๊ณผ์ •์„ ์‹œ๊ฐํ™”ํ•˜๋ฉด ์ด ์˜์ƒ์ฒ˜๋Ÿผ ๋ณด์ธ๋‹ค. (quick sort๋ฅผ ์ดํ•ดํ•˜๋Š” ๋ฐ ๋ณ„๋กœ ๋„์›€์€ ์•ˆ ๋˜์ง€๋งŒ ์žฌ๋ฐŒ๋‹ค.)

    ๊ทธ๋ฆฌ๊ณ  ์ข€ ๋” ์ตœ์ ํ™”๋œ ๋ฐฉ๋ฒ•์œผ๋กœ inplace quick sort๋ฅผ ์“ธ ์ˆ˜ ์žˆ๋‹ค. inplace ๋ฐฉ์‹์€ pivot์„ ์ •ํ•˜๊ณ  ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ฐ’๋“ค์„ ์ด๋™์‹œํ‚ค๋Š” ๊ณผ์ •์„ ๊ฐœ์„ ํ•œ ๊ฒƒ์ด๋‹ค.

    1. ๋จผ์ € ์™ผ์ชฝ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ์ธ๋ฑ์Šค l๊ณผ ์˜ค๋ฅธ์ชฝ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ์ธ๋ฑ์Šค r์„ ๋งŒ๋“ ๋‹ค.
    2. l์€ pivot๋ณด๋‹ค ํฐ ๊ฐ’์„ ๋งŒ๋‚˜๋ฉด ์ •์ง€ํ•˜๊ณ , r์€ pivot๋ณด๋‹ค ์ž‘์€ ๊ฐ’์„ ๋งŒ๋‚˜๋ฉด ์ •์ง€ํ•œ๋‹ค.
    3. ๋‘ ์ธ๋ฑ์Šค๊ฐ€ ๋ชจ๋‘ ์ •์ง€ํ•˜๋ฉด ๊ฐ’์„ ๊ต์ฒดํ•œ๋‹ค.
    4. ์ด ๊ณผ์ •์„ l๊ณผ r์ด ๊ฐ™์•„์งˆ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค.

    ์ด๋Ÿฐ ์‹์œผ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ๋” ์ ์€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

    # pivot = 50
    # l = 85, r = 96, (l > pivot)
    ["85", 24, 63, 45, 17, 31, "96", "50"]
    
    # l = 85, r = 31, (l > pivot) (r < pivot)
    ["85", 24, 63, 45, 17, "31", 96, "50"]
    
    # l๊ณผ r์„ ๊ต์ฒด
    ["31", 24, 63, 45, 17, "85", 96, "50"]
    
    # l = 24, r = 17, (r < pivot)
    [31, "24", 63, 45, "17", 85, 96, "50"]
    
    # l = 63, r = 17 (l > pivot) (r < pivot)
    [31, 24, "63", 45, "17", 85, 96, "50"]
    
    # l๊ณผ r์„ ๊ต์ฒด
    [31, 24, "17", 45, "63", 85, 96, "50"]
    
    # l = 45, r = 45 (l == r)
    [31, 24, 17, "45", 63, 85, 96, "50"]
    
    # l(45)๊ณผ r(45)์ด pivot๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฏ€๋กœ l += 1
    # l = 63, r = 45
    [31, 24, 17, "45", "63", 85, 96, "50"]
    
    # l๊ณผ pivot์„ ๊ต์ฒด
    [31, 24, 17, 45, "50", 85, 96, 63]
    

    ํŒŒ์ด์ฌ์œผ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

    def quick_sort(S, a, b):
      if a >= b:
        return
    
      pivot = S[b]
      left = a
      right = b - 1
    
      while left <= right:
        while left <= right and S[left] < pivot:
          left += 1
    
        while left <= right and pivot < S[right]:
          right -= 1
    
        if left <= right:
          S[left], S[right] = S[right], S[left]
          left, right = left + 1, right - 1
    
      S[left], S[b] = S[b], S[left]
    
      quick_sort(S, a, left - 1)
      quick_sort(S, left + 1, b)
    

    ์ด๋ฏธ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ quick sort๋กœ ์ •๋ ฌํ•˜๋Š” ๊ฒฝ์šฐ O(n2)O(n^2) ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์ฆ‰, worst case์—์„œ O(n2)O(n^2) ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค๋Š” ๋ง์ด๋‹ค. ์žฌ๋ฐŒ๋Š” ๊ฒƒ์€ average case์—์„œ๋„ O(nlogโกn)O(n \log n) ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋Š”๋ฐ, ์ด๋Š” quick sort๋ผ๋Š” ์ด๋ฆ„์ด ๋ถ™์„ ์ •๋„๋กœ ๋น ๋ฅธ ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค. ๊ทธ๋Ÿผ์—๋„ quick sort์ธ ์ด์œ ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์บ์‹œ hit ratio๊ฐ€ ๋†’๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. (์ปดํ“จํ„ฐ ์•„ํ‚คํ…์ฒ˜์— ๊ด€ํ•œ ๋ถ€๋ถ„์ด๋‹ค.) ๊ทธ๋ž˜์„œ ์ด๋ก ์ ์œผ๋กœ๋Š” ํ‰๊ท  O(nlogโกn)O(n \log n)์ด์ง€๋งŒ ์‹ค์ œ๋กœ๋Š” ๋” ๋น ๋ฅด๊ฒŒ ์ •๋ ฌ๋œ๋‹ค.

    ๏ผœ

    ๐Ÿง ์œˆ๋„์šฐ์—์„œ ์šฐ๋ถ„ํˆฌ ๋Œ๋ฆฌ๊ธฐ

    ๊ฐœ๋ฐœ์„ ์œ„ํ•œ WSL ์„ธํŒ…

    ๏ผž

    Java Design Pattern: Singleton

    ๐Ÿ“š