๐ŸŒ ํ€ต ์ •๋ ฌ (quick sort)

eunseo kim ๐Ÿ‘ฉโ€๐Ÿ’ปยท2021๋…„ 1์›” 7์ผ
0

โœจ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ธฐ๋ณธ

๋ชฉ๋ก ๋ณด๊ธฐ
8/10

๐Ÿ“Œ ํ€ต ์ •๋ ฌ์ด๋ž€?

  • ๊ธฐ์ค€์ (pivot ์ด๋ผ๊ณ  ๋ถ€๋ฆ„)์„ ์ •ํ•ด์„œ, ๊ธฐ์ค€์ ๋ณด๋‹ค ์ž‘์€ ๋ฐ์ดํ„ฐ๋Š” ์™ผ์ชฝ(left), ํฐ ๋ฐ์ดํ„ฐ๋Š” ์˜ค๋ฅธ์ชฝ(right) ์œผ๋กœ ๋ชจ์œผ๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•จ
  • ๊ฐ ์™ผ์ชฝ(left), ์˜ค๋ฅธ์ชฝ(right)์€ ์žฌ๊ท€์šฉ๋ฒ•์„ ์‚ฌ์šฉํ•ด์„œ ๋‹ค์‹œ ๋™์ผ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜์—ฌ ์œ„ ์ž‘์—…์„ ๋ฐ˜๋ณตํ•จ
  • ํ•จ์ˆ˜๋Š” ์™ผ์ชฝ(left) + ๊ธฐ์ค€์ (pivot) + ์˜ค๋ฅธ์ชฝ(right) ์„ ๋ฆฌํ„ดํ•จ

๐Ÿ“Œ ํ€ต ์ •๋ ฌ ๊ตฌํ˜„ํ•˜๊ธฐ

๐Ÿ‘‰๊ทธ๋ฆผ์œผ๋กœ ๊ณผ์ • ์ดํ•ดํ•˜๊ธฐ


โœ… Code

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)
  • ํŒŒ์ด์ฌ list comprehension์„ ์‚ฌ์šฉํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
def qsort(data):
    if len(data) <= 1:
        return data
    
    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(left) + [pivot] + qsort(right)

๐Ÿ˜‰ ์ดํ•ด๊ฐ€ ์ž˜ ์•ˆ๋œ๋‹ค๋ฉด ์—ฌ๊ธฐ๋ฅผ ํด๋ฆญ


๐Ÿ“Œ ์‹œ๊ฐ„ ๋ณต์žก๋„

  • ํ€ต ์ •๋ ฌ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(nlogn)O(n log n)
  • ๋‹จ, ์ตœ์•…์˜ ๊ฒฝ์šฐ(๋งจ ์ฒ˜์Œ pivot์ด ๊ฐ€์žฅ ํฌ๊ฑฐ๋‚˜, ๊ฐ€์žฅ ์ž‘์•„์„œ ๋ชจ๋“  ๋ฐ์ดํ„ฐ๋ฅผ ๋น„๊ตํ•˜๋Š” ์ƒํ™ฉ)์—๋Š” O(๐‘›2)O( ๐‘›^2 )
profile
์—ด์‹ฌํžˆ๐Ÿ’จ (์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ธ”๋กœ๊ทธ)

0๊ฐœ์˜ ๋Œ“๊ธ€