๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/๊ธฐ๋ณธ ์•Œ๊ณ ๋ฆฌ์ฆ˜

์ •๋ ฌ ์ฝ”๋“œ2(ํ€ต ์ •๋ ฌ, ๋ณ‘ํ•ฉ ์ •๋ ฌ)

ํ€ต ์ •๋ ฌ (quick sort)

  • ํ€ต์ •๋ ฌ์€ ์‚ฝ์ž…์ •๋ ฌ๊ณผ ๋‹ค๋ฅด๊ฒŒ '์ด๋ฏธ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋œ ๊ฒฝ์šฐ' ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๊ฑฐ์˜ O(n^2)์œผ๋กœ ๋งค์šฐ ๋Š๋ฆฌ๊ฒŒ ๋™์ž‘ํ•œ๋‹ค.
  • ํ•˜์ง€๋งŒ ๋ฐ์ดํ„ฐ๊ฐ€ ๋ฌด์ž‘์œ„๋กœ ์ž…๋ ฅ๋˜๋Š” ๊ฒฝ์šฐ O(nlogn)์˜ ์†๋„๋กœ ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ๋™์ž‘ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๋ฐ์ดํ„ฐ์˜ ์ƒํƒœ๋ฅผ ๋ณด๊ณ  ์‚ฝ์ž…์ •๋ ฌ๊ณผ ์ž˜ ์„ ํƒํ•˜์—ฌ ์‚ฌ์šฉํ•ด์•ผํ•œ๋‹ค.

def quick_sort(array, start, end):
    if start >= end:                   # ์•„๋ž˜ ์žฌ๊ท€ํ•จ์ˆ˜์—์„œ ๋ชจ๋“  ์ •๋ ฌ์ด ๋๋‚˜๊ณ  ์›์†Œ๊ฐ€ 1๊ฐœ์ธ ๊ฒฝ์šฐ ์ข…๋ฃŒ
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:             # left์™€ right๊ฐ€ ๊ต์ฐจํ• ๋•Œ ์ž‘์€๊ฐ’(right(์—‡๊ฐˆ๋ ธ์œผ๋ฏ€๋กœ))๊ณผ pivot ๊ต์ฒด
            array[right], array[pivot] = array[pivot], array[right]
        else: # ๋งŒ์•ฝ ๊ต์ฐจํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด left์™€ right ๊ต์ฒด
            array[left], array[right] = array[right], array[left]

 

    quick_sort(array, start, right - 1) # pivot ๊ธฐ์ค€ ์™ผ์ชฝ
    quick_sort(array, right + 1, end) # pivot ๊ธฐ์ค€ ์˜ค๋ฅธ์ชฝ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ๋‹ค์‹œ ์ •๋ ฌ

 


ํ€ต ์ •๋ ฌ2 (quick sort)

  • ํŒŒ์ด์ฌ์˜ ์žฅ์ ์„ ์‚ด๋ฆฐ ์ข€ ๋” ์งง๊ณ  ์ง๊ด€์ ์ธ quick sort code (๋น„๊ต ํšŸ์ˆ˜๊ฐ€ ์ฆ๊ฐ€ํ•˜์—ฌ ํšจ์œจ์€ ์กฐ๊ธˆ ๊ฐ์†Œ)

 

def quick_sort(array):

    if len(array) <= 1:

        return array

 

    pivot = array[0]

    tail = array[1:]

 

    left_side = [x for x in tail if x <= pivot]         # ํ”ผ๋ด‡์„ ์ œ์™ธํ•œ ๋ฆฌ์ŠคํŠธ tail ์ค‘ ํ”ผ๋ด‡๋ณด๋‹ค ์ž‘์€ ๊ฐ’์„ left_side ๊ฐ์ฒด์— ์ €์žฅ (๋ชจ๋“  tail์— ๋Œ€ํ•ด ๋น„๊ต๋ฅผ ํ•˜๋ฏ€๋กœ ๋” ์—ฐ์‚ฐํšŸ์ˆ˜๊ฐ€ ๋งŽ์Œ)

    right_side = [x for x in tail if x > pivot]         # ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ํ”ผ๋ด‡๋ณด๋‹ค ํฐ ๊ฐ’์„ right_side ๊ฐ์ฒด์— ์ €์žฅ return           

    quick_sort(left_side) + [pivot] + quick_sort(right_side)         # ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜์—ฌ len(array) <= 1 ์ผ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๊ณ  ์ „์ฒด ๋ฆฌ์ŠคํŠธ ๋ฐ˜ํ™˜

 


๋ณ‘ํ•ฉ ์ •๋ ฌ (merge sort)

  • ๋ฐ์ดํ„ฐ๋ฅผ ๋” ์ด์ƒ ๋‚˜๋ˆŒ ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋‚˜๋ˆ„๊ณ , ๋‹ค์‹œ ๋ณ‘ํ•ฉํ•˜๋ฉฐ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. (๋ณ‘ํ•ฉ ํ•  ๋•Œ ์ •๋ ฌ์‹คํ–‰) 
  • ๋ฐ์ดํ„ฐ๋ฅผ ๋‚˜๋ˆŒ ๋•Œ ์ ์ฐจ ๋ฐ˜์”ฉ ์ค„์–ด๋“œ๋ฏ€๋กœ O(logN), ๋ณ‘ํ•ฉ ํ• ๋•Œ ๋ชจ๋“  ๊ฐ’์„ ๋น„๊ต ํ•ด์•ผํ•˜๋ฏ€๋กœ O(N)์ด๋ฏ€๋กœ ์ด O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

def merge_sort(array):

    if len(array) <= 1:

        return array

 

    mid = len(array) // 2

    left_array = array[:mid]

    right_array = array[mid:]

 

    left_array = merge_sort(left_array)

    right_array = merge_sort(right_array)

    return merge(left_array, right_array)

 

def merge(left, right):

    result = []

    while ( len(left) > 0 or len(right) > 0 ):

        if ( len(left) > 0 and len(right) > 0 ):

            if ( left[0] <= right[0] ):

                result.append(left[0])

                left = left[1:]

            else:

                result.append(right[0])

                right = right[1:]

        elif len(left) > 0:

            result.append(left[0])

            left = left[1:]

        elif len(right) > 0:

            result.append(right[0])

            right = right[1:]

    return result