1. Selection Sort

• 가장 작은 value찾아서 앞으로 이동하여 정렬하는 방식
• Time complexity: O(N^2)

2. Bubble Sort

• 마지막 요소부터 시작하여 이웃한 요소들을 비교하여 swap, 이를 array의 길이 만큼 진행
• Time complexity: O(N^2)

3. Insertion Sort

• 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬 https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
• Time complexity: O(N^2)
• Bubble Sort보단 조금 더 효율적

4. Heap Sort

1. Unsorted array를 Heap으로 만듦. → reheapdown (n/2*non leaf노드의 개수) 번 → O(NlogN)
2. Root Node의 값이랑 last location의 값이랑 swap한 뒤 reheapdown 진행 → n번 진행 → O(NlogN)

• Time complexity: O(NlogN)

5. Quick Sort

• spliVal 지정해서 그보다 작은 건 왼쪽으로 큰 건 오른쪽으로 계속 나눔.

• Time complexity:
  • O(NlogN) → Average
  • O(N^2)→ Worst case(이미 오름차순으로 정렬되어 있어서 1 vs N-1로 나누어질 때)

6. Merge Sort

1. arrary를 반으로 cut