정렬 알고리즘의 비교

정렬 알고리즘의 성능 비교

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n^2)	O(n^2)
선택 정렬	O(n^2)	O(n^2)	O(n^2)
버블 정렬	O(n^2)	O(n^2)	O(n^2)
쉘 정렬	O(n)	O(n^1.5)	O(n^1.5)
퀵 정렬	O(nlog 2n)	O(nlog 2n)	O(n^2)
힙 정렬	O(nlog 2n)	O(nlog 2n)	O(nlog 2n)
합병 정렬	O(nlog 2n)	O(nlog 2n)	O(nlog 2n)
기수 정렬	O(dn)	O(dn)	O(dn)

- 최적의 정렬 방법은 정렬해야 할 데이터의 수, 크기, 타입에 따라 달라지므로 정렬 방법들의 장단점을 잘 이해하여 적합한 정렬을 사용할 수 있어야 합니다.

정렬 알고리즘별 실험 결과

- 정수 60000개 정렬

알고리즘	실행시간 (단위 : 초)
삽입 정렬	7.438
선택 정렬	10.842
버블 정렬	22.894
쉘 정렬	0.056
힙 정렬	0.034
합병 정렬	0.026
퀵 정렬	0.014

- 삽입, 선택, 버블 정렬은 정렬속도가 느려서 비효율적입니다.

정렬 알고리즘별 안정성, 추가 메모리 필요 여부

알고리즘	안정성	추가 메모리 필요
삽입 정렬	O	X
선택 정렬	X	X
버블 정렬	O	X
쉘 정렬	X	X
힙 정렬	X	X
합병 정렬	O	O
퀵 정렬	X	X
기수 정렬	O	O

- 안정성 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬