[Algorithm] 정렬

정렬이란, 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순)이나 혹은 그 반대로(내림차순) 재배열하는 작업을 의미한다.

종류

대표적인 정렬 알고리즘으로 버블정렬, 카운팅정렬, 선택정렬, 퀵정렬, 삽입정렬, 병합정렬 등이 있다. 각각의 정렬을 비교하면 다음과 같다(출처 : SW Expert Academy Learn 5차시).

알고리즘	평균	최악	알고리즘 기법	특징	안정/불안정
버블	$O(n^2)$	$O(n^2)$	비교, 교환	코딩이 가장 쉬움.	안정
선택	$O(n^2)$	$O(n^2)$	비교, 교환	교환의 횟수가 버블, 삽입보다 적음.	불안정
삽입	$O(n^2)$	$O(n^2)$	비교, 교환	n의 개수가 적을 때 효과적.	안정
퀵	$O(nlogn)$	$O(n^2)$	분할 정복	최악의 경우 O(n^2)이지만, 평균적으로는 가장 빠름.	불안정
병합	$O(nlogn)$	$O(nlogn)$	분할 정복	연결 리스트의 경우 가장 효율적.	안정
카운팅	$O(n+k)$	$O(n+k)$	비교환	n이 비교적 작을 때만 가능.	안정

일단 위에 등장하지 않은 정렬에 대해서는 여기를 참고하며 공부하자.

분류

안정 vs. 불안정

• 정렬 후에 기존의 순서가 보장되면 안정 정렬, 그렇지 않으면 불안정 정렬.
• 즉, 중복 값이 있을 때, 그 중복된 값의 순서가 바뀌지 않으면 안정 정렬, 바뀌면 불안정 정렬이다.

초기 값	안정 정렬	불안정 정렬
2 5 1 3 4 3	1 2 3 3 4 5	1 2 3 3 4 5

in-place

• 입력 리스트 내부에서 정렬이 이루어지는 알고리즘.
• 정렬 도중 별도 저장 공간을 필요로 하지 않는다.