정렬 알고리즘

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

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

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

분류[편집]

정렬 알고리즘은 보통 아래와 같은 기준으로 분류 된다.

종류[편집]

정렬 알고리즘은 그 특징에 따라 몇 가지로 분류할 수 있다.

비교 정렬[편집]

비교 정렬은 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘들을 일컫는다. 예를 들어 거품 정렬(bubble sort)은 비교하는 원소들이 숫자거나, 문자열이거나, 심지어는 복잡한 객체에 대해서도 순서가 결정되어 있다면 적용할 수 있다.

비교 정렬 알고리즘들은 아무리 빨라도 최악의 경우 시간을 필요로 한다. 이는 이 알고리즘들을 결정 트리의 형태로 기술할 수 있다는 점에서 증명할 수 있는데, 개의 원소들의 순열가지로 이들을 잎 노드로 가지는 결정 트리의 깊이는 스털링 근사에 따라 적어도 이어야 하기 때문이다.

비교 정렬이 아닌 알고리즘들은 이런 시간 복잡도의 제약이 없지만, 대신 다른 제약을 가질 수 있다. 예를 들어 기수 정렬은 사전순으로 표기하고 분리하기 쉬운 숫자나 문자열에 대해서는 효과적이지만, 그렇지 않은 객체들에 대해서는 일반 비교 정렬보다 느릴 수 있다.

제자리 정렬[편집]

제자리 정렬은 원소들의 개에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘들을 의미하며, 제자리 알고리즘의 범위에 포함된다. 예를 들어 삽입 정렬은 이미 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이 과정에서 원소들을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 원소가 저장되는 공간과 루프 변수 정도에 불과하다.

퀵 정렬은 제자리 알고리즘의 정의에 따라서 제자리 정렬로 분류할 수도 있고 아닐 수도 있다. 퀵 정렬은 재귀적으로 정의되기 때문에 스택을 사용하게 되는데, 이 스택의 깊이는 개의 원소에 대해 에 비례하므로 전체 공간 복잡도는 상수가 아니다. 하지만 실용적인 의미에서 퀵 정렬은 상대적으로 작은 메모리만을 더 사용하기 때문에 흔히 제자리 정렬로 기술된다.

온라인 정렬[편집]

온라인 정렬은 모든 원소들이 처음부터 주어지지 않고 차례대로 들어 오는 경우도 처리할 수 있는 정렬 알고리즘을 의미하며, 온라인 알고리즘에 해당된다. 대표적으로 합병 정렬은 이미 정렬된 여러 개의 부분 리스트를 관리하다가 매 원소가 들어 올 때마다 적절한 리스트에 추가하고 필요하면 리스트들을 합병하는 식으로 온라인 정렬로 만들 수 있다.

정렬 알고리즘의 목록[편집]

참조[편집]