배열을 쓰다보면 정렬을 빼놓을수없다.
애초에 배열이 오름차순 내림차순 정렬이 되어있어야 쓰기 편할뿐 아니라
탐색이나 다른 알고리즘을 최적화하는데 아주 중요하다.
거품 선택 삽입 힙 퀵 만 보도록 한다.
거품(bubble) 정렬.
뽀글뽀글이다. 1번2번 비교해서 정렬하고, 2번 3번비교해서 정렬하고.. ...쭈욱가다보면 마지막 원소만 원하는값으로 정렬이 되었을것이다. 만약 이 마지막 인덱스를 n이라고 치면
n-1번만에 된것. 그다음은 n-2번만에 될것이고 ...쭉가다보면 한번만에 정렬이 끝날것이다.
그렇게되면 정렬은 n(n-1) / 2 번만에 이루어질것이다.
이 정렬은 거의 모든상황에서 최악의 성능을 보여준다. 물론 이미 정렬된자료에서는 1번만 돌면되기때문에 최고의 성능을 보여주지만, 이미정렬된자료를 정렬한다고? 여기까지.
1 2 3 4 5 6 7 8 9 10 11 | void Bubble_Sort(int len) { for(int i=0; i<len; i++) for (int j = 0; j < len - i - 1; j++) if (a[j] > a[j+1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } | cs |
선택(selection) 정렬
하나하나 꼽아넣는 형태이다.
처음부터 끝까지 다 훑어서 제일작은걸 첫번쨰. 두번째부터 쭉 훑어서 제일작은걸 그다음. 이렇게 놓는방식인데
어떻게보면 버블이랑 비슷해 보일수도있다.
버블정렬보다 swap을 많이 안한다는게 장점이며, 평균적인 시간도 빠르다.
하지만 중복된 값들을 여러번 swap할 가능성이있어서 불안정하다고 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void SelectionSort(int arr[], int len) { int i, j; int min, temp; for(i=0; i<len-1; i++) { min = i; for(j=i+1; j<len; j++) { if(arr[j] < arr[min]) min = j; } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } | cs |
이렇게 돌아가는구나..정도만 알면 될것같다.
애초에 정렬자체가 요즘엔 버블 선택이런것보다 인클루드해서 쉽게 정렬하는방법이 많으니..
삽입(insertion) 정렬
하나뽑아서 적절한위치에 넣고 나머지 자리를 당기는 방식이다.
6 8 5 7 4 9 3 2 1 이런식으로 되어있을때
6을 먼저뽑아서 그자리에 놓는다. 이미 정렬된게 없기때문.
다음 8 을뽑아서 8의 적절한자리인 6다음에 놓도록 한다. 그럼 6 8 그대로 된다.
그다음 5를 뽑아서 적절한위치를 찾기위해 8을 당기고 6을 당겨서 제일 앞자리로 위치할수있게한다. 그러면 5 6 8 7 4.... 이 된다. 이런식으로 진행한다.
평균적으로는 빠른편이긴한데(거품 선택 삽입 중에서) 위 예시처럼 작은수가 뒤에 몰려있으면 당겨야하는 수도 그만큼많아지기때문에 지옥..
힙(heap) 정렬
시간복잡도 O(N*logN)
힙 정렬은 힙을사용한건데
자료구조에서 힙이란 완전이진트리의 일종으로 우선순위큐를 위한것이다.
최대값 최소값을 쉽게 얻어낼수있는데
제일 root에 가장큰값이 있다면 최대힙, 가장작으면 최소힙이라고 한다.
최대힙기준
모든 원소를 힙에 삽입하고
루트에있는값은 최대값이므로 출력한후에 루트에서 제거한다.
삭제된 루트노드에는 그 힙의 마지막 노드를 넣는다. 그러고선 다시 힙을 완성시키고 루트값을 출력하고 제거하는 반복적인 일만 남았다.
코드로 짤경우 2세트 정도가 필요하다.
힙삽입, 루트제거
다음 문제로 알아보도록한다.
퀵(quick) 정렬
퀵정렬은 평균적인 상황에서 최고의 성능을 자랑한다.
피벗을정해서 양쪽을 기준으로 또 피벗정하고의 반복인데. 피벗이 계속 제일작은값이거나 제일큰값이면 시간복잡도 O(n^2)의 성능을 가지게되서 엄청구리다.
이를 보완하기위한 방법으로는 random quicksort나 전체수에서 임의의 3개나 9개값을 뽑아서 그들의 중간값으로 피벗을 정하는것.
최악의 경우를 막기위해서 생긴 방법이라고는 하나, 저렇게 해도 빠르다.
3 2 1 6 5 4 9 8 7
1.피벗을하나뽑는다. -> 제일왼쪽 3으로 하겠다.
2.피벗을제외한 2 1 6 5 4 9 8 7 을 봤을때 제일 왼쪽값을 left, 오른쪽값을 right로 하겠다. 지금은 left =2, right =7
3.순서는 반복적이다. 피벗과 left비교 -> 피벗과 right비교-> 자리바꿀지여부
4.피벗과 left를 비교하여 left가 더 크다면 right와 피벗을비교 or 피벗과 left를 비교하여 left가 더 작다면 left를 한칸 우측으로 이동시킨다.
5. 지금은 피벗인 3이 left인 2보다 더 크므로, left를 한칸 우측으로 이동시켜 1로 한다.
6. 현재 left = 1 , right = 7, 피벗 = 3
7. left가 피벗보다 작으므로 그대로 두고 right를 비교해본다.
8. right(7)보다 피벗(3)이 더작으므로, right를 한칸 좌측으로 이동시킨다. 그렇다면 right=8이 된다.
말은 복잡하지만( 필자가 잘 쓰질 못함..)
해보면 엄청 간단하다.
이렇게하게되면 피벗 (3)으로 기준이 정해지고, 그러면 그 피벗을 기준으로 큰값들 작은값들로 나뉘게된다.
그러면 또 그 작은값들, 큰값들에서 각각 피벗을 정하고 똑같이 정렬을하면 퀵정렬이 완료된다.
코딩할때는 이부분을 재귀로해서 간단하게 구현할 수 있다.
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 | #define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; void swap(int arr[], int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } int cut(int arr[] , int cutstart, int cutend) { int pivot = arr[cutstart]; int left = cutstart + 1; int right = cutend; while (left <= right) { while (pivot >= arr[left] && left <= cutend){ left++; // left를 우측으로 } while (pivot <= arr[right] && right >= cutstart +1){ right--; // right를 좌측으로 } if (left <= right){ swap(arr, left, right); //left,right스왑 } } swap(arr, cutstart, right); // 피벗과 high가 가리키는 대상을 교환 return right; } void quicksort(int arr[], int start, int end) { if (start <= end) { int pivot = cut(arr, start, end); quicksort(arr, start, pivot - 1); quicksort(arr, pivot + 1, end); } } int main() { int arr[9] = { 3,2,1,6,5,4,9,8,7 }; cout << "3 2 1 6 5 4 9 8 7 을 정렬 합니다." << endl;; quicksort(arr, 0, 8); for (int i = 0; i < 9; i++) { cout << arr[i] << " "; } cout << " << 정렬 결과 " << endl; } | cs |
이런식으로 구현했다. cut 이 자르기위해 피버를정해서 정렬하는 과정이고 quicksort에서는 이걸 재귀로하여 정렬하였다.
'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글
| KMP 알고리즘 (0) | 2019.02.15 |
|---|---|
| 3장. 문자열 (0) | 2019.02.13 |
| 백준 2846번 오르막길 (0) | 2019.02.09 |
| 백준 2920번 음계 (0) | 2019.02.07 |
| 1장. 배열 (0) | 2019.02.07 |