Sort

Bubble Sort

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘\
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.\
선택 정렬과 기본 개념이 유사하다.

시간복잡도 : O(n^2)

Selection Sort

제자리 정렬(in-place sorting) 알고리즘의 하나\
입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법\
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

시간복잡도 : O(n^2)

Insertion Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘\
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

시간 복잡도 : O(n^2)

Merge Sort

일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.

과정 설명
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

**시간 복잡도 : O(N logN)

안정 정렬이란?\
안정 정렬이란 정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 되는 정렬 알고리즘을 안정 정렬이라고 한다.

제자리 알고리즘이란?\
추가적인 자료구조를 사용하지 않고 입력을 변환하는 알고리즘\
보통 약간의 추가공간은 허용한다.

Heap Sort

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법\
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

**시간복잡도 : O(N logN)

Quick Sort

퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.\
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법\

과정 설명
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
5. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될 때까지 반복한다.
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

시간복잡도 : O(N log N)

Radix Sort

데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 방식\
but\
기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없다. 또한 길이가 다른 데이터들을 대상으로는 정렬이 불가능하다.

시간 복잡도 : O(d(N + k))
d = 정렬자릿수, k = 각 자리에 가능한 수

비교연산을 통한 정렬간의 비교

단순하지만 비효율적인 방법
삽입, 선택, 버블
복잡하지만 효율적인 방법
퀵, 힙, 합병, 기수

Intro Sort
이는 C++에서 std::sort에서 사용하는 알고리즘으로써
재귀 깊이가 특정 임계값을 초과할 때까지 입력 데이터에 대해 빠른 정렬을 사용하는 것입니다. 이 시점에서 알고리즘은 최악의 성능을 피하기 위해 힙 정렬로 전환됩니다. 또한 introsort는 작은 하위 배열에 대한 삽입 정렬을 사용하여 작은 데이터 세트에 대한 효율성을 활용합니다.
실제 Quick Sort와 Heap Sort를 임계점에 따라 바꿔가며 사용합니다.
Swift에선 진화된 Intro Sort를 사용하는데, swift는 일부 정렬된 데이터라면 특수한 퀵 정렬을 이용하여 문제를 해결합니다.

Counting Sort

주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

시간복잡도 : O(N)
근데 숫자가 커지거나 밀도가 낮으면 헛도는 경우가 생겨 실제로는 숫자크기에 큰 영향을 받아 비효율적인 알고리즘이다.

불안정 정렬\
순서가 정렬 후 보장되지 않는 정렬
선택 정렬(selection sort), 퀵 정렬(quick sort), 힙 정렬(heap sort)