[Sorting Algorithm]

O(N^2) Sorting

-Without a divide-and-conquer approach

-Sequential comparisons with two index iteration: 두 번의 iteration -> N!

-종류:Insertion Sort / Selection Sort / Bubble Sort

 

Insertion Sort

 

Selection Sort

 

Bubble Sort

O(N * logN) Sorting

-With a divide-and-conquer approach : 타겟 시퀀스를 쪼개서 비교한다!

-recursion 이 들어감!

-종류:

Quick Sort  : pivot (기준점) 을 설정하고, 이를 기준으로 원소를 pivot보다 더 큰 것/ pivot보다 더 작은 것으로 나눈다. pivot을 잘 설정하지 않으면 그냥 O(N^2) 될 수도 있음!

Quick Sort

 

 

 Merge Sort : 일단 반으로 쪼개서 하나씩 남겨둔 후, 값을 서로 비교

Merge Sort

Heap Sort : Binary Heap 구조에 넣어서 dequeue 하면서 정렬함! 

Heap Sort

O(N) Sorting

-더이상 비교하지도 않음

-대신 가정이 필요함. 

-종류 : Radix Sort / Counting Sort

Radix Sort

 

Counting Sort

가정: (1)only integers, (2)ranging from 0 to K

-0~K 사이즈의 빈 array를 생성->타겟 시퀀스에서 숫자가 몇 번 발생하는지 카운트->array의 해당 index에 횟수 저장. 

-Time complexity : O(N + R) * R은 K. 만약 K가 엄청 클 경우 O(K) 가 될 것임!

 

Radix Sort

가정: sequence contains integers

10진수의 각 자리별로 counting sort에 넣어가며 비교함

-Time complexity : O(ND)

Radix Sort