각종 정렬방법에 대한 정리.
자격증 시험 공부 중...
출처는 위키피디아.
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 1013 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
바로 인접한 것만 고친다. 그래서 효율이 낮다.
invalid-file
