정렬 알고리즘 정리&비교 (진행중..)

https://www.toptal.com/developers/sorting-algorithms/

Insertion Sort - Sorting Algorithm Animations

 

시간복잡도 빠르기 비교

O(1) > O(logN) > O(N) > O(NlogN) > O(n^2)

 

시간복잡도 비교

	선택 정렬	삽입 정렬	버블 정렬	병합 정렬	퀵 정렬	힙 정렬	카운팅 정렬
시간복잡도(평균)	n^2	n^2	n^2	nlogn	nlogn	nlogn	n
시간복잡도(최악)	n^2	n^2	n^2	nlogn	n^2	nlogn	n
가장 빠른 경우	일정	거의 정렬된 리스트	정렬된 리스트	일정		일정
가장 느린 경우	일정	정렬된 리스트	역순 배열	일정		일정
장점	쉬운 구현	최선의 경우 O(N)	쉬운 구현	일정한 빠른 속도	추가적인 메모리 할당 불필요	추가 메모리가 필요하지 않다	매우 빠른 속도
단점	느린 속도	최선 N, 최악 N^2 으로 성능차 심함	느린 속도	추가적인 메모리 할당 필요	피봇에 의한 성능차 심함	병합, 퀵정렬보다 실행시간 오래걸림	추가적인 메모리 공간 필요

선택정렬 (Selection Sort)

전체 리스트 다 보고 가장 작은 값 찾아 맨 앞에 배치(0번 인덱스 값과 교체)

이후 1번 인덱스부터 끝까지 다 보고 가장 작은 값 찾아 1번 인덱스 값과 교체

어떤 경우던 일정하게 느리기 때문에 어디다 쓰지? 싶지만, swap 횟수가 적기 때문에

cost of swapping items 가 높은 경우 유용하다.

삽입 정렬 (Insertion Sort)

인덱스를 하나하나 늘려가며 확인하는데, 더 작은 수가 나올 경우 적정 위치까지 계속 왼쪽으로 옮긴다.

나머지 수들은 오른쪽으로 민다.

비록 최악의 경우 O(n^2) 로 매우 느리지만, 데이터가 거의 정렬된 경우, 문제가 작은 경우 매우 빠르다.(오버헤드가 적기 때문)

안정적이기 때문에, 삽입 정렬은 종종 병합정렬이나 퀵정렬 재귀표현의 베이스케이스로 사용되기도 한다.

 

버블 정렬 (Bubble Sort)

 

병합 정렬 (Merge Sort)

원본 배열을 분할하고 정렬하며 정복해나가는 방식.

항상 NlongN의 시간 복잡도가 필요하다.

 

퀵 정렬 (Quick Sort)

피벗을 정하고 피벗보다 작으면 왼쪽, 크면 오른쪽. 계속 비교하면서 교환.

분할 과정에서 logN, 전체적으로 NlogN

 

힙 정렬 (Heap Sort)

최대 힙을 만들고 루트 노드 던지고 마지막 노드를 루트 노드 위치에 넣고 다시 최대 힙 만들기를 반복