정렬별 장단점 및 특징

1. 선택정렬

 

선택정렬은 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다.

따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식이다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림 차순으로 정렬되어 있는 자료를 오름 차순으로 재정렬할 때 최적이다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점이 있다.

시간복잡도 : O(N²)

69 10 30 2 16 8 31 22

2 10 30 69 16 8 31 22

2 8 30 69 16 10 31 22

2 8 10 69 16 30 31 22

2 8 10 16 69 30 31 22

2 8 10 16 22 30 31 69

 

2. 버블정렬

 

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물속에서 물위로 올라오는 물방울 모양과 같다하여 버블정렬이라고 한다. n개의 원소에 대하여 n개의 메모리를 사용한다. 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교횟수가 많아지므로 성능면에서는 좋은 방법이 아니다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬한다.

시간복잡도 : O(N²)

[69 10 30 2 16 8 31 22]

[10 30 2 16 8 31 22] 69

[10 2 16 8 30 22] 31 69

[2 10 8 16 22] 30 31 69

[2 8 10 16] 22 30 31 69

[2 8 10] 16 22 30 31 69

[2 8] 10 16 22 30 31 69

2 8 10 16 22 30 31 69

 

3. 퀵정렬

 

연속적인 분할에 의한 정렬이다. 처음 하나의 축을 정해서 이 축의 값보다 작은 값은 왼쪽에 큰 값은 오른쪽으로 위치시킨다. 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져 축값이 1이 될 때까지 정렬한다. 안정성이 없으며 가장 많이 사용되는 정렬법이다.

시간복잡도 : NlogN

[69 10 30 2 16 8 31 22]

2 [10 30 69 16 8 31 22[

2 [10 8] 16 [69 30 31 22]

2 [8] 10 16 [69 30 31 22]

2 8 10 16 [22 30 31 69]

2 8 10 16 [22] 30 [31 69]

2 8 10 16 22 30 31 69

 

4. 삽입정렬

 

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 삽입정렬이다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 반해 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 ㅋ기가 적은 데이터 집합을 정렬하는 루팅을 작성할 시 버블정렬보다 탁월한 성능 효율을 보인다.

시간복잡도 :　O(N²)

69 10 30 2 16 8 31 22

[10 69] 30 2 16 8 31 22

[10 30 69] 2 16 8 31 22

[2 10 30 69] 16 8 31 22

[2 10 16 30 69] 8 31 22

[2 8 10 16 30 69] 31 22

[2 8 10 16 30 31 69] 22

2 8 10 16 22 30 31 69

 

5.쉘정렬

 

삽입정렬의 개념을 확대하여 일반화한 정렬방법이다. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다. 수행 능력도 삽입 정렬보다 우수한 것으로 평가한다. 멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결할 수 있다.

시간복잡도 :　O(n^1.25)

69 10 30 2 16 8 31 22

16 10 30 2 69 8 31 22

16 8 30 2 69 10 31 22

16 8 30 2 69 10 31 22

16 8 30 2 69 10 31 22

16 8 30 2 69 10 31 22

16 8 30 2 31 10 69 22

16 2 30 8 31 10 69 22

2 8 10 16 22 30 31 69

6.병합정렬

 

작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식이다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이다. 안정성이 있으며 상당히 좋은 성능을 나타낸다. 큰 결점은 데이터 전체 크기만한 메모리가 더 필요하다는 점이다.

시간복잡도 :　O(nlogn)

69 10 30 2 16 8 31 22

69 10 30 2 | 16 8 31 22

2 10 30 69 | 16 8 31 22 1번

2 10 30 69 | 8 16 22 31 2번

2 8 10 16 22 30 31 69

 

 

7. 기수정렬

 

이 정렬법은 비교 연산을 하지 않으며, 무엇보다도 시간 복잡도가 O(n)이다. 물론 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하지요. 기수 정렬은 정렬 방법의 특수성 때문에 부동소수점처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 매우 특이하고 멋진 알고리즘임은 틀림없다.

시간복잡도 :　O(nlogn)

69 10 30 2 16 8 31 22

1의 자리에 대해서 버킷에 분배

[10 30 31 2 22 16 8 69]

10의 자리에 대해서 버킷에 분배

[2 8 10 16 22 30 31 69]

 

8. 힙정렬

 

이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘이다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꾼다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려간다.

시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 큰 장점이다.

시간복잡도 : O(nlogn)

나무뿌리에서 큰 순서대로 추출

 

9. 트리정렬

 

트리정렬은 이진탐색트리를 이용하여 정렬하는 방법이다. 정렬할 원소들을 이진탐색트리로 구성하고 중위 우선 순회방법을 사용하여 이진탐색트리의 원소들을 순회하여 꺼내면 오름차순 정렬이 된다.

 

시간복잡도 : O(nlogn)

Space Complexity = 필요한 메모리 stability = 정렬되기 이전의 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가?   선택정렬 : 최소값을 찾아서 제일 앞으로 삽입정렬 : 앞쪽에 데이터를 넣으면서 정렬을 시킨다. 그래서 정렬된 =>이미 정렬된 부분에 이 값이 어디에 들어갈 것인가 버블정렬 : 인접한 값을 비교 교환 쉘정렬 : 자료가 역순으로 정렬되어있어 속도가 많이 떨어지는 삽입정렬의 단점을 보완한 정렬 기법 추가 메모리 공간 소요가 없으면서도 정렬중에서도 속도가 빠르다 퀵정렬 : 의 평균성능은 NlogN 이지만 최악의 경우 N^2 로 간다. => 추가 메모리를 비교적 필요로 하는 상황이 벌어진다. 힙정렬 : 최대값이 루트에 있다 , 추가 메모리를 필요하지 않는다 , => 힙정렬 자체로 정렬 할 경우 NlogN 중에서는 비교적 조금 느린 성능을 보인다. 특성을 잘 활용하는 것이 중요하다.   병합정렬 : 순차적인 접근방식이라 순차적 접근방식에서 사용될만 한 방식=> stability 가 유지 되면서 추가 메모리가 필요 없다 Radix(기수) 들과 Distrubtion(분포수세기) 은 양의정수만을 또는 이진수를 정렬 할 수 있는 정렬 => 속도가 빠르다