1. 파이썬에서 기본적으로 주어진 정렬 방법 (Timsort)

버블 정렬

느림.

퀵 정렬

분할 정복 알고리즘- 재귀 구조임

기준을 어떻게 정하느냐가 성능에 영향(최초 3개 중 중간값을 선택하는 방법이 최악을 피하게 함.)

최악의 경우의 수는 버블이나 삽입과 속도가 같아짐.

트리 정렬(Tree sort)

이진 탐색 트리를 만들어 정렬하는 방식이다. 힙 정렬과 비슷해 보이지만 차이가 있는데, 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 자식이 되느냐 오른쪽 자식이 되느냐가 갈린다는 차이가 있다.어떻게 진행되는지를 대략적으로 설명하자면,

1. 정렬될 배열의 맨 첫 값이 루트 노드가 된다.
2. 다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다.
3. 위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 방향의 자식 노드가 있으면 계속 그 방향으로 가서 조사하고 없으면 그 방향의 자식 노드로 추가한다.
4. 모든 값이 노드로 추가되었으면 해당 트리를 중위 순회 방식으로 순회하여 그 순서대로 값을 정렬해 나간다.

예를 들어, [4, 6, 1, 7, 5, 8, 2, 3]을 트리 정렬로 정렬하기 위해 이진 트리를 만들면 이렇게 된다.

이 이진 트리를 중위 순회 방식(왼쪽 자식 - 자신 - 오른쪽 자식 순)으로 순회하면(위 그림에서 무지개색 순으로 순회한다) [1, 2, 3, 4, 5, 6, 7, 8]이 된다.최대값과 최소값을 탐색할때 매우 강력하다.이를 배열로도 구현이 가능하다 그러나 입력값이 적은것이 아니라면 별로 추천하지 않는다.[28]

삽입 정렬

평균적으로 버블보다 빠르거나 같음

병합 정렬

성능이 일관적이다. 정렬된 두 배열을 머징할때 응용하면 가장 빠르게 정렬된 상태로 합칠 수 있다.

https://youtu.be/XaqR3G_NVoo

Tim정렬

Tim sort에 대해 알아보자

셀 정렬

삽입 정렬을 띄엄띄엄 하고 간격을 좁히기

**계수 정렬

(Counting sort)**

**힙 정렬(Heap sort)**

자료구조 개념 이해하기 ‘힙과 힙 정렬 알고리즘’ | 요즘IT