정렬

정렬이란 무엇이냐

일정한 순서대로 열거¹ 하는 것을 의미한다.

물론 사전적 정의다. 서론으로 이런 거 써놓으면 있어보여서 적었다.

알고리즘에선 데이터를 일정한 기준에 따라 순서대로 나열하는 것을 의미한다.

대표적 정렬 알고리즘

알고리즘명	시간복잡도(평균)	공간복잡도	특징
버블 정렬	O(N^2)	O(1)	단순, 느림
선택 정렬	O(N^2)	O(1)	단순, 느림
삽입 정렬	O(N^2)	O(1)	거의 정렬된 경우 빠름
병합 정렬	O(N log N)	O(N)	항상 빠름, 안정적
퀵 정렬	O(N log N)	O(log N)	대부분 빠름, 불안정
팀소트	O(N log N)	O(N)	파이썬 기본, 빠름

버블정렬이 개인적으로 이름이 마음에 든다.

기포가 위로 올라오는 모습을 본땄다는데 그래서 쌍방향 버블 정렬은
칵테일 정렬이라고도 부른다.

개노잼 정렬에서 순식간에

이리저리 흔들리는 쉐이커가 되었다.

이래서 서사와 이름이 중요한거다.

그치만 효율 졸라 구리니 에지간해선 쓸일 없을테니 이름만 알아두자.

나중에 스몰토크 할때 써먹어라 두번 써라

코딩 이야기 : 데이터가 적으면 팀소트(Python 기본)보다 빠를 때도 있다던데…
난 잘 모르겠다.
악질 찌라시일 수 있으니 주의하자.

파이썬의 내장 정렬 함수

팀소트라는 어지간해선 가장 효율적인 알고리즘을 쓴다.

그리고 내부 C언어로 굴리기에 속도로 더빠르다.

sort와 sorted로 2개가 있으니 상황에 따라 돌려 쓰면 된다.

함수명	설명	반환값	원본 변화
`sorted(리스트)`	정렬된 새 리스트 반환	새 리스트	X
`리스트.sort()`	리스트 자체를 정렬 (리턴값 없음)	None	O

팀소트(Timsort)에 대한 추가정보

파이썬의 sorted()와 list.sort()는 Timsort(팀소트) 라는 하이브리드 정렬 사용

합병 정렬(Merge Sort) + 삽입 정렬(Insertion Sort)의 장점을 합침
시간복잡도: 최악, 평균 O(N log N)
실제 대부분의 경우 매우 빠름

추가적인 정보는 시간 나면 자세히 다뤄보겠다.

시간 안날 거 같긴 하다만…

여러 가지 예나 사실을 낱낱이 죽 늘어놓음. ↩