병합 정렬(Merge sort)
▷ 합병정렬(Merge sort)
전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다.
▷ 정렬방법.
1. 데이터 집합을 반으로 나눈다.
2. 데이터 집합의 크기가 2이상일 경우 하나의 원소가 될때까지 1번을 반복한다.
3. 같은 집합에서 나뉘어진 원소끼리 정렬하면서 집합으로 만든다.
4. 모든 원소가 하나의 집합이 될때까지 3번을 반복한다.
임의의 값을 정렬해보자.
정렬의 순서는 오름차순이다.
※ 분할 - 파란색 블록은 기준점이다.
※ 정복
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> using namespace std; #define MAX 5 void MergeSort(int *Number, int Low, int Mid, int High); void Division(int *Number, int Low, int High); void main() { int Number[MAX] = {5,1,6,4,8,3,7,9,2}; Division( Number, 0, MAX - 1); for(int i = 0; i < MAX; i++) printf("%d \n", Number[i] ); } // 분할 void Division(int *Number, int Low, int High) { int Mid; if(Low < High) { Mid = (Low + High) / 2; Division( Number, Low, Mid ); Division( Number, Mid + 1, High); MergeSort( Number, Low, Mid, High); } } // 정복 void MergeSort( int *Number, int Low, int Mid, int High) { // 집합의 크기만큼 동적할당. int *TempIndex = new int[ High + 1 ]; int Left = Low; // 왼쪽 집합의 시작 값. int Right = Mid + 1; // 오른쪽 집합의 시작 값. int CountIndex = Low; // // 왼쪽 집합과 오른쪽 집합의 원소 값을 비교하여 // 더 작은 값을 새로 동적할당하여 만든 집합에 대입한다. while(Left <= Mid && Right <= High) { if(Number[Left] < Number[Right]) TempIndex[CountIndex++] = Number[Left++]; else TempIndex[CountIndex++] = Number[Right++]; } // 왼쪽 혹은 오른쪽 집합이 새로만든 집합에 모두 들어갔을 경우 // 남은 집합을 새로운 집합에 모두 집어넣는다. if( Left > Mid ) { for(int i = Right; i <= High; i++) TempIndex[CountIndex++] = Number[i]; } else { for(int i = Left; i <= Mid; i++) TempIndex[CountIndex++] = Number[i]; } // 새로만든 집합공간에 있는 모든 원소값을 원래 존재했던 집합 공간에 대입한다. for(int i = Low; i <= High; i++) Number[i] = TempIndex[i]; // 새로 만들었던 집합공간의 메모리 해제. delete[] TempIndex; } | cs |
결과
'자료구조' 카테고리의 다른 글
| 연결 리스트(Linked List) (0) | 2017.01.06 |
|---|---|
| 퀵 정렬 (Quick sort) (0) | 2017.01.04 |
| 쉘 정렬 (Shell sort) (0) | 2017.01.02 |
| 삽입정렬 (Insertion sort) (0) | 2017.01.01 |
| 빅오 (0) | 2017.01.01 |
쉘 정렬 (Shell sort)
▷ 쉘 정렬 (Shell sort)
쉘 정렬은 삽입 정렬이 어느 정도 정렬된 리스트에 대해서는 대단히 빠른것에 착안한 방법이다.
쉘 정렬은 삽입 정렬과는 다르게 전체의 값을 한 번에 정렬하지 않는다.
쉘 정렬은 일정한 기준에 따라 값을 분류한 후 부분 리스트들을 만들고 그 부분 리스트들에 대해서 삽입정렬을 실행한다.
그리고 각 정렬될 리스트들을 모아서 하나로 만든 후 삽입정렬을 실행한다.
삽입 정렬은 이미 정리되어 있는 데이터에 대해서는 연산을 하지 않기 때문에 부분을 미리 정렬하고 전체를 정렬할 경우
연산이 줄어들기 때문에 순수한 삽입 정렬보다는 효율이 좋다.
임의의 값을 정렬해보자.
정렬의 순서는 오름차순이다.
시작 : 7 2 4 1 8 3 5 9 6 10
1. 간격을 5로 잡고 각 간격에 있는 숫자들을 각각 모아 삽입정렬로 정렬한다.
※ 간격은 자신의 마음대로 정해도 된다.
한 번 정렬된 결과.
2. 정렬이 끝났으면 간격을 2로 나눈다.
※ 5를 나눴을 때 2.5 하지만 소수점 자리는 버린다.
3. 간격이 2로 바뀌었으므로 2간격으로 떨어진 숫자들을 모아 삽입정렬한다.
두 번째 정렬된 결과.
4. 정렬이 끝났으면 간격을 2로 나눈다.
5. 간격이 1로 바뀌었으므로 전체에 대한 삽입정렬을 실행한다.
6. 간격이 1보다 작아지면 반복을 중지한다.
7. 정렬 완료.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> using namespace std; #define MAX 5 void ShellSort( int *Number ); void main() { int Number[MAX] = {7, 3, 9, 4, 1}; ShellSort( Number ); for(int i = 0; i < MAX; i++) printf("%d \n", Number[i] ); } void ShellSort( int *Number ) { int Gap = 5; int Value, i, j; while( Gap > 0 ) { for(i = Gap; i < MAX; i++) { Value = Number[i]; for(j = i - Gap; j >= 0; j -= Gap) { if(Value < Number[j]) Number[j + Gap] = Number[j]; else break; } Number[j + Gap] = Value; } Gap /= 2; } } | cs |
결과.
'자료구조' 카테고리의 다른 글
| 퀵 정렬 (Quick sort) (0) | 2017.01.04 |
|---|---|
| 병합 정렬(Merge sort) (0) | 2017.01.02 |
| 삽입정렬 (Insertion sort) (0) | 2017.01.01 |
| 빅오 (0) | 2017.01.01 |
| 선택정렬 (Selection sort) (0) | 2017.01.01 |
삽입정렬 (Insertion sort)
삽입정렬 (Insertion sort)
리스트를 가상으로 왼쪽과 오른쪽 리스트로 구분하자.
왼쪽은 정렬이 되어있고, 오른쪽은 정렬해야될 값이 들어있다.
오른쪽 리스트에 첫 번째 값이 왼쪽 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후 제 위치에 삽입한다.
이 경우, 삽입될 위치로부터 오른쪽에 있는 값들을 한 칸씩 오른쪽으로 이동시킨다.
임의의 값을 정렬해보자.
정렬의 순서는 오름차순이다.
※ 유의사항
- 삽입정렬은 영역을 정하고 그 영역 안에서의 순서를 정해 이동하는 방식이다.
- value : 현재 기준이 되는 값. 또는 값의 임시 저장소라고 생각하면 된다.
시작 : 7 3 9 4 1
1).
value : 3
↓
인덱스 : 0 1 2 3 4
값 : [7 3] 9 4 1
3을 기준으로 7을 비교한다.
if( 3 < 7 ) ? 참.
현재 검사하고 있는 범위( [ ] ) 안에서 각 숫자들을 한 칸씩 당겨주어야 하므로.
1번째 인덱스에 0번째 인덱스 값을 넣는다.
↓
- [ 7 7 ] 9 4 1
다음은 비교할 값이 없으므로 현재 인덱스에 value가 가진 값을 대입한다.
↓
- [ 3 7 ] 9 4 1
2).
value : 9
↓
인덱스 : 0 1 2 3 4
인덱스: [ 3 7 9 ] 4 1
if( 9 < 7 ) ? 거짓.
if문의 조건이 충족되지 않으므로 다음으로 넘어간다.
3).
value : 4
↓
인덱스 : 0 1 2 3 4
값 : [ 3 7 9 4 ] 1
if( 4 < 9 ) ? 참
1. 숫자들을 뒤로 한 칸씩 당긴다.
2. value의 값과 당길 숫자들과 비교한다.
3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.
↓
- [ 3 7 9 4 ] 1 - if( 4 < 9 ) ? 참
=>[ 3 7 9 9 ] 1
↓
- [ 3 7 9 9 ] 1 - if( 4 < 7 ) ? 참
=>[ 3 7 7 9 ] 1
↓
- [ 3 7 9 9 ] 1 - if( 4 < 3 ) ? 거짓
=>[ 3 4 7 9 ] 1
4).
value : 1
↓
인덱스 : 0 1 2 3 4
값 : [ 7 3 4 9 1 ]
if( 1 < 9 ) ? 참
1. 숫자들을 뒤로 한 칸씩 당긴다.
2. value의 값과 당길 숫자들과 비교한다.
3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.
↓
- [ 3 4 7 9 1 ] - if( 1 < 9 ) ? 참
=> [ 3 4 7 9 9 ]
↓
- [ 3 4 7 9 9 ] - if( 1 < 7 ) ? 참
=> [ 3 4 7 7 9 ]
↓
- [ 3 4 7 9 9 ] - if( 1 < 4 ) ? 참
=> [ 3 4 4 7 9 ]
↓
- [ 3 4 7 9 9 ] - if( 1 < 3 ) ? 참
=> [ 3 3 4 7 9 ]
더이상 검사할 인덱스가 없으므로 현재 인덱스에 vaule를 대입.
=> [ 1 3 4 7 9 ]
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream> using namespace std; #define MAX 5 void InsertSort(int *Number ); void main() { int Number[MAX] = {7, 3, 9, 4, 1}; InsertSort( Number ); for(int i = 0; i < MAX; i++) printf("%d \n", Number[i] ); } void InsertSort( int *Number ) { int Value,i,j; for(i = 1; i < MAX; i++) { Value = Number[i]; for(j = i - 1; j >= 0; j--) { if(Value < Number[j]) Number[j + 1] = Number[j]; else break; } Number[j + 1] = Value; } } | cs |
결과
'자료구조' 카테고리의 다른 글
| 병합 정렬(Merge sort) (0) | 2017.01.02 |
|---|---|
| 쉘 정렬 (Shell sort) (0) | 2017.01.02 |
| 빅오 (0) | 2017.01.01 |
| 선택정렬 (Selection sort) (0) | 2017.01.01 |
| 변형된 버블정렬 (Bubble Sort) (0) | 2017.01.01 |
