[CS] 정렬에 대한 나름의 이해

Comparison Sort: 비교를 통해 정렬하는 방식이다.

Bubble Sort: 인접한 두개를 반복해서 비교한다. 제일 큰 수부터 쌓인다.

Selection Sort: 인덱스를 선택하고 기억하고 있다가 한번 훑으며 최솟값을 찾아 그 인덱스의 값을 고쳐준다.

Insertion Sort: 오른쪽으로 순회하며 그 값에 해당하는 위치에 삽입해준다.

Merge Sort: 쪼개고 병합하며 정렬해간다. n이 트리의 깊이 logn으로 줄기 때문에 시간 복잡도가 감소한다.

Heap Sort: 넣고 뺄 때 최소나 최대를 위로 올려준다. 그래서 logn이고 n개에 대해서 진행되니 nlogn이다.

Quick Sort: pivot을 기준으로 왼쪽과 오른쪽 기준을 가지며 pivot보다 크고 작으면 swap해준다. 엇갈릴 때까지 진행된다. 엇갈리면 멈추는 이유는 pivot이 들어가야 할 위치가 엇갈린 중간이기 때문이다. 일단 엇갈린 왼쪽은 큰 값을 지칭하고 있고 엇갈린 오른쪽은 작은 값을 지칭하고 있기 때문이다. pivot은 median of three를 활용하면 제일 효율이 좋다고 알려져 있다.

 

non-Comparison Sort: 비교를 하지않고 정렬하는 방식이다.

Counting Sort: 값에 해당하는 인덱스라고 보고 그만큼 버킷을 준비하여 버킷에는 값의 개수를 넣는다. 누적합을 만들어서 새로운 배열에 할당하는 방법이라고 한다. 그러나 굳이 누적합을 만들지 않아도 그 개수만큼을 추가해주는 방식으로 해도 똑같다. 그리고 이 방식이 생각하기 더 편하다.

Radix Sort: 기수 정렬이라고 하고 같은 길이를 대상으로 한다. 한 자리씩 정렬해나가는 방법이다.

Bucket Sort: Counting Sort의 확장이다. Bucket은 특정 index의 길이를 담고 있다. 그 안에서 정렬이 되는 방식이다. 분할 정복과도 유사하다. 비교라고 볼 수 있고 아니라고 할 수도 있다. 애매하다.

 

Reference

---

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Algorithm#sorting-algorithm

https://blog.naver.com/occidere/220870294816

[정렬] Median of Three QuickSort(중간값 퀵소트) (2017.10.13 수정 완료)

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

https://yaboong.github.io/algorithms/2018/03/20/counting-sort/

Counting Sort - 계수정렬

https://ratsgo.github.io/data%20structure&algorithm/2017/10/18/bucketsort/

버킷 정렬(Bucket sort) · ratsgo's blog