Sep 15, 2019 โ€ข3 min read โ˜•

๐Ÿ’ป Quick Sort, ํ€ต ์ •๋ ฌ์ด๋ž€?

Quick sort๋Š” Divide and Conquer(๋ถ„ํ•  ์ •๋ณต) ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ข…๋ฅ˜์ค‘ ํ•˜๋‚˜์ด๋‹ค. ๋ถ„ํ• ์ •๋ณต์ด๋ž€ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ sub ๋ฌธ์ œ๋“ค๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ์— ๊ทธ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐํ•œ ๋‹ค์Œ์— ํ•ฉ์น˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

Pseudo-code ์„ค๋ช…

Quicksort๋Š” ์ž„์˜์˜ ์ˆซ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •ํ•œ ๋‹ค์Œ์— ๊ทธ ์ˆซ์ž๋ณด๋‹ค ์ž‘์€ ์ˆซ์ž๋“ค๊ณผ ํฐ ์ˆซ์ž๋“ค์— ๋‹ค์‹œ ์žฌ๊ท€๋ฅผ ์‚ฌ์šฉํ•ด์„œ quick sort ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๋‹ค์‹œ ๊ทธ ๋ถ„ํ• ๋œ ์ˆซ์ž๋“ค ์ค‘์—์„œ ๊ธฐ์ค€์„ ์ •ํ•˜๊ณ  ๋‚˜๋ˆ ์„œ quick sort๋ฅผ ์ง„ํ–‰ํ•œ๋‹ค. ์กฐ๊ธˆ ๋” ์ž์„ธํžˆ ์„ค๋ช…ํ•˜๋ฉด, ์ž„์˜์˜ ์ˆซ์ž๋ฅผ ๊ณ ๋ฅด๊ณ  ๋‚˜์„œ ํ•ด๋‹น ์ˆซ์ž๋ณด๋‹ค ์ž‘์€ ์ˆซ์ž๋“ค์„ ์™ผ์ชฝ์— ์œ„์น˜์‹œํ‚ค๊ณ , ํ•ด๋‹น ์ˆซ์ž๋ณด๋‹ค ํฐ ์ˆซ์ž๋“ค์„ ์˜ค๋ฅธ์ชฝ์— ์œ„์น˜์‹œํ‚จ๋‹ค. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜์„œ ์ •ํ•ด์ง„ ์ž„์˜์˜ ์ˆซ์ž๋ฅผ ๊ทธ ์ค‘๊ฐ„์— ์œ„์น˜์‹œํ‚ค๋Š” ๊ฒƒ์ด๋‹ค.

Partition ๋ถ€๋ถ„์„ ์ž์„ธํžˆ ์‚ดํŽด๋ณด๊ธฐ ์ „์— ๊ฐ ์ธ์ž๋“ค์ด ๋ฌด์—‡์„ ์˜๋ฏธํ•˜๋Š”์ง€ ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. A๋Š” ์ฃผ์–ด์ง„ list์ด๋‹ค. p๋Š” ์ฃผ์–ด์ง„ list์˜ lower part๋กœ list์˜ ์‹œ์ž‘ ๋ถ€๋ถ„์„ ์˜๋ฏธํ•˜๊ณ , r์€ ์ฃผ์–ด์ง„ list์˜ higher part๋กœ list์˜ ๋ ๋ถ€๋ถ„์„ ์˜๋ฏธํ•œ๋‹ค.

  1. pivot์„ ์ •ํ•œ๋‹ค
  2. i๋Š” list์˜ ์‹œ์ž‘ index๋ณด๋‹ค ํ•˜๋‚˜ ์ž‘๊ฒŒ ๋‘”๋‹ค. i๋Š” pivot์ธ A[r]๋ณด๋‹ค ์ž‘์€ ์ˆซ์ž๋“ค์˜ list ์ค‘ ๊ฐ€์žฅ ๋†’์€ index๋ฅผ ์˜๋ฏธํ•œ๋‹ค.
  3. j๋Š” ์ฃผ์–ด์ง„ list์˜ ์‹œ์ž‘ ๋ถ€๋ถ„์ธ p๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ r-1๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค.

    1. item์ด pivot๋ณด๋‹ค ์ž‘์œผ๋ฉด i+=1์„ ํ•ด์ค€๋‹ค. pivot๋ณด๋‹ค ์ž‘์€ ์ˆ˜๋“ค์˜ index ๋ฒ”์œ„๋ฅผ ๋Š˜๋ฆฌ๋Š” ์ž‘์—…์ด๋‹ค.
    2. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜์„œ ์„œ๋กœ swap์„ ํ•ด์ค€๋‹ค.
  4. ๋งˆ์ง€๋ง‰์— pivot์„ pivot๋ณด๋‹ค ์ž‘์€ ์ˆ˜ ๊ทธ๋ฆฌ๊ณ  ํฐ ์ˆ˜๋“ค๋กœ ๋‚˜๋‰œ ๊ตฌ๊ฐ„ ์ค‘๊ฐ„์— ์œ„์น˜์‹œํ‚จ๋‹ค.
  5. i+1, ์ฆ‰, pivot์˜ ์œ„์น˜ index๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.

Quick sort๋Š” ์ถ”๊ฐ€์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ํ• ๋‹น๋œ list์˜ ๋ฉ”๋ชจ๋ฆฌ๋งŒ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— inplace ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ถˆ๋ฆฐ๋‹ค. ๋ฌผ๋ก , ๊ตฌํ˜„ ๋ฐฉ๋ฒ•์— ๋”ฐ๋ผ์„œ non-inplace ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ๋„ ์ž‘์„ฑ๋  ์ˆ˜ ์žˆ๋‹ค.

Quick sort ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ‰๊ท  ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(nlgn)์ด๋‹ค. Worse case๋Š” pivot์œผ๋กœ ํ•ญ์ƒ list์˜ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’ ํ˜น์€ ๊ฐ€์žฅ ํฐ ๊ฐ’์œผ๋กœ ์ •ํ–ˆ์„ ๋•Œ ๋ฐœ์ƒํ•˜๊ณ  ๊ทธ ๋•Œ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n^2)๊ฐ€ ๋œ๋‹ค. ํ•˜์ง€๋งŒ, ๋ณดํ†ต pivot์„ ์ •ํ•  ๋•Œ ๋žœ๋ค์œผ๋กœ ์ •ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ‰๊ท ์ ์œผ๋กœ๋Š” ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(nlgn)์ด ๋œ๋‹ค.

์ด์ œ ๊ทธ๋ฆผ์„ ๋ณด๋ฉด์„œ quick sort๊ฐ€ sorting์„ ํ•˜๋Š” ๊ณผ์ •์„ ์‚ดํŽด๋ณด์ž. ํ•ด๋‹น ๊ทธ๋ฆผ์€ Iteration๋งˆ๋‹ค ๋ฐ”๋€Œ๋Š” ๊ณผ์ •์„ ๋ณด์—ฌ์ฃผ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ํ•œ๋ฒˆ divide๋˜๊ณ  conquer๋˜๋Š” ๊ณผ์ •์„ ๋ณด์—ฌ์ค€๋‹ค. ๊ทธ๋ฆผ ๋‚ด 6๊ฐœ์˜ ์ž‘์€ ๊ทธ๋ฆผ๋“ค์ด ์žˆ๋Š”๋ฐ ๊ฐ๊ฐ step1~6์œผ๋กœ ํ‘œํ˜„์„ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

  • step1์—์„œ๋Š”, pivot์€ list[r]์ธ 6์ด ์„ ํƒ๋˜์—ˆ๋‹ค.
  • step2์—์„œ๋Š”, 6์€ 3๋ฒˆ์งธ index์— ์œ„์น˜ํ•˜๊ฒŒ ๋˜์—ˆ๊ณ , ํ•ด๋‹น index๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ index๋“ค์˜ ๊ฐ’๋“ค์€ 6๋ณด๋‹ค ์ž‘๊ณ , ์˜ค๋ฅธ์ชฝ์€ 6๋ณด๋‹ค ํฌ๋‹ค. 6์ด ์ž๊ธฐ ์ž๋ฆฌ๋ฅผ ์ฐพ์•˜๊ธฐ ๋•Œ๋ฌธ์— ์ •๋ ฌ๋˜์—ˆ๋‹ค๊ณ  ๊ฐ„์ฃผ๋ฅผ ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜์„œ ์ƒˆ๋กœ์šด pivot๋“ค์„ ์„ ํƒํ•˜๊ฒŒ ๋˜๊ณ , ์ˆซ์ž 6์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ list์ธ [2,3,5]์™€ ์˜ค๋ฅธ์ชฝ list์ธ [7,9,10,11,14,12]์—์„œ ๊ฐ๊ฐ ์ƒˆ๋กœ์šด pivot๋“ค์ด ์ •ํ•ด์กŒ๋‹ค.
  • step3์—์„œ๋Š”, 3๊ณผ 11์„ ์ •๋ ฌ๋œ ์ž๋ฆฌ์— ์ด๋™์„ ์‹œ์ผฐ๋‹ค. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜์„œ 3์˜ ์ขŒ์šฐ list์—์„œ ๊ฐ๊ฐ pivot(2,5)์„ ๊ณ ๋ฅด๊ณ , 11์˜ ์ขŒ์šฐ list์—์„œ ๊ฐ๊ฐ pivot(10,12)์„ ์„ ํƒํ–ˆ๋‹ค.
  • ste4์—์„œ๋Š”, 2์™€ 5๋Š” ๊ฐ๊ฐ ์ž์‹ ๋“ค์ด p์ด์ž r์ด๊ธฐ ๋•Œ๋ฌธ์— ์ •๋ ฌ๋œ ์ƒํƒœ๋กœ ๊ฐ„์ฃผ๋˜์—ˆ๋‹ค. 10์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ์— ์ž์‹ ๋ณด๋‹ค ํฐ ์ˆซ์ž๋“ค์ด ์—†์œผ๋‹ˆ ๊ทธ๋Œ€๋กœ ์œ„์น˜ ์ด๋™์„ ์•ˆํ•˜๊ณ  12๋Š” ํ•œ์นธ ์ด๋™์„ ํ–ˆ๋‹ค. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜์„œ ๋‹ค์‹œ pivot(9,14)๋ฅผ ์„ ํƒํ–ˆ๋‹ค.
  • step5์—์„œ๋Š”, 9์™€ 14๋ฅผ ๋” ์›€์ง์ผ ๊ณณ์ด ์—†์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ •๋ ฌ๋œ ์ƒํƒœ๋กœ ๊ฐ„์ฃผํ–ˆ๋‹ค. ๊ทธ๋Ÿฌ๊ณ  ๋งˆ์ง€๋ง‰ pivot์œผ๋กœ ์„ ํƒ๋˜์ง€ ์•Š์•˜๋˜, 7์„ ์„ ํƒํ•œ๋‹ค.
  • step6์—์„œ๋Š”, 7์ด p์ด์ž r์ด๊ธฐ ๋•Œ๋ฌธ์— ์ •๋ ฌ๋œ ์ƒํƒœ๋กœ ๊ฐ„์ฃผํ•˜๊ฒŒ ๋œ๋‹ค. ์ด๋ ‡๊ฒŒ ๋˜๋ฉด, ์ „์ฒด list๊ฐ€ ์ •๋ ฌ์ด ๋œ๋‹ค.

์œ„์—์„œ QuickSort ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ˜ธ์ถœํ•  ๋•Œ ํ•„์š”ํ•œ ์ธ์ž๋“ค์˜ ์˜๋ฏธ๋Š” ์„ค๋ช…ํ–ˆ๊ณ , ์ด์ œ ์ดˆ๊ธฐ์— ์–ด๋–ค ๊ฐ’์„ ๋„ฃ์–ด์•ผ ํ•˜๋Š”์ง€ ์„ค๋ช…ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. A์ž๋ฆฌ์—๋Š” ์ •๋ ฌํ•ด์•ผํ•  list๋ฅผ ๋„˜๊ธฐ๊ณ , p์˜ ์ž๋ฆฌ์—๋Š” list์˜ ์‹œ์ž‘ index, r์ž๋ฆฌ์—๋Š” list์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ index๋ฅผ ์ „๋‹ฌํ•˜๋ฉด ๋œ๋‹ค.

Python Code

import random

class QuickSort:
    def __init__(self, num):
        self.num = num

    def quick_sort(self, p, r):
        # p๋Š” list์‹œ์ž‘, r์€ ๋, q๋Š” ์ค‘๊ฐ„์ธ pivot
        if p<r:
            q = self.partition(p,r)
            self.quick_sort(p,q-1) # pivot์˜ ์™ผ์ชฝ์„ ๋‹ค์‹œ ๋ถ„ํ• ํ•œ๋‹ค
            self.quick_sort(q+1,r) # pivot์˜ ์˜ค๋ฅธ์ชฝ์„ ๋‹ค์‹œ ๋ถ„ํ• ํ•œ๋‹ค
        

    def partition(self, p, r):
        x = self.num[r] # pivot ๊ฐ’ ์ €์žฅ
        i = p - 1
        for j in range(p, r): 
            if self.num[j] <= x: # pivot๋ณด๋‹ค ์ž‘์œผ๋ฉด ํ•ด๋‹น ๊ฐ’์„ pivot index๋ณด๋‹ค ์™ผ์ชฝ์œผ๋กœ ์ด๋™์‹œํ‚จ๋‹ค
                i += 1
                self.num[i], self.num[j] = self.num[j] ,self.num[i] 
        self.num[i+1], self.num[r] = self.num[r], self.num[i+1] # pivot์„ ์ „์ฒด list์— ์ •๋ ฌ๋œ ์œ„์น˜์— ๋†“๋Š”๋‹ค
        return i+1  # pivot์˜ ์œ„์น˜๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค


number = [i for i in range(10)]
random.shuffle(number)
print(number)
quick = QuickSort(number)
quick.quick_sort(0, len(number)-1) # list์˜ ์ฒซ index์™€ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ index๋ฅผ ์ „๋‹ฌํ•œ๋‹ค
print(quick.num)
ยฉ 2021 Dojin Kim, Built with Gatsby