정렬 알고리즘
위키백과 ― 우리 모두의 백과사전.
전산학과 수학에서 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다.
- 출력은 비 내림차순(각각의 원소가 완전 순서에 의해 이전의 원소보다 작지 않은 순서)이다;
- 출력은 입력을 재배열하여 만든 순열이다.
컴퓨터의 초창기에, 정렬 알고리즘은 연구하기에 대단히 매력적인 주제였다. 간단하고 익숙하지만, 그것을 효율적으로 풀어내기는 복잡하기 때문일지도 모른다. 예를 들어, 거품 정렬은 1956년에 분석되었다[1]. 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다(예를 들어, 라이브러리 정렬은 2004년에 발표되었다). 정렬 알고리즘은 다양한 핵심 알고리즘 개념 — 점근 표기법, 분할 정복 알고리즘, 자교 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등 — 을 소개하는데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다.
[편집] 정렬 알고리즘의 종류
정렬 알고리즘을 특징별로 분류하면, 크게 안정 정렬과 불안정 정렬로 나눌 수 있다. 예를 들어, 다음과 같은 원소들이 있다고 할 때,
(4, 1) (3, 7) (3, 1) (5, 6)
이것을 앞의 숫자를 기준으로 정렬할 때에 다음과 같은 두 가지의 가능성이 존재한다.
(3, 7) (3, 1) (4, 1) (5, 6) (순서 보존) (3, 1) (3, 7) (4, 1) (5, 6) (순서 변경)
(3, 7)과 (3, 1)은 앞의 숫자가 같기 때문에 두 가지가 모두 가능하고, 이 때에 원래의 순서가 보존되는 경우를 안정 정렬이라고 한다. 이와는 반대로 원래의 순서를 바꿀 가능성이 있다면 불안정 정렬이라고 한다.
[편집] 안정 정렬
- 거품 정렬
- 삽입 정렬
- 버킷 정렬
- 병합 정렬
- 기수 정렬
