정렬 알고리즘 ~_~

Etc 2007.12.06 23:22

시험공부하다가 머리아프기도 하고, 내가 제대로 이해하고 있는건가 싶기도 해서

Bubble Sort

가장 원시적인 정렬 알고리즘. ~_~

가장 간단하고 이해가 쉽지만 가장 구리다.

여기서 구리다고 하는것은 가장 처리속도가 느리다는 것.

아예 PPT 자료에 이건 이렇게 써있구만.

Don't use it.

아 네..

대충 요를 보자면, 이 정렬이 Bubble Sort 인 이유가, 자료 중 가장 작은(혹은 큰)

자료가 거품처럼 움직이기 때문.

인접한 2개의 자료를 대조해서 조건에 들어맞을 경우 두 자료를 스왑.

모든 인접한 자료들에 대해 이 짓을 수행하고 나면, 한 번 수행에 가장 작은 자료(혹은 가장 큰 자료)

가 데이터의 제일 앞으로 가 있게 된다.

그 다음에는 제일 앞으로 이미 가 있는 제일 작은 자료를 제외하고 나머지 자료에 대해 이짓을 반복.

맨 마지막 자료 2개에 대해 이 작업을 수행할 때까지 이짓을 무한반복.

결국 정렬이 된다는 알고리즘.

EX)

 5 4 9 6 7 8 2    원래 데이터

 5 4 9 6 7 8 2   비교

 4 5 9 6 7 8 2   교환

 4 5 9 6 7 8 2   비교

 4 5 9 6 7 8 2   비교

 4 5 6 9 7 8 2   교환

 4 5 6 9 7 8 2   비교

 4 5 6 7 9 8 2   교환

 4 5 6 7 9 8 2   비교

 4 5 6 7 8 9 2   교환

 4 5 6 7 8 9 2   비교

 4 5 6 7 8 2 9   교환

이게 작업을 1번 수행한것. 제일 큰 자료인 9가 제일 뒤로 밀렸으니, 이제 9 빼고 나머지 6개의

자료를 다시 2개씩 비교하는 짓을 반복해 그 다음 큰 숫자를 9 앞으로 밀고, 이런짓을 정렬 완료시까지

반복.


어딘가에서 긁어온거라 이 예제에서는 가장 큰 수를 뒤로 밀어버리는 방식으로 정렬을 했지만

결국 가장 작은걸 앞으로 끌어오나 가장 큰걸 뒤로 미나 똑같은거니까 -_-; 옌장

한마디로 존나 쓰레기 -_-;;

Complexity 는 당연하게도 O(n^2)


Insert Sort

삽입 정렬.

삽입 정렬은 말 그대로 삽입해서 정렬한다고 해서 삽입 정렬이다.

뭘 삽입하냐 하면 자료를 삽입하는 거지.

간단한 예제.

2 7 1 8 3 5    원래 자료

제일 앞의 자료인 2는 제끼고, 7을 기준으로 7 앞의 자료와 7을 비교.

7 앞의 자료는 2뿐. 순서는 그대로

2 7 1 8 3 5

다음엔 1을 기준으로 해서, 1 앞의 자료와 1을 비교.

2,7 모두 1보다 크다. 따라서 1을 2 앞에 삽입

1 2 7 8 3 5

8은 더 작은 자료가 앞에 없으므로 무시.

3은 1 2 7 8 중 7,8 보다 작으므로 7 앞에 삽입.

1 2 3 7 8 5

5는 7,8보다 작으므로 7,8 앞에 삽입

1 2 3 5 7 8

ㅅㄱ.

이런식으로 하는 정렬.

Complexity - Assignments 0.25n^2 + O(n)
Complexity - Comparisons 0.25n^2 + O(n)

Bubble sort 보다 한단계 발전한 형태. 역시 느리긴 매한가지.


Selection sort

선택 정렬.

자료를 선택해서 교환하는 방식이라 선택 정렬이라고 부름.

모든 자료중, 최소값을 찾아 배열 제일 앞의 자료와 교환.

그리고 최소값의 자료를 제외한 남은 자료 중 역시 제일 작은 값을 찾아 배열의 2번째 자료와 교환.

뭐 말하자면 제일 작은거 찾아서 젤 앞에 쑤셔넣고, 그다음 작은거 찾아서 2번째 자리에 쑤셔넣고

뭐 이런방식으로 하는 정렬.

뭐 역시 원시적이긴 매한가지 ~_~

Complexity - Assignments : 3n + O(1)
Complexity - Comparisons : 0.5n^2 + O(n)


Shell Sort

쉘 정렬인 이유는 쉘이라는 사람이 처음 고안한 알고리즘이라서 ~_~

먼저, 기준값과 비교할 값의 거리를 정하고,

그 거리에 따라 전체 자료를 몇 개의 집단으로 나눈 후, 각각의 집단에 대해 Insertion Sort를 수행.

거리를 반으로 줄여서 다시 집단을 거리에 따라 나눈 후, 다시 각각의 집단에 대해 Insertion sort.

마지막으로 거리를 1로 하여 Insertion Sort를 수행하면 결국 정렬이 완료된다는 방식.

Insertion Sort에 비해 무슨 차이인가 싶겠지만, 이것은 전체를 부분부분 나누어서, 각 집단에 대해서

정렬을 수행하므로, Insertion Sort의 최대 약점인, 자료를 미는 작업이 최소화된다. ~_~

뭐 대강 이해 안가는 자들을 위한 예제.


81 94 11 96 12 35 17 95 28 58 41 75 15

처음에 거리를 5로 설정하면

(81, 35, 41) (94, 17, 75) (11, 95, 15) ..... 을 Grouping.

이런식으로 5칸씩 떨어진 원소끼리 그룹을 지은 후 각 집단에서 Insertion sort.

그 후 거리를 3으로 줄여 다시 그룹을 지은 후 다시 Insertion sort.

다시 거리를 1로 줄여 다시 Insertion Sort (이 경우 통상의 Insertion Sort와 같다)

이 알고리즘은 기반을 Insertion Sort에 두고 있기 때문에 최악의 경우 Insertion Sort와 같은

성능을 보여준다. (최악의 경우 자료에 따라 Grouping을 했을 때 정렬이 전혀 안 되고,

거리를 1로 그룹을 지었을 때만 정렬이 가능해지는 식으로 데이터가 배열이 되어있다면

이는 Insertion Sort와 완벽히 성능이 같아짐)

다만 이런 최악의 경우를 배제하면, Grouping을 통해 Insertion Sort의 단점인 자료를 뒤로

미는 시간이 존내 오래 걸린다는 단점을 해소할 수 있다.

이를테면 2 3 4 5 6 7 8 9 1 이라는 자료에서 1을 제일 앞으로 보내야 되는데 이럴려면

2 3 4 5 6 7 8 9 를 전부 한칸씩 뒤로 밀어야 됨. 근데 이거 상당히 시간이 오래걸리는 짓이라서 ~_~

Complexity - Average : O(n^7/6)(?)


Heap Sort

Heap Tree를 구성하면, 최상단의 자료가 항상 전체 자료에서 최대의 크기를 가진다는 점에 착안한

정렬. Insert-Phase와  Delete-Phase 로 나뉨.

Insert-Phase에서는 배열의 자료를 하나하나 Heap에 추가시켜 Heap를 구성한다.

Delete-Phase에서는 Heap Tree의 root를  heap array의 제일 마지막 원소와 교환한 후, 교환된

root는 heap tree에서 제외. 나머지 자료들을 재정렬하여 new heap을 구성한 후, 다시 root를

최후방으로 옮기고 new heap 구성. 이런식으로 자료가 정렬될때까지 반복.

이 알고리즘을 제대로 이해하려면 heap이 뭔지부터 알아야 하지만 설명하기 귀찮으므로 패스.

Complexity - O(N logN)


Merge Sort

Divide-and-Conquer 방식의 정렬 알고리즘.

(1) 자료를 같은 크기의 2집단으로 나눔.
(2) 각 집단을 정렬
(3) 합친다.

이 작업을 재귀적으로 수행시키면 merge sort 가 된다.

예제

13 25 24 1 38 2 14 27

Divide

13 25 24 1 / 38 2 14 27

Divide

13 25 / 24 1 / 38 2 / 14 27

Sort

13 25 / 1 24 / 2 38 / 14 27

2개씩 묶어서 합침

13, 1 비교 1이 작으므로 1을 버퍼에 삽입

1

13, 24 비교, 13이 작으므로 13을 버퍼에 삽입

1 13

25, 24비교 24가 작으므로 24를 버퍼에 삽입

1 13 24 25

뒤의 2개도 같은방식으로 합친다

1 13 24 25 / 2 14 27 38

2개를 위와 같은 방식으로 합침

1 2 13 14 24 25 27 38

Complexity - O(N logN)


Quick Sort

merge sort의 발전된 형태.(발전이랄까.. 뭐 사실 complexity의 차이는 없다.)

Complexity의 혁신적인 발전이 있었던 것은 Shell Sort지.. 처음으로 n^2의 벽을 깼는데 ㅡㅡ;

역시 Divide-and-Conquer 방식의 알고리즘

(1) pivot을 설정한다.
(2) pivot을 기준으로 자료를 두 집단으로 나눈다.
(3) 한 집단에는 pivot보다 작은 수만 쓸어넣고 다른 집단에는 큰 수만 쓸어넣는다.
(4) 각 집단에서 다시 pivot을 설정
(5) 각 집단을 재분할해 다시 pivot을 기준으로 크고 작은 집단으로 나눈다.
(6) 이짓을 무한반복
(7) 최종적으로 각 그룹이 1개의 원소만을 가지고 있을때까지 반복한 후, 각 그룹과 pivot을 합침
(8) 정렬완료

아 귀찮다 예제안써 훡.

Radix Sort

(1) 각 자료를 1의 자리수를 기준으로 Hash Table에 정렬.
(2) 완료되고 나면 그 앞의 자리수를 기준으로 다시 Hash Table 에 정렬.
(3) 모든 자리수를 훑을때까지 무한반복
(4) 정렬완료

걍 간단히 말하면 1의 자리수 존나 비교해서 정렬

10의 자리수 존나 비교해서 정렬.

100의 자리수 존나 비교해서 정렬..

이짓을 끝까지 반복.

역시 예제안써 훡. 귀찮다.

Complexity 비교에서는 언급하지 않는다.

자료의 개수뿐만이 아니라 자료의 질에 따라서도 정렬시간이 존나 많이 변하는 방식이라서

이래저래 아웃사이더 취급당하고 별로 쓰이지도 않는 방식..

(그렇지 않냐? 전체 자료의 개수가 똑같아도 자료가 최대 10^6 자리수인것과 10^8의 자리수인

것과 정렬 시간이 틀린 좀 어이없는 알고리즘이라 -_-)


대강의 속도비교

N                   Insertion          Shell           Heap           Quick
10                  0.00044            0.00041        0.00057        0.00046
100                0.00675            0.00171        0.00420        0.00284
1000               0.59564            0.02827        0.05565        0.03153
10000             58.864              0.42998        0.71650        0.36765
100000            NA                  5.7298          8.8591         4.2298
1000000           NA                 71.164          104.68         47.065

N은 정렬할 자료의 개수
숫자 단위는 전부 초.

Inserstion Sort에서 십만과 백만단위에서 NA가 뜬건 뭐 너무 오래걸려서 언급할 가치도 없다는 뜻일듯.

흠 근데 같은 O(N logN)의 컴플렉시티라도 계수가 차이나서 속도차이는 좀 나는근영 ㄲㄲ

신고
Posted by 나일레