정렬(Sort) 알고리즘

 

4.1 선택 정렬 (Selection Sort)

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 배열에서 가장 작은(또는 큰) 값을 찾아 맨 앞(또는 맨 뒤)과 교환하는 과정을 반복합니다. 즉, 전체 배열에서 최솟값을 찾아 첫 번째 위치와 바꾸고, 그 다음에는 두 번째부터 끝까지에서 최솟값을 찾아 두 번째 위치와 바꾸는 방식입니다. 이 과정을 배열의 끝까지 반복하면 정렬이 완료됩니다. 비교 횟수는 항상 n(n-1)/2로, 데이터의 정렬 정도와 상관없이 느린 편이지만, 구현이 매우 쉽고 추가 메모리가 거의 필요하지 않다는 장점이 있습니다.

4.2 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하여 크기가 잘못된 경우 서로 교환하는 과정을 반복하는 정렬 알고리즘입니다. 한 번의 패스가 끝나면 가장 큰 값이 배열의 끝으로 "버블"처럼 올라가게 됩니다. 이 과정을 배열이 완전히 정렬될 때까지 반복합니다. 최악의 경우와 평균의 경우 모두 시간 복잡도가 O(n²)로 비효율적이지만, 구현이 매우 쉬워서 교육용으로 많이 사용됩니다. 만약 한 번의 패스에서 교환이 한 번도 일어나지 않으면 배열이 이미 정렬된 것이므로, 그 즉시 종료할 수 있습니다.

4.3 삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 두 번째 원소부터 시작하여, 현재 원소를 그 앞에 있는 정렬된 부분 배열에서 적절한 위치에 "삽입"하는 방식으로 동작합니다. 즉, 각 단계마다 정렬된 부분 배열이 한 칸씩 늘어나며, 새로 추가되는 원소를 앞쪽으로 이동시키며 삽입합니다. 이미 정렬된 배열에 대해서는 매우 빠르며(최선의 경우 O(n)), 데이터가 거의 정렬되어 있을 때 효율적입니다. 하지만 역순으로 정렬된 경우에는 O(n²)의 시간이 소요됩니다.

4.4 병합 정렬 (Merge Sort)

병합 정렬은 "분할 정복(Divide and Conquer)" 전략을 사용하는 정렬 알고리즘입니다. 배열을 반으로 계속 쪼개서 더 이상 쪼갤 수 없을 때까지 분할한 후, 쪼개진 배열들을 다시 합치면서 정렬하는 방식입니다. 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 병합(merge) 과정이 핵심입니다. 시간 복잡도는 항상 O(n log n)으로 매우 효율적이며, 안정 정렬(stable sort)이기도 합니다. 다만, 추가적인 메모리 공간이 필요하다는 단점이 있습니다.

4.5 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복을 이용한 매우 빠른 정렬 알고리즘입니다. 피벗(pivot)이라는 기준값을 하나 정하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다. 이 과정을 각 부분 배열에 대해 재귀적으로 반복하여 전체 배열을 정렬합니다. 평균적으로 매우 빠르며 O(n log n)의 시간 복잡도를 가지지만, 피벗 선택이 불균형하게 이루어질 경우(예: 이미 정렬된 배열에서 첫 번째 원소를 피벗으로 선택)에는 O(n²)까지 느려질 수 있습니다. 추가 메모리 사용이 적고, 실제로 많은 라이브러리에서 사용되는 정렬입니다.

4.6 힙 정렬 (Heap Sort)

힙 정렬은 완전 이진 트리의 한 종류인 힙(Heap) 자료구조를 이용한 정렬 알고리즘입니다. 먼저 배열을 최대 힙(또는 최소 힙)으로 변환한 뒤, 루트(최대값 또는 최소값)를 배열의 끝으로 보내고, 남은 부분에 대해 다시 힙을 재정렬하는 과정을 반복합니다. 힙의 삽입과 삭제 연산이 O(log n)이므로 전체 정렬은 O(n log n)에 수행됩니다. 추가 메모리 공간이 거의 필요 없고, 항상 일정한 시간 복잡도를 보장하지만, 안정 정렬은 아닙니다.

4.7 기수 정렬 (Radix Sort)

기수 정렬은 비교 기반이 아닌, 자릿수를 기준으로 여러 번의 정렬을 반복하는 방식입니다. LSD(Least Significant Digit) 방식은 가장 낮은 자릿수부터, MSD(Most Significant Digit) 방식은 가장 높은 자릿수부터 정렬합니다. 각 자릿수별로 계수 정렬(Counting Sort)과 같은 안정 정렬을 사용하여 정렬을 반복합니다. 정수, 문자열 등 자릿수가 명확한 데이터에 적합하며, 시간 복잡도는 O(d(n+k)) (d: 자릿수, k: 기수 범위)로 매우 빠를 수 있습니다. 단, 비교 기반이 아니므로 범용성은 떨어집니다.