정렬 알고리즘 - 2
셸 정렬
셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하여 좀 더 빠르게 정렬하는 알고리즘이다.
단순 삽입 정렬의 특징 살펴보기
다음 배열에서 2, 3, 4, 5까지는 이미 정렬이 되어 있는 상태기 때문에 요소를 이동하지 않지만 0을 삽하려면 총 6회에 걸쳐 요소를 이동(대입)해야 한다.
특징
A : 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠르다(장점)
B : 삽입할 곳이 멀리 떨어지면 이동(대입)하는 횟수가 많다.(단점)
따라서 셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완한 정렬 알고리즘으로, 먼저 일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다.
먼저 4칸 떨어져 있는 요소를 모아 배열을 4개의 그룹 ({8, 7}, {1, 6}, {4, 3}, {2, 5})으로 나누고 각 그룹별로 정렬한다. 1은 {8, 7}을 {7, 8}로 2는 {1, 6}을 {1, 6}으로, 3은 {4, 3}을 {3, 4}로 4는 {2, 5}를 {2, 5}로 정렬한 상태다.
이렇게 4칸 떨어진 요소를 하나의 그룹으로 묶어 정렬하는 방법을 '4-정렬'이라고 한다. 아직 정렬을 마친 상태는 아니지만 정렬을 마친 상태에 가까워지는 것을 볼 수 있다.
'4-정렬'을 마친 상태에서 2칸 떨어진 요소를 모아 두 그룹({7, 3, 8, 4}, {1, 2, 6, 5})으로 나누어 '2-정렬'을 하는 과정이다.
'2-정렬'을 실행한 뒤 가각의 그룹은 ({3, 4, 7, 8}, {1, 2, 5, 6})으로 정렬된다.
마지막으로 '1-정렬'을 적용하면 정렬을 마치게 된다.
- 각각의 정렬을 'h-정렬'이라고 한다.
'1-정렬'은 단순 삽입 정렬과 같다.
여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해서이다. 정렬해야 하는 횟수는 늘지만 전체적으로 요소의 이동 횟수가 줄어들어 효율적으로 정렬할 수 있다.
알고리즘 코드
import java.util.Scanner;
public class ShellSort {
static void shellSort(int[] a, int n) {
for(int h = n / 2; h > 0; h /= 2 ) { // 4-, 2-, 1-으로 반반으로 나눠 정렬
for(int i = h; i < n; i++) {
int j;
int tmp = a[i];
for(j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("셸 정렬 (버전 1) ");
System.out.print("요솟수 : ");
int nx = sc.nextInt();
int[] x= new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
shellSort(x, nx); // 배열 x를 셸 정렬
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < nx; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
중복값(h값) 선택하기
위에서는 h값을 4 > 2 > 1 처럼 변화시켰다.
h값은 n부터 감소시켜 마지막에 1이되면 된다. 그러면 h값을 어떤 수열로 감소시켜야 좀 더 효율적인 정렬을 할 수 있을까?
바로 h값이 서로 배수가 되지 않도록 만들면 된다. 이렇게 하면 요소가 충분히 섞여 효율적으로 정렬할 수 있다. 다음 수열을 사용하면 셸 정렬 알고리즘을 간단하게 만들 수 있을 뿐만 아니라 효율적인 결과도 얻을 수 있다.
h = ... > 121 > 40 > 13 > 4 > 1
이 수열을 뒤에서부터 살펴보면 1부터 시작해 3배한 값에 1을 더하는 수열이라는 것을 알 수 있다.
n * 3 + 1
알고리즘 코드
import java.util.Scanner;
public class ShellSort {
static void shellSort(int[] a, int n) {
int h;
// 1
for(h = 1; h < n; h = h * 3 + 1);
// 2
for(; h < n; h /= 3)
for(int i = h; i < n; i++) {
int j;
int tmp = a[i];
for(j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("셸 정렬 (버전 2) ");
System.out.print("요솟수 : ");
int nx = sc.nextInt();
int[] x= new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
shellSort(x, nx); // 배열 x를 셸 정렬
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < nx; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
1의 for문은 h의 초깃값을 구한다. 1부터 시작해 값을 3배하고 1을 더하면서 n을 넘지 않는 가장 큰 값을 h에 대입한다.
2의 for문이 버전 1과 다른 점은 h값이 변한느 방법이다.(반복할 때마다 h값을 3으로 나눈다.) 반복하여 마지막에 h값은 1이된다.
셸 정렬의 시간 복잡도는 O(n^1.25)으로, 기존 시간 복잡도인 O(n^2)에 비해 매우 빠르다. 그리고 이 알고리즘은 멀리 떨어져 있는 요소를 교환하므로 안정적이지 않다.
퀵 정렬
퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되고 있다.
피벗(pivot) : 그룹을 나누는 기준
배열을 두 그룹으로 나누기
배열을 나누는 순서는 피벗을 x, 왼쪽 끝 요소를 pl, 오른족 끝 요소의 인덱스 pr이라고 지정한다.
그룹을 나누려면 피벗 이하의 요소를 배열 왼족으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다.
- a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다.
- a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다.
그 결과로는 pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점이고, pr이 위치한 지점은 피벗값 이하의 요소가 있는 지점이 된다.
여기서 왼쪽과 오른쪽 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다. 그러면 피벗 이하의 값은 왼쪽으로 이동하고, 피벗 이상의 값은 오른쪽으로 이동하게 된다.
- 피벗 이하의 그룹 : a[0], ..., a[pl - 1]
- 피벗 이상의 그룹 : a[pr + 1], ..., a[n - 1]
또 그룹을 나누는 작업이 끝난 다음 pl > pr + 1이면 다음과 같은 그룹이 생길 수 있다.
- 피벗과 같은 값을 갖는 그룹 : a[pr + 1], ..., a[pl - 1]
알고리즘 코드
import java.util.Scanner;
public class Partition {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 배열을 나눔
static void partiotion(int[] a, int n) {
int pl = 0; // 왼쪽 커서
int pr = n - 1; // 오른쪽 커서
int x = a[n / 2]; // 피벗(가운데 요소)
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr)
swap(a, pl++, pr--);
}while(pl <= pr);
System.out.println("피벗값은 " + x + "입니다.");
System.out.println("피벗 이하의 그룹");
for(int i = 0; i <= pl - 1; i++)
System.out.print(a[i] + " ");
System.out.println();
if(pl > pr + 1) {
System.out.println("피벗과 같은 그룹");
for(int i = pr + 1; i <= pl; i++) // a[pr + 1] ~ a[pl - 1]
System.out.print(a[i] + " ");
System.out.println();
}
System.out.println("피벗 이상의 그룹");
for(int i = pr + 1; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열을 나눕니다.");
System.out.print("요솟수: ");
int nx = sc.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
partiotion(x, nx);
}
}
퀵 정렬 구현하기
위에서는 배열을 피벗 기준으로 나누기만 했고 이제 좀 더 발전시켜 퀵 정렬을 만들어보겠다.
배열 길이가 9인 배열을 나누면 a[0] ~ a[4]와 a[5]~a[8]로 나눠진다. 그러고 나서 이 두 그룹을 다시 같은 방법으로 나는다.
a[0]~a[4]를 두 그룹으로 나누고, a[5]~a[8]을 두 그룹으로 나눠서 요솟수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로 요솟수가 2개 이상인 그룹만 나누면 된다. 따라서 아래처럼 배열을 반복해서 나누게 된다.
- pr이 맨 앞보다 오른쪽에 있으면 (left < pr)왼쪽 그룹을 나눈다.
- pl이 맨 뒤보다 왼쪽에 있으면(pl < right) 오른쪽 그룹으로 나눈다.
※ 가운데 그룹은 나눌 필요가 없으므로 제외시킨다.
이 알고리즘은 분할 정복 알고리즘이므로 재귀호출을 사용해 간결하게 구현할 수 있다.
퀵 정렬 알고리즘 코드
import java.util.Scanner;
public class QuickSort {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 배열을 나눔
static void quickSort(int[] a, int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr)
swap(a, pl++, pr--);
}while(pl <= pr);
if(left < pr) quickSort(a, left, pr);
if(pl < right) quickSort(a, pl, right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열을 나눕니다.");
System.out.print("요솟수: ");
int nx = sc.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
quickSort(x, 0, nx - 1);
System.out.println("오름차순으로 정렬");
for(int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
퀵 정렬에서 배열을 나누는 과정 출력하기
static void quickSort(int[] a, int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
System.out.printf("a[%d]~a[%d]: {", left, right);
for(int i = left; i < right; i++)
System.out.printf("%d , " + a[i]);
System.out.printf("%d}\n", a[right]);
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr)
swap(a, pl++, pr--);
}while(pl <= pr);
if(left < pr) quickSort(a, left, pr);
if(pl < right) quickSort(a, pl, right);
}추가
비재귀적 퀵 정렬 구현
static void quickSort(int[] a, int left, int right) {
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left);
rstack.push(right);
while(lstack.isEmpty() != true) {
int pl = left = lstack.pop(); // 왼쪽 커서
int pr = right = rstack.pop(); // 오른쪽 커서
int x = a[(left + right) / 2]; // 피벗
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr)
swap(a, pl++, pr--);
}while(pl <= pr);
if(left < pr) {
lstack.push(left);
rstack.push(pr);
}
if(pl < right) {
lstack.push(pl);
rstack.push(right);
}
}
}
- lstack : 나눌 범위의 왼쪽 끝(맨 앞) 요소의 인덱스를 저장하는 스택
- rstack : 나눌 범위의 오른쪽 끝(맨 뒤) 요소의 인덱스를 저장하는 스택
병합 정렬
배열의 앞부분과 뒷부분 둘로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘
예시로 3개의 배열이 있다고 하면 3개의 배열 a, b, c를 동시에 스캔한다. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb, pc이다.
1) 이 인덱스를 저장한 변수를 커서라고 부르겠다. 처음에는 첫 요소를 선택하므로 커서를 모두 0으로 초기화한다.
배열 a에서 선택한 요소 a[pa]와 배열 b에서 선택한 b[pb]를 비교해 작은 쪽 값을 c[pc]에 저장한다. pa가 더 작다고 치면 그 다음 pb, pc를 한 칸 나아가도록 하고 커서 pa는 그대로 둔다. 이런 작업을 반복한 후에 커서 pa가 배열 a의 끝에 다다르거나 커서 pb가 배열 b에 끝에 다다르면 while문에서 빠져나와 작업을 종료한다.
2) 이 while 문이 실행되는 것은 1)에서 배열 b의 모든 요소를 배열 c로 복사했으나 배열 a에는 아직 복사하지 않은 요소가 남아있는 경우이다. 커서 pa를 한 칸씩 나아가면서 복사하지 않은 모든 요소를 배열 c에 복사한다.
3) 이 while문이 실행되는 것은 1)에서 배열 a의 모든 요소를 배열 c로 복사했으나 배열 b에는 아직 복사하지 않은 요소가 남아 있는 경우이다. 커서 pb를 한 칸씩 나아가면서 복사하지 않은 모든 요소를 배열 c에 복사한다.
정렬을 마친 배열의 병합 코드
import java.util.Scanner;
public class MergeArray {
static void merge(int[] a, int na, int[] b, int nb, int[] c) {
int pa = 0;
int pb = 0;
int pc = 0;
while(pa < na && pb < nb) { // 작은 쪽 값을 C에 저장
c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
}
while(pa < na) // a에 남아있는 요소를 복사
c[pc++] = a[pa++];
while(pb < nb) // b에 남아있는 요소를 복사
c[pc++] = b[pb++];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] a = {2, 4, 6, 8, 11, 13};
int[] b = {1, 2, 3, 4, 9, 16, 21};
int[] c = new int[13];
System.out.println("두 배열을 병합");
merge(a, a.length, b, b.length, c);
System.out.println("배열 a와 b를 병합하여 배열 c에 저장");
System.out.println("배열 a: ");
for(int i = 0; i < a.length; i++)
System.out.println("a[" + i +"] = " + a[i]);
System.out.println("배열 b: ");
for(int i = 0; i < b.length; i++)
System.out.println("b[" + i + "] = " + b[i]);
System.out.println("배열 c: ");
for(int i = 0; i < c.length; i++)
System.out.println("c[" + i + "] = " + c[i]);
}
}
병합에 필요한 시간 복잡도는 O(n)이다.
병합 정렬 구현하기
정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
먼저 배열을 앞부분과 뒷부분으로 나눈다. 이 그름은 배열의 요솟수가 12개이므로 6개씩 두 부분으로 각각 나눈다.
나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다.
앞 부분과 뒷 부분으로 나누고 정렬하기
정렬을 마친 후
병합 정렬 알고리즘
배열의 요솟수가 2개 이상인 경우
- 배열의 앞부분을 병합 정렬로 정렬한다.
- 배열의 뒷부분을 병합 정렬로 정렬한다.
- 배열의 앞부분과 뒷부분을 병합한다.
병합 정렬 알고리즘 코드
import java.util.Scanner;
public class MergeSort {
static int[] buff; // 작업용 배열
// a[left] ~ a[right]를 재귀적으로 병합 정렬
static void __mergeSort(int[] a, int left, int right) {
if(left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
// 재귀 호출
__mergeSort(a, left, center); // 배열의 앞부분을 병합 정렬
__mergeSort(a, center + 1, right); // 배열의 뒷부분을 병합 정렬
// 앞부분과 뒷부분을 병합
for(i = left; i <= center; i++)
buff[p++] = a[i];
while(i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while(j < p)
a[k++] = buff[j++];
}
}
// 병합 정렬
static void mergeSort(int[] a, int n) {
buff = new int[n]; // 작업용 배열을 생성
__mergeSort(a, 0, n - 1); // 배열 전체를 병합 정렬
buff = null; // 작업용 배열을 해제
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("병합 정렬");
System.out.print("요솟수 : ");
int nx = sc.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: " );
x[i] = sc.nextInt();
}
mergeSort(x, nx); // 배열 x를 병합 정렬
System.out.println("오름차순 정렬");
for(int i = 0; i < nx; i++)
System.out.println("x[" + i + "]=" + x[i]);
}
}
시간 복잡도
배열 병합의 시간 복잡도는 O(n)이다. 데이터의 요솟수가 n개일 때 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간 복잡도는 O(n lon n)이라고 할 수 있다.
병합 정렬은 서로 떨어져 있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이라고 할 수 있다.
힙 정렬
선택 정렬을 응용한 알고리즘으로 힙의 특성을 이용해 정렬한다.
힙이란?
힙 정렬은 힙을 사용해 정렬하는 알고리즘으로 힙은 '부못값이 자식값보다 항상 크다'라는 조건을 만족하는 완전이진트리를 말한다.
힙에서 부모와 자식 사이의 대소 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않는다.
- 부모는 a[(i - 1) / 2]
- 왼쪽 자식은 a[i * 2 + 1]
- 오른쪽 자식은 a[i * 2 + 2]
힙 정렬 알아보기
힙 정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다. 다음과 같은 작업을 반복해서 수행한다.
- 힙에서 가장 큰 값인 루트를 꺼낸다.
- 루트 이외의 부분을 힙으로 만든다.
이 과정에서 꺼낸 값을 늘어놓으면 배열은 정렬을 마치게 된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘으로, 힙에서 가장 큰 값인 루트를 꺼낸 뒤 남은 요소에서 다시 가장 큰 값을 구해야 한다. 따라서 나머지 9개의 요소로 구성된 트리도 힙이 되도록 재구성해야 한다.
루트를 없애고 힙 상태 유지하기
힙에서 루트에 위치한 값을 꺼낸다. 다음 비어 있는 루트 위치로 힙의 마지막 요소를 옮긴다.
이후 루트로 옮긴 요소가 들어갈 위치로 요소를 이동시켜주면 힙 상태를 유지할 수 있다. 앞에서 말한 조건으로 부못값 >= 자식값을
기억하자
순서 정리
- 루트를 꺼낸다.
- 마지막 요소를 루트로 옮긴다.
- 자기보다 큰 값을 갖는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 이때 자식값이 작거나 잎에 다다르면 작업을 종료한다,
힙 정렬 알고리즘 살펴보기
- 변수 i값을 n - 1로 초기화한다.
- a[0]과 a[i]를 바꾼다.
- a[0], a[1], ..., a[i - 1]을 힙으로 만든다.
- i값을 1 감소시켜 0이 되면 끝낸다. 그렇지 않으면 '2'로 돌아간다.
배열을 힙으로 만들기
4를 루트로 하는 부분트리는 힙이 아니라고 가정하고 왼쪽 자식 8을 루트로 하는 부분트리 b와 오른쪽 자식 5를 루트로 하는 부분트리 c는 모두 힙이다.
이것은 아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙으로 만들 수 있다.
힙 정렬 프로그램 작성
import java.util.Scanner;
public class HeapSort {
// 배열 요소 a[idx1]과 a[idx2]의 값을 교환
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// a[left] ~ a[right]를 힙으로 만듦
static void downHeap(int[] a, int left, int right) {
int temp = a[left]; // 루트
int child; // 큰 값을 갖는 자식
int parent; // 부모
for(parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; // 왼쪽 자식
int cr = cl + 1; // 오른쪽 자식
child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 큰 쪽을 자식에 대입
if(temp >= a[child])
break;
a[parent] = a[child];
}
a[parent] = temp;
}
static void heapSort(int[] a, int n) {
for(int i = (n - 1) / 2; i >= 0; i--) // a[i] ~ a[n - 1]를 힙으로 만듦
downHeap(a, i, n - 1);
for(int i = n - 1; i > 0; i--) {
swap(a, 0, i); // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
downHeap(a, 0, i - 1); // a[0] ~ a[i - 1]을 힙으로 만듦
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("힙 정렬");
System.out.print("요솟수: ");
int nx = sc.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
heapSort(x, nx);
System.out.println("오름차순 정렬");
for(int i = 0; i < nx; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
downHeap 메서드
배열 a에서 a[left] ~ a[right]의 요소를 힙으로 만드는 메서드이다. 맨 앞에 있는 a[left]이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다.
heapSort 메서드
요솟수가 n개인 배열 a를 힙 정렬하는 메서드이다.
1) downHeap 메서드를 사용해 배열 a를 힙으로 만든다.
2) 루트(a[0])에 있는 가장 큰 값을 꺼내 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복해 정렬을 수행한다.
힙 정렬의 복잡도
단순 선택 정렬에서 가장 큰 요소를 선택하는 시간 복잡도는 O(n)이고 힙 정렬에서 '다시 힙으로 만들기' 작업을 수행하는 시간 복잡도는 O(log n)이다.
결국 '다시 힙으로 만들기' 작업을 반복하므로, 정렬 전체에 필요한 시간 복잡도는 단순 선택 정렬이 O(n^2)인 데 반해 힙 정렬은 O(n log n)이다.