정렬 알고리즘 (Sort) 정의

 전산학과 수학에서 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다.

 1. 출력은 비 내림차순(각각의 원소가 완전 순서에 의해 이전의 원소보다 작지 않은 순서)이다.
 2. 출력은 입력을 재배열하여 만든 순열이다.

 컴퓨터의 초창기에, 정렬 알고리즘은 연구하기에 대단히 매력적인 주제였다. 간단하고 익숙하지만, 그것을 효율적으로 풀어내기는 복잡하기 때문일지도 모른다. 예를 들어, 거품 정렬은 1956년에 분석되었다. 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다. 정렬 알고리즘은 다양한 핵심 알고리즘 개념 (점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등) 을 소개하는 데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다.

(참고 : http://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC)

 

 위키백과의 설명에도 나와 있듯이 정렬 알고리즘은 핵심 알고리즘 개념을 이해하기 좋다. 이에, 정렬 알고리즘을 하나씩 정리하고, 그 이해를 바탕으로 더욱 복잡하고 효율이 좋은 알고리즘을 만들어나가려 한다. 정렬의 이해와 구현을 넘어서서, 각각의 원리와 그 효율을 비교, 분석하려 한다.