정렬 알고리즘

정렬 알고리즘은 컴퓨터 과학에서 자료(예: 숫자, 문자열 등)를 특정 기준(예: 크기, 사전 순서 등)에 따라 일정한 순서(오름차순, 내림차순 등)로 재배열하는 문제 또는 이를 해결하기 위한 절차나 방법(알고리즘)을 의미한다. 정렬되지 않은 자료를 정렬된 상태로 만듦으로써, 해당 자료에 대한 검색, 분석, 기타 연산 등을 효율적으로 수행할 수 있게 된다.

다양한 정렬 알고리즘이 존재하며, 각 알고리즘은 다음과 같은 기준에 따라 성능과 특성이 달라진다:

• 시간 복잡도 (Time Complexity): 입력 데이터의 크기가 커짐에 따라 알고리즘의 실행 시간이 얼마나 증가하는지를 나타낸다. 일반적으로 최선, 평균, 최악의 경우 시간 복잡도를 분석한다. O(n log n)이나 O(n²) 등이 대표적인 시간 복잡도 표현이다.
• 공간 복잡도 (Space Complexity): 알고리즘을 실행하는 데 필요한 추가적인 메모리 공간의 양이다. 입력 배열 외에 추가적인 공간이 거의 필요 없는 경우 '제자리 정렬(In-place Sort)'이라고 한다.
• 안정성 (Stability): 값이 같은 두 요소가 있을 때, 정렬 후에도 그들의 상대적인 순서가 정렬 전과 동일하게 유지되는지 여부이다. 안정적인 정렬은 복합적인 기준에 따라 여러 번 정렬할 때 유용하다.
• 비교 기반 정렬 (Comparison Sort): 두 요소를 비교하여 순서를 결정하는 알고리즘이다. 대부분의 일반적인 정렬 알고리즘(버블, 삽입, 선택, 힙, 합병, 퀵 정렬 등)이 여기에 속하며, 이론적으로 최적의 시간 복잡도는 Ω(n log n)이다.
• 비비교 기반 정렬 (Non-comparison Sort): 요소 간의 비교 없이 다른 속성(예: 값의 범위, 자릿수 등)을 이용하여 정렬한다. 계수 정렬(Counting Sort), 기수 정렬(Radix Sort) 등이 있으며, 특정 조건(예: 값이 정수이고 범위가 제한적)에서는 O(n)에 가까운 성능을 보일 수 있다.

대표적인 정렬 알고리즘의 예시는 다음과 같다:

• 버블 정렬 (Bubble Sort)
• 선택 정렬 (Selection Sort)
• 삽입 정렬 (Insertion Sort)
• 합병 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 힙 정렬 (Heap Sort)
• 계수 정렬 (Counting Sort)
• 기수 정렬 (Radix Sort)

어떤 정렬 알고리즘을 사용할지는 데이터의 특성(크기, 분포, 정렬 상태), 요구되는 성능(시간, 공간), 안정성 필요 여부 등을 고려하여 결정된다. 정렬은 데이터베이스, 검색 알고리즘(이진 탐색 등), 데이터 분석, 운영체제 스케줄링 등 다양한 컴퓨터 과학 및 응용 분야에서 핵심적인 기반 기술로 활용된다.