정렬 알고리즘

정렬 알고리즘은 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 정렬된 리스트에서 동작하는 다른 알고리즘을 최적화하는 데 중요하다. 또한 데이터의 정규화나 의미 있는 결과물을 생성하는 데 유용하게 사용된다.

배너 광고

개요

정렬 알고리즘은 데이터를 특정 기준에 따라 순서대로 나열하는 기법이다. 이는 검색 효율성을 향상시키고 데이터 중복 관리 및 분석을 용이하게 한다. 컴퓨터 과학 교육 과정에서는 점근 표기법, 분할 정복 알고리즘, 자료 구조 등 핵심 개념을 소개하는 입문 주제로 널리 활용된다.

안정 정렬과 불안정 정렬의 차이를 보여주는 예시 — 데이터의 상대적 순서 유지 여부에 따른 안정 정렬과 불안정 정렬의 비교정렬 알고리즘 - 나무위키

역사

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

주요 분류

정렬 알고리즘은 시간 복잡도와 동작 방식에 따라 다음과 같이 분류할 수 있다.

시간 복잡도에 따른 분류

$O(n^2)$ 계열: 버블 정렬, 선택 정렬, 삽입 정렬 등이 포함된다. 구현이 간단하여 소량의 데이터 처리에 적합하다.
$O(n \log n)$ 계열: 병합 정렬, 힙 정렬, 퀵 정렬 등이 해당한다. 대규모 데이터 처리에 효율적이다.
기타: 계수 정렬, 기수 정렬 등 비교에 기반하지 않는 알고리즘은 특정 조건에서 더 나은 성능을 보일 수 있다.

안정성에 따른 분류

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

대표적인 알고리즘

알고리즘	평균 시간 복잡도	최악 시간 복잡도	특징
버블 정렬	$O(n^2)$	$O(n^2)$	인접한 두 요소를 비교하며 교환
삽입 정렬	$O(n^2)$	$O(n^2)$	요소를 하나씩 탐색하여 적절한 위치에 삽입
퀵 정렬	$O(n \log n)$	$O(n^2)$	피벗을 기준으로 리스트를 분할하여 정렬
병합 정렬	$O(n \log n)$	$O(n \log n)$	리스트를 반으로 나누어 각각 정렬 후 결합

병합 정렬의 분할 및 정복 과정 도식 — 데이터를 분할하고 다시 정렬하며 합치는 병합 정렬의 동작 과정정렬 알고리즘 - 나무위키

참고 자료

5건