정렬 알고리즘

정렬 알고리즘은 데이터 집합을 일정한 기준(숫자 크기, 알파벳 순 등)에 따라 재배열하는 기법이다. 정렬의 주된 목적은 탐색 효율성을 높이는 데 있다. 정렬된 데이터에서는 원하는 항목을 더 빠르고 쉽게 찾을 수 있기 때문이다. 또한 데이터 중복 관리, 통계 처리, 시각화 등 다양한 데이터 분석 과정에서 기초적인 단계로 활용된다.

컴퓨팅 초기부터 효율적인 정렬을 위한 연구가 지속되었다. 1951년경 에니악(ENIAC)과 유니박(UNIVAC) 개발에 참여했던 베티 홀버튼이 초기 정렬 알고리즘 개발자 중 한 명으로 기록되어 있다. 거품 정렬은 1956년에 분석되었으며, 21세기에도 팀소트(2002년)나 라이브러리 정렬(2006년 출판)과 같은 새로운 알고리즘이 발명되어 널리 쓰이고 있다.

정렬 알고리즘은 동작 방식과 자원 사용량에 따라 여러 방식으로 분류된다.

안정성(Stability)

동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 유지되면 안정 정렬(Stable Sort), 유지되지 않으면 불안정 정렬(Unstable Sort)이라고 한다. 삽입 정렬과 병합 정렬은 안정적이지만, 퀵 정렬과 선택 정렬은 불안정 정렬에 속한다.

메모리 사용 방식

• 내부 정렬(Internal Sort): 모든 데이터가 주기억장치(RAM) 내에서 처리되는 방식이다.
• 외부 정렬(External Sort): 데이터 양이 너무 많아 보조기억장치를 활용하며 부분적으로 정렬하는 방식이다.
• 제자리 정렬(In-place Sort): 입력 크기에 비례하는 추가적인 메모리 공간을 거의 사용하지 않는 알고리즘을 의미한다.

구현 방식

• 비교 기반 정렬: 요소 간의 크기를 직접 비교하여 순서를 결정한다. 이론적으로 $O(n \log n)$보다 나은 성능을 낼 수 없다.
• 비비교 기반 정렬: 계수 정렬이나 기수 정렬처럼 키 값을 직접 계산하여 정렬하며, 특정 조건에서 $O(n)$의 성능을 보이기도 한다.