๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ Python

[Python] sort, sorted (Timsort, ํŒ€ ์†ŒํŠธ)

by dev.py 2025. 5. 22.

๋ฌธ๋“ Python์˜ Sequence.list(), sorted() ๋Š” ์–ด๋–ค ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์“ฐ๋Š” ์ง€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค.

๊ฒฐ๋ก ๋ถ€ํ„ฐ ๋งํ•˜๋ฉด ๋‘˜ ๋‹ค Timsort๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. (3.11 ์ดํ›„๋Š” Timsort ๋ณ€ํ˜•์ธ Powersort)

1. sort() vs sorted() 

ํ•จ์ˆ˜ ์‚ฌ์šฉ ํ˜•ํƒœ ์›๋ณธ ๋ณ€๊ฒฝ ๋ฐ˜ํ™˜๊ฐ’
list.sort() ๋ฆฌ์ŠคํŠธ ๋ฉ”์„œ๋“œ O None
sorted() ๋‚ด์žฅ ํ•จ์ˆ˜ X ์ •๋ ฌ๋œ ์ƒˆ๋กœ์šด ๋ฆฌ์ŠคํŠธ

 

  • sort ํ•จ์ˆ˜๋Š” List.sort(*, key=None, reverse=False) ํ˜•์‹์œผ๋กœ "๋ฆฌ์ŠคํŠธํ˜•์˜ ๋ฉ”์†Œ๋“œ"โ€‹โ€‹์œผ๋กœ ๋ฆฌ์ŠคํŠธ_๊ฐ์ฒด ๊ฐ’์„ ์ง์ ‘ ์ˆ˜์ •ํ•œ๋‹ค.
  • sorted ํ•จ์ˆ˜๋Š” sorted(iterable, /, *, key=None, reverse=False) ํ˜•์‹์œผ๋กœ "ํŒŒ์ด์ฌ ๊ธฐ๋ณธ ๋‚ด์žฅ ํ•จ์ˆ˜"์œผ๋กœ  ์›๋ณธ ๊ฐ’์€ ๊ทธ๋Œ€๋กœ์ด๊ณ  ์ •๋ ฌ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

 

2. Timsort

  • ์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort)์™€ ๋ณ‘ํ•ฉ ์ •๋ ฌ(Merge Sort)์˜ ํ•˜์ด๋ธŒ๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • 2002๋…„ Python์˜ ์ •๋ ฌ ์„ฑ๋Šฅ์„ ์ตœ์ ํ™”ํ•˜๊ธฐ ์œ„ํ•ด Tim Peters๊ฐ€ ๊ฐœ๋ฐœํ–ˆ์œผ๋ฉฐ, Java, Kotlin, Android ๋“ฑ์—๋„ ์ผ๋ถ€ ์ฑ„ํƒ

ํ•ต์‹ฌ ์•„์ด๋””์–ด

  • ํ˜„์‹ค ์„ธ๊ณ„์˜ ๋ฐ์ดํ„ฐ๋Š” ๋ฌด์ž‘์œ„๋ณด๋‹ค ์–ด๋А ์ •๋„ ์ •๋ ฌ๋œ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง„ ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์Œ
  • ์ด๋Ÿฐ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ค๋ฃฐ ๋•Œ, ๋‹จ์ˆœํ•œ Quick Sort ๋ณด๋‹ค Timsort๊ฐ€ ํ›จ์”ฌ ๋” ํšจ์œจ์ 

ํŠน์ง•

  • ์ตœ์•… O(n log n)
  • "๋ถ€๋ถ„ ์ •๋ ฌ๋œ ๋ฐ์ดํ„ฐ"์—์„œ ๋น ๋ฅด๊ฒŒ ๋™์ž‘
  • ์•ˆ์ • ์ •๋ ฌ (Stable)
  • ์บ์‹œ์™€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ž˜ ํ™œ์šฉ

 

3. ์™œ Insertion Sort๋ฅผ ์„ž์—ˆ์„๊นŒ - ์ฐธ์กฐ ์ง€์—ญ์„ฑ (Locality of Reference)

์ถœ์ฒ˜ : https://d2.naver.com/helloworld/0315536

 

Timsort๋Š” ์ž‘์€ ๊ตฌ๊ฐ„(run)์„ ์ •๋ ฌํ•  ๋•Œ ์‚ฝ์ž… ์ •๋ ฌ์„ ์‚ฌ์šฉํ•œ๋‹ค.

์™œ ์‹œ๊ฐ„ ๋ณต์žก๋„ O(nยฒ)์ธ ์‚ฝ์ž… ์ •๋ ฌ์„ ์‚ฌ์šฉํ• ๊นŒ?

  • ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(nยฒ)์ด์ง€๋งŒ, ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ์ด ์ˆœ์ฐจ์ ์ด๊ณ , ์บ์‹œ ์นœํ™”์ ์ด๋ฉฐ, ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋˜์–ด ์žˆ์œผ๋ฉด ๋งค์šฐ ๋น ๋ฆ„

 

์ฐธ์กฐ ์ง€์—ญ์„ฑ

์ข…๋ฅ˜ ์„ค๋ช…
๊ณต๊ฐ„ ์ง€์—ญ์„ฑ ๊ฐ€๊นŒ์šด ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ•จ๊ป˜ ์ฐธ์กฐ
์‹œ๊ฐ„ ์ง€์—ญ์„ฑ ์ตœ๊ทผ ์ ‘๊ทผํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ค์‹œ ์ฐธ์กฐ
์ˆœ์ฐจ ์ง€์—ญ์„ฑ ๋ฐ์ดํ„ฐ๊ฐ€ ์ˆœ์ฐจ์ ์œผ๋กœ ์ ‘๊ทผ๋จ

 

 

์‚ฝ์ž… ์ •๋ ฌ์€ ์ˆœ์ฐจ์ ์ด๊ณ  ์ธ์ ‘ํ•œ ๋ฉ”๋ชจ๋ฆฌ๋งŒ ์ ‘๊ทผํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ์บ์‹œ ์ ์ค‘๋ฅ (Cache Hit)์ด ๋†’์•„ ์„ฑ๋Šฅ์ด ์ข‹์Œ

 

 

 

 

์ถœ์ฒ˜ : https://d2.naver.com/helloworld/0315536 Insertion Sort
์ถœ์ฒ˜ : https://d2.naver.com/helloworld/0315536   Merge Sort

 

 

4. Timsort ์ „์ฒด ํ๋ฆ„

  1. Run ํƒ์ƒ‰:
    ์ด๋ฏธ ์ •๋ ฌ๋œ ๋ถ€๋ถ„(run)์„ ์ฐพ๊ณ  ๊ฐ€๋Šฅํ•œ ๊ธธ๊ฒŒ ํ™•์žฅ
    (ex. ์˜ค๋ฆ„์ฐจ์ˆœ ๋˜๋Š” ๋‚ด๋ฆผ์ฐจ์ˆœ โ†’ ๋’ค์ง‘์–ด์„œ ์ฒ˜๋ฆฌ)
  2. minrun ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ:
    ์ž‘์€ run์€ Binary Insertion Sort๋กœ ์ •๋ ฌ (์ด์ง„ ํƒ์ƒ‰ + ์‚ฝ์ž…)
  3. Run ๋ณ‘ํ•ฉ(Merge):
    Merge Sort ๊ธฐ๋ฐ˜์ด์ง€๋งŒ, ์œ ๋™์ ์ธ Run ๋ณ‘ํ•ฉ ์กฐ๊ฑด ์‚ฌ์šฉ
    (๋น„์Šทํ•œ ํฌ๊ธฐ๋ผ๋ฆฌ, ๋ณ‘ํ•ฉ ํšŸ์ˆ˜ ์ตœ์†Œํ™”)
  4. Galloping ์ตœ์ ํ™”:
    ํ•œ Run์ด ๊ณ„์† ์ด๊ธฐ๋ฉด ์ง€์ˆ˜ ๋‹จ์œ„๋กœ ๊ฑด๋„ˆ๋›ฐ๋ฉฐ ์ด๋ถ„ํƒ์ƒ‰

 

 

 

 

5. ์ถœ์ฒ˜

๋” ์ž์„ธํ•œ ์–˜๊ธฐ๋Š” ๋„ค์ด๋ฒ„ ๊ฐœ๋ฐœ์ž ๋ธ”๋กœ๊ทธ์— ๊ทธ๋ฆผ ์˜ˆ์‹œ๋กœ ์„ค๋ช…๋˜์–ด ์žˆ๋‹ค.

https://d2.naver.com/helloworld/0315536