sorting

각종 정렬방법에 대한 정리.

자격증 시험 공부 중...

출처는 위키피디아.

http://en.wikipedia.org/wiki/Shell_sort

http://en.wikipedia.org/wiki/Insertion_sort

1. shell sort

긴 배열을 토막내서 부분부분 정렬한다.

처음에는 토막을 크개 내서 정렬하다가 점점 토막을 작게 내서 정렬하고,

마지막에는 삽입 정렬을 한다.

예를 들어..

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

라는 수가 있으면...

토막을 내서 다음과 같이 만든다.

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

이것을 다음과 같이 정렬을 한다.

(세로줄 끼리 정렬 되었다. )

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

이것을 다시 풀어 쓰면

 [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

이 되고, 이것을 토막의 크기를 줄이며 위의 과정을 반복한다.

위에서 5개 단위 토막이었으면 예를 들어 다음과 같이 3개 단위 토막으로 구성한 뒤 다시 정렬 하면 된다.

10 14 73
25 23 13
27 94 33 
39 25 59 
94 65 82
45

(이후 세로로 정렬, 정렬 다 되고 나면 2개단위 토막 만들어 정렬하고, 나머지는 삽입 정렬 하면 된다. )

장점은 이동하는 거리가 크지 않다는 것.

특징은 내부 정렬이라는 것.

2. insertion sort

이른바 삽입정렬.

순서대로 점검하면서 뒤에 오는 수가 현재의 수의 max 보다 작으면 순서에 맞춰서 삽입하여 정렬 해준다.

그림으로 더 쉽게 표현이 될 것 같다.

실행은 다음과 같이 될꺼다.

5 7 0 3 4 2 6 1 (0)

5 7 0 3 4 2 6 1 (0)

0 5 7 3 4 2 6 1 (2)    // 5, 7 다음  0 이 와서 0 을 가장 앞으로 삽입

0 3 5 7 4 2 6 1 (2)    // 7 다음 3 이 와서 3 을 앞으로 삽입

0 3 4 5 7 2 6 1 (2)    // 7 다음 4가 와서 앞으로 삽입

0 2 3 4 5 7 6 1 (4)    // 7 다음 2 와서 앞으로 삽입

0 2 3 4 5 6 7 1 (1)    // 7 다음 6. 삽입

0 1 2 3 4 5 6 7 (6)    // 7 다음 1. 삽입

이런 식으로 현재 정렬된 범위의 가장 큰 수와 다음에 오는 수를 비교하여

앞에 삽입 하는 방법으로 정렬이 이루어진다.

3. Quick sort

divide and conquer 가 핵심이다.

전체에서 축을 잡은 다음 그것을 토대로 비교를 하며 swap 한다. (3개를)

진행하며 정렬이 되어서 축을 기준으로 큰것 / 작은것이 완전 구분이 되면

그 축을 기준으로 부분으로 나누고, 다시 이전 과정을 반복한다.

(축을 잡고 비교하며 스왑)

그림으로 보는 것이 가장 깔끔할 것 같다.

과정을 예를 들면 다음과 같이 들 수 있다.

4. bubble sort

바로 옆의 것을 비교하며 정렬한다.

축이나 뭐 특별한 것 없다.

순서대로 한번 지나가며 바로 옆의 것이랑 비교 정렬 해주고,

다시 정렬 해주고.. 반복 하는 식.

그림으로 보면 다음과 같다.

예를 들어 위에서 사용된 배열을 이용해서 bubble sort 해보자.

(단계별 설명 생략. 뭐가 바꼈는지 따라 와보기 바란다. )

13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
13 14 33 94 82 25 59 94 65 23 45 27 73 25 39 10
13 14 33 82 94 25 59 94 65 23 45 27 73 25 39 10

13 14 33 82 25 94 59 94 65 23 45 27 73 25 39 10

13 14 33 82 25 59 94 94 65 23 45 27 73 25 39 10

13 14 33 82 25 59 94 65 94 23 45 27 73 25 39 10

13 14 33 82 25 59 94 65 23 94 45 27 73 25 39 10

13 14 33 82 25 59 94 65 23 45 94 27 73 25 39 10

13 14 33 82 25 59 94 65 23 45 27 94 73 25 39 10

13 14 33 82 25 59 94 65 23 45 27 73 94 25 39 10

13 14 33 82 25 59 94 65 23 45 27 73 25 94 39 10

13 14 33 82 25 59 94 65 23 45 27 73 25 39 94 10

13 14 33 82 25 59 94 65 23 45 27 73 25 39 10 94

바로 인접한 것만 고친다. 그래서 효율이 낮다.

다른 정렬은 다음에 더 필요하면 올리도록 하겠다...

마지막으로 위키피디아에서 분류된 정렬의 종류 표..

일일이 다 "새 창에서 뜸" 으로 바꿔주기 귀찮으니..;;;

아래 주소 가서 맨 아래 가서 보기 바란다..;;

http://en.wikipedia.org/wiki/Sorting_algorithm

v • d • e Sorting algorithms
Theory	Computational complexity theory | Big O notation | Total order | Lists | Stability | Comparison sort
Exchange sorts	Bubble sort | Cocktail sort | Odd-even sort | Comb sort | Gnome sort | Quicksort
Selection sorts	Selection sort | Heapsort | Smoothsort | Cartesian tree sort | Tournament sort
Insertion sorts	Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting
Merge sorts	Merge sort | Polyphase merge sort | Strand sort | Timsort
Non-comparison sorts	Radix sort | Bucket sort | Counting sort | Pigeonhole sort | Burstsort | Bead sort
Others	Topological sorting | Sorting network | Bitonic sorter | Batcher odd-even mergesort | Pancake sorting
Ineffective/humorous sorts	Bogosort | Stooge sort