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

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

ํ€ต ์†ŒํŠธ ๋งค์ปค๋‹ˆ์ฆ˜. ํฌ๊ฒŒ 5๋‹จ๊ณ„.

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

  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)์ด์ง€๋งŒ ์‹ค์ œ๋กœ๋Š” ๋” ๋น ๋ฅด๊ฒŒ ์ •๋ ฌ๋œ๋‹ค.