- 트리 정렬(Tree Sort)이란? 이진 탐색 트리를 만들어 정렬하는 방식. 힙 정렬과 비슷해 보이지만 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 자식이 되느냐 오른쪽 자식이 되느냐가 다르다. - 트리 정렬의 정렬 과정 정렬될 배열의 맨 첫 값이 루트 노드가 된다. 다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다. 위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 ..

- 퀵 정렬(Quick Sort)이란? 적절한 원소 하나를 기준(pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 기준을 옮겨 기준보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 기준을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.

- 힙 정렬(Heap Sort)이란? 선택 정렬과 거의 같은 알고리즘으로, 가장 큰 원소를 뒤로 보내는 데에 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다. - 힙 정렬의 정렬 과정 원소들을 전부 힙에 삽입한다. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다. 힙이 빌 때까지 2의 과정을 반복한다.

- 병합 정렬/합병 정렬(Merge Sort)이란? 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합하는 방식. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다. 이 그림에서 분할 정복으로 일정하게 정렬이 이뤄지는 병합 정렬의 특징을 잘 파악할 수 있다. [38, 27, 43, 3, 9, 82, 10]인 입력값은 [38, 27, 43, 3]과 [9, 82, 10] 로 두 부분으로 분할, 다시 [38, 27], [43, 3], [9, 82], [10]로 네 부분으로 분할 등의 방식으로 각각 더 이상 쪼갤 수 없을 때까지 계속해서 분할한 후, 분할이 끝나면 정렬하면서 정복해 나간다.

- 삽입 정렬(Insertion Sort)이란? k번째 원소를 1부터 k－1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식 → 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘 ex) 카드 게임을 할 때나 번호대로 도서를 정리할 때 사용