[기술면접준비] 알고리즘

Sorting Algorithm

Comparisons Sorting Algorithm : 비교방식 알고리즘

1. Bubble sort : O(n^2)
2. selection sort : O(n^2)
3. Insertion sort : O(n^2)
4. Merge sort : O(n log n) , divide / conquer
5. Heap sort : O(n log n) [정렬], O(log n) [삽입, 삭제],
(1) 힙에 넣었다가 꺼내는 원리로 sorting
(2) 기존의 배열을 heapify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법
6. Quick sort : O(n log n), divide / conquer

• worst case : O(n^2)
• Balanced Partitioning
• Partitioning

non-Comparisons Sortimg Algorithm

1.Counting Sort : O(n)
2.Radix Sort : O(n), 기수행렬, 데이터길이에 의존, LSD / MSD

Prime Number Algorithm

에라토스테네스의 체