[์•Œ๊ณ ๋ฆฌ์ฆ˜] Quick Sort (ํ€ต ์ •๋ ฌ)

2021. 9. 9. 08:02ใ†์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์ค€๋น„/์•Œ๊ณ ๋ฆฌ์ฆ˜

728x90
๋ฐ˜์‘ํ˜•

์•ˆ๋…•ํ•˜์„ธ์š”? ์ฃผ๋‹ˆํ•˜๋ž‘ ์ž…๋‹ˆ๋‹ค.

์˜ค๋Š˜์€ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ํ€ต ์ •๋ ฌ์— ๋Œ€ํ•ด ๊ณต๋ถ€ ํ•ด ๋ณด๋„๋ก ํ•˜๋Š” ๊ฒƒ์ด์—์š”.

์†Œ์Šค ์ฝ”๋“œ์— ๋Œ€ํ•ด์„œ ํ™•์ธ ํ•˜๊ณ  ์‹ถ์œผ์‹  ๋ถ„๋“ค๊ป˜์„œ๋Š” ์ฃผ๋‹ˆํ•˜๋ž‘์˜ Git hub์— ๊ด€์‹ฌ์„ ์ฃผ์„ธ์š”!

 

 

 

 





 

๐Ÿ“Œ Quick Sort(ํ€ต ์ •๋ ฌ)์ด๋ž€?


 

์ด๊ฒƒ์€ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฝƒ์ธ ๊ฒƒ์ด์—์š”!

์ด๋ฆ„ ๊ทธ๋Œ€๋กœ ๋น ๋ฅด๊ธฐ ๋•Œ๋ฌธ์ธ ๊ฒƒ์ด์—์š”.

ํ€ต ์ •๋ ฌ์€ ๊ธฐ์ค€์ (pivot)์„ ์ •ํ•ด์„œ, ๊ธฐ์ค€์ ๋ณด๋‹ค ์ž‘์€ Data๋Š” ์™ผ์ชฝ(left)์—  ๊ทธ๋ณด๋‹ค ํฐ Data๋Š” ์˜ค๋ฅธ์ชฝ(right)๋กœ ๋ชจ์œผ๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜๋Š” ๊ฒƒ์ด์—์š”.

๊ฐ ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ์€ ์žฌ๊ท€์šฉ๋ฒ•์„ ํ™œ์šฉํ•˜์—ฌ ๋‹ค์‹œ ๋™์ผ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ ๋’ค ์œ„ ์ž‘์—…์„ ๋ฐ˜๋ณตํ•˜๋„๋ก ํ•˜๋ฉด ๋˜๋Š” ๊ฒƒ์ด์—์š”.

๊ทธ๋Ÿฐ ๋’ค, ํ•จ์ˆ˜๋Š” ์™ผ์ชฝ + ๊ธฐ์ค€์  + ์˜ค๋ฅธ์ชฝ์„ ํ•œ ๋’ค ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋˜๋Š” ๊ฒƒ์ด์—์š”.

 

 

import random


def qsort(data):
    if len(data) <= 1:
        return data

    left, right = list(), list()
    pivot = data[0]

    for index in range(1, len(data)):
        if pivot > data[index]:
            left.append(data[index])

        else:
            right.append(data[index])

    return qsort(left) + [pivot] + qsort(right)


def qsort_list_comprehension(data):
    if len(data) <= 1:
        return data

    left, right = list(), list()
    pivot = data[0]

    left = [item for item in data[1:] if pivot > item]
    right = [item for item in data[1:] if pivot <= item]

    return qsort_list_comprehension(left) + [pivot] + qsort_list_comprehension(right)


data_list = random.sample(range(100), 10)

print(qsort(data_list))
print("=" * 1000)

data_list = random.sample(range(100), 10)

print(qsort_list_comprehension(data_list))
print("=" * 1000)

 

 

 

 

 

 

๐Ÿ“Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„์„


 

๋ณ‘ํ•ฉ ์ •๋ ฌ๊ณผ ์œ ์‚ฌํ•œ ์ด ์นœ๊ตฌ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O($n log n$)์ธ ๊ฒƒ์ด์—์š”.

ํ•˜์ง€๋งŒ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์—” ๋งจ ์ฒ˜์Œ pivot์ด ๊ฐ€์žฅ ํฌ๊ฑฐ๋‚˜, ๊ฐ€์žฅ ์ž‘์•„๋ฒ„๋ฆฌ๋ฉด ๋ฌธ์ œ๊ฐ€ ๋˜์–ด ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์ด์—์š”.

์ด๋ ‡๊ฒŒ ๋˜์–ด ๋ฒ„๋ฆฌ๋ฉด ๋ชจ๋“  Data๋ฅผ ๋น„๊ตํ•ด์•ผ ํ•˜๋Š” ํ”ผ๊ณคํ•œ ์ƒํ™ฉ์ด ๋ฐœ์ƒํ•˜๋ฉฐ, ์ด ๋•Œ, ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O($n^2$)์ด ๋˜๋Š” ๊ฒƒ์ด์—์š”.

 

728x90
๋ฐ˜์‘ํ˜•