선택 정렬
- 레코드의 이동 횟수를 줄이려는 목적에서 개발되었으며, 자료 중에서 최솟값 또는 최댓값을 선택해 가면서 리스트의 처음이나 마지막으로 이동하는 방식
- 키 비교 횟수를 정확히 산출할 수 있으나 정렬 도중에 이미 정렬이 완료된 경우라도 이를 확인할 수가 없다.
최대 비교 횟수는 n(n-1)/2 이므로 O(n^2)이 된다.
거품 정렬
- 인접한 레코드의 키 값을 비교해서 그 크기에 따라 교환하는 방식으로, 각 단계마다 가장 큰(작은) 키 값을 갖는 레코드를 마지막에 위치시킨다.
- 이미 정렬이 부분적으로 완료되어 있는 상태에서는 사실상 이들 레코드들의 키 값을 비교할 필요가 없는데도 불필요하게 비교 작업이 반복되는데, 이때 flag를 사용하면 이런 단점을 보완할 수 있다.
- 이렇게 하면 n개의 자료를 정렬하는 경우 무조건적으로 n(n-1)/2번을 비교하지 않아도 되고, 최악의 경우에만 n(n-1)/2번 비교하면 된다.
최대 비교 횟수는 n(n-1)/2 이므로 O(n^2)이 된다.
삽입 정렬
- 이미 정렬된 레코드에 새로운 레코드를 삽입시켜 다시 정렬하는 기법이다.
- 최초의 자료가 대부분 정렬되어 있는 경우 효과적이다.
최대 비교 횟수는 리스트가 완전히 역순인 n(n-1)/2 이므로 이 된다.
쉘 정렬
- 버블 정렬에서 어떤 데이터가 제 위치에서 멀리 떨어져 있을 때, 많은 비교와 교환이 일어나는 단점을 보완한 기법으로, 멀리 떨어진 데이터끼리도 비교, 교환될, 수 있도록 하였다.
- 삽입 정렬을 확장한 기법으로, 자료를 매개변수의 값에 따라 여러 부분으로 나누어 각 부분을 삽입 정렬하는 방법이다.
- 상위의 값과 하위의 값은 매개 변수를 기준으로 교환한다. 즉, 매개변수(파라미터) 값에 의해 입력 리스트는 여러 개의 서브 리스트로 분리되고 단계적으로 정렬되며 매개변수의 값이 1이 되면 종료한다.
- 수행 시간 복잡도는 평균, 최악의 경우 모두 O(n^2)이다.
힙 정렬
- 입력 자료를 완전 이진트리로 구성하여 가장 큰(작은) 키 값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법
- 최대(소) 힙트리는 각 노드의 키 값이 그 자식의 키 값보다 작지(크지) 않은 트리이다. 즉, 힙의 정의에 의해 최소 트리의 루트는 그 트리에서 가장 작은 키 값을 가지며, 최대 트리의 루트는 가장 큰 값을 가진다.
- 평균, 최악의 수행 시간 모두 O(nlogn)이 된다.
2원 합병 정렬
- 정렬할 배열을 둘로 분할하여 왼쪽 부분 배열에 대하여 합병 정렬 알고리즘을 순환 호출하여 정렬한 다음 오른쪽 부분 배열에 대하여 같은 방법으로 정렬 알고리즘을 순환 호출하여 정렬한 후 이 두 부분 배열을 하나로 합치는 정렬 기법
- 정렬된 두 개 이상의 서브 파일을 합병하여 하나의 정렬된 파일을 생성하는 방법
- 2원 합병 정렬은 1회전 수행 시마다 파일의 크기가 반씩 줄어들므로 수행 횟수는 logn이고 수행 시간은 O(nlogn)이다.
- 분할 정복 방식의 알고리즘이다.
퀵 정렬
- 입력 자료를 특정한 키(제어키) 보다 작은 값을 갖는 자료들과 큰 값을 갖는 자료로 분리하여 한 개의 파일을 논리적으로 두 개의 파일로 재배열하고 각각 서브 파일에 대해 순환적으로 퀵 정렬을 사용한다.
- 정렬을 수행하기 위해 리스트 분리 기준이 되는 임의의 한 원소(pivot)를 선정해야 한다.
- 문제 해결을 위해 대상을 여러 개의 작은 부분으로 나누어 각 문제를 해결한 후 그 결과를 합병하여 원하는 해를 구하는 방법이다. 즉, 분할과 정복 기법을 순환적으로 적용한다.
- 이미 정렬된 리스트를 대상으로 퀵 정렬을 하면 최악의 경우로 수행 시간은 O(n^2)이다.
기수 정렬(버킷 정렬)
- 하나의 레코드를 구성하고 있는 자릿수(Digit)만큼의 버킷을 준비하여 각 자릿수들을 해당 버킷에서 순서대로 분류하는 정렬 방법으로서 보통 버킷 정렬이라고 한다.
- 대상 자료의 각 자릿수 값을 조사하여 자릿수 별로 분배하여 정렬하는 방식으로, 비교 정렬 기법이 아니다.
- 비교해서 정렬하는 다른 정렬법과 다르게 기수 정렬은 큐를 이용한 분배법을 사용한다.
