๋ฌธ๋ 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)

Timsort๋ ์์ ๊ตฌ๊ฐ(run)์ ์ ๋ ฌํ ๋ ์ฝ์ ์ ๋ ฌ์ ์ฌ์ฉํ๋ค.
์ ์๊ฐ ๋ณต์ก๋ O(nยฒ)์ธ ์ฝ์ ์ ๋ ฌ์ ์ฌ์ฉํ ๊น?
- ์๊ฐ ๋ณต์ก๋๋ O(nยฒ)์ด์ง๋ง, ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ์ด ์์ฐจ์ ์ด๊ณ , ์บ์ ์นํ์ ์ด๋ฉฐ, ๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋์ด ์์ผ๋ฉด ๋งค์ฐ ๋น ๋ฆ
์ฐธ์กฐ ์ง์ญ์ฑ
์ข ๋ฅ | ์ค๋ช |
๊ณต๊ฐ ์ง์ญ์ฑ | ๊ฐ๊น์ด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ๊ป ์ฐธ์กฐ |
์๊ฐ ์ง์ญ์ฑ | ์ต๊ทผ ์ ๊ทผํ ๋ฐ์ดํฐ๋ฅผ ๋ค์ ์ฐธ์กฐ |
์์ฐจ ์ง์ญ์ฑ | ๋ฐ์ดํฐ๊ฐ ์์ฐจ์ ์ผ๋ก ์ ๊ทผ๋จ |
์ฝ์ ์ ๋ ฌ์ ์์ฐจ์ ์ด๊ณ ์ธ์ ํ ๋ฉ๋ชจ๋ฆฌ๋ง ์ ๊ทผํ๊ธฐ ๋๋ฌธ์, ์บ์ ์ ์ค๋ฅ (Cache Hit)์ด ๋์ ์ฑ๋ฅ์ด ์ข์


4. Timsort ์ ์ฒด ํ๋ฆ
- Run ํ์:
์ด๋ฏธ ์ ๋ ฌ๋ ๋ถ๋ถ(run)์ ์ฐพ๊ณ ๊ฐ๋ฅํ ๊ธธ๊ฒ ํ์ฅ
(ex. ์ค๋ฆ์ฐจ์ ๋๋ ๋ด๋ฆผ์ฐจ์ โ ๋ค์ง์ด์ ์ฒ๋ฆฌ) - minrun ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ:
์์ run์ Binary Insertion Sort๋ก ์ ๋ ฌ (์ด์ง ํ์ + ์ฝ์ ) - Run ๋ณํฉ(Merge):
Merge Sort ๊ธฐ๋ฐ์ด์ง๋ง, ์ ๋์ ์ธ Run ๋ณํฉ ์กฐ๊ฑด ์ฌ์ฉ
(๋น์ทํ ํฌ๊ธฐ๋ผ๋ฆฌ, ๋ณํฉ ํ์ ์ต์ํ) - Galloping ์ต์ ํ:
ํ Run์ด ๊ณ์ ์ด๊ธฐ๋ฉด ์ง์ ๋จ์๋ก ๊ฑด๋๋ฐ๋ฉฐ ์ด๋ถํ์
5. ์ถ์ฒ
๋ ์์ธํ ์๊ธฐ๋ ๋ค์ด๋ฒ ๊ฐ๋ฐ์ ๋ธ๋ก๊ทธ์ ๊ทธ๋ฆผ ์์๋ก ์ค๋ช ๋์ด ์๋ค.
https://d2.naver.com/helloworld/0315536
'๐ Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] type hint & generic (0) | 2025.04.23 |
---|---|
์ดํํฐ๋ธ ํ์ด์ฌ 8์ฅ - ๊ฐ๊ฑด์ฑ๊ณผ ์ฑ๋ฅ (0) | 2025.04.09 |
์ดํํฐ๋ธ ํ์ด์ฌ 7์ฅ - ๋์์ฑ๊ณผ ๋ณ๋ ฌ์ฑ (0) | 2025.04.01 |
์ดํํฐ๋ธ ํ์ด์ฌ 6์ฅ - ๋ฉํํด๋์ค์ ์ ํธ๋ฆฌ๋ทฐํธ (0) | 2025.03.30 |
์ดํํฐ๋ธ ํ์ด์ฌ 5์ฅ - ํด๋์ค์ ์ธํฐํ์ด์ค (0) | 2025.03.21 |