버블소트만큼 구현하기 쉽고 이해하기 쉬운 정렬들이다.
하지만 이것도 버블소트와 마찬가지로 worst case에는 
별로 효율적인 정렬과는 거리가 멀다.
정렬하는 방식은 어떻게 짜느냐에 따라 방법이 다르고, 효율이 다르다.
Insertion Sort와 Selection Sort는 삽입할때 정렬을 시켜서 삽입하느냐 아니냐에 따라
방식이 달라진다. 삽입할 때 정렬을 시키는 방법은 아래와 같다.
Selection Sort : 우선 어떤 배열(a)에서 앞에서부터 나아가며
가장 작은 minimum값을 찾아 별도의 배열(b)의 제일 앞에 이동을 시킨다.
그리고 a배열의 남은 값들중에서 다시 minimum값을 찾아
b배열의 가장 뒤에 저장한다.
이 과정을 n번 반복하면 a배열은 다 없어지고 b배열에 정렬된 형태로 남게된다.
Insertion Sort : 키값을 앞에서부터 정해놓고
키값이 바로 앞의 값보다 작을경우 두 수를 바꿔주면서 제일 앞에 있는 수까지 비교와 교환을 계속해주다가
키값의 앞의 값이 키값보다 작을경우 즉, 정렬이 완료된 부분을 만날경우
교환을 그만하고 다시 키값을 증가시켜서 과정을 반복한다.
두 과정다 worst case의 경우
Selection Sort는 무조건 끝까지 다 훑게되지만
Insertion Sort는 중간에 정렬된 부분을 빨리 만난다면 끝까지 갈 필요가 없기때문에
평균적으로는 Insertion Sort가 더 빨리 끝나게된다.
< 출처 : 유투브(YouTube) - Selection Sort >
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 | #include <iostream> #define MAXSIZE 5 using namespace std; int main() { int arr[] = { 2,4,3,5,1 }; int min, num; cout << "정렬 전 : "; for (int i = 0;i < MAXSIZE;i++) { cout << arr[i] << " "; }cout << endl; for (int i = 0;i < MAXSIZE;i++) { min = arr[i]; for (int j = i;j < MAXSIZE;j++) { if (min > arr[j]) { min = arr[j]; num = j; } } swap(arr[i], arr[num]); } cout << "정렬 후 : "; for (int i = 0;i < MAXSIZE;i++) { cout << arr[i] << " "; }cout << endl; return 0; } | cs |
(c++)
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 | package JaRyoGuJo; public class InsertionSort { public static void main(String[] args) { // TODO Auto-generated method stub int arr[] = {2,4,3,5,1}; final int MAXSIZE = 5; int tmp; System.out.print("정렬 전 : "); for(int i =0;i<MAXSIZE;i++){ System.out.print(arr[i]); }System.out.println(""); for (int i = 0;i < MAXSIZE;i++) { for (int j = i;j > 0;j--) { if (arr[j-1] > arr[j]) { tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp; } else break; } } System.out.print("정렬 후 : "); for(int i =0;i<MAXSIZE;i++){ System.out.print(arr[i]); }System.out.println(""); } } | cs |
(Java)
< 출처 : 유투브(YouTube) - Insertion Sort >
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> #define MAXSIZE 5 using namespace std; int main() { int arr[] = { 2,4,3,5,1 }; int min; cout << "정렬 전 : "; for (int i = 0;i < MAXSIZE;i++) { cout << arr[i] << " "; }cout << endl; for (int i = 0;i < MAXSIZE;i++) { for (int j = i;j > 0;j--) { if (arr[j-1] > arr[j]) { swap(arr[j - 1], arr[j]); } else break; } } cout << "정렬 후 : "; for (int i = 0;i < MAXSIZE;i++) { cout << arr[i] << " "; }cout << endl; return 0; } |
(c++)
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 | package JaRyoGuJo; public class SelectionSort { public static void main(String[] args) { // TODO Auto-generated method stub int arr[] = { 2, 4, 3, 5, 1 }; final int MAXSIZE = 5; int min, num = 0, tmp; System.out.print("정렬 전 : "); for (int i = 0; i < MAXSIZE; i++) { System.out.print(arr[i]); } System.out.println(""); for (int i = 0; i < MAXSIZE; i++) { min = arr[i]; for (int j = i; j < MAXSIZE; j++) { if (min > arr[j]) { min = arr[j]; num = j; } } if (num != 0) { tmp = arr[i]; arr[i] = arr[num]; arr[num] = tmp; } num = 0; } System.out.print("정렬 후 : "); for (int i = 0; i < MAXSIZE; i++) { System.out.print(arr[i]); } System.out.println(""); } } | cs |
(Java)
'학교 > 자료구조' 카테고리의 다른 글
| [정렬] 버블소트 (0) | 2016.03.30 |
|---|---|
| [정렬] sorting의 종류와 효율 (0) | 2016.03.28 |
| STL container -ing (0) | 2016.03.19 |
| 기초 Algorithm(2) (0) | 2015.11.03 |
| 기초 Algorithm(1) (0) | 2015.10.29 |
뭐해볼까
< O(n) < 