[CS] 정렬의 종류

버블정렬 (Bubble Sort)

-인접한 두 요소를 비교하여 정렬하는 방식이다.
-시간 복잡도가 𝑂(𝑛^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

선택정렬 (Selection Sort)

-주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 바꿔 정렬하는 방식이다.
-시간 복잡도가 𝑂(𝑛^2)이다.

삽입 정렬 (Insertion Sort)

-배열을 두 부분으로 나누어(정리시작 전 후), 정렬된 부분에 요소를 삽입하여 정렬하는 방식이다.
-시간 복잡도가 𝑂(𝑛^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

합병 정렬 (Merge Sort)

-배열을 반으로 나누어 각각을 정렬한 후 병합하는 방식이다.
-시간 복잡도는 O(n log n)이다.
-제자리 합병정렬의 경우엔 시간 복잡도는 O(n log^2 n)이다.

퀵 정렬 (Quick Sort)

-기준이 되는 점(피벗)을 구하여 기준에 비해 작은 값과 큰 값을 분할하여 정렬하는 방식이다.
-시간 복잡도는 평균 O(n log n), 최악 O(n^2)이다.

힙 정렬 (Heap Sort)

-힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순:최소 힙, 오름차순:최대힙을 구성한다.
-시간 복잡도는 O(n log n)이다.
-추가 메모리 공간이 거의 필요하지 않다.

쉘 정렬 (Shell Sort)

-삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화된 형태로, 자료를 subfile로 쪼개서, 각 subfile에서 정렬을 수행하는 방식이다.
-시간 복잡도는 O(n log n)에서 O(n^2) 사이이다.

번외 : 시간복잡도 구하기

빅오 표기법에서는 상수와 낮은 차수의 항을 무시하고, 가장 큰 차수의 항만을 고려한다. 예를들어 버블정렬은 실제로 효율을 구해보면 시간복잡도가 n(n-1)/2인데, 상수와 낮은차수를 제외하면 n^2이다.