|정렬 알고리즘|버블, 선택, 삽입, 퀵, 병합, 힙 정렬 연습

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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <queue> #include <stack> #include <set> #include <map> #include <vector> #include <string> #include <stdlib.h> #include <time.h> #define min(a, b) a > b ? b : a #define MAX_NUM   using namespace std; bool debug = true; void swap(int* a, int* b) {     int temp = *a;     *a = *b;     *b = temp; }   void PRINT(vector<int> _arr) { for (int i = 0; i < _arr.size(); i++) { cout << _arr[i] << " "; }cout << "\n";} bool compare(int a, int b) {     return a > b; } void bubble(vector<int> _arr) {     int size = _arr.size();     for (int i = 0; i < size - 1; i++) {         for (int j = 0; j < size - 1 - i; j++)         {             if (compare(_arr[j], _arr[j+1]))                 swap(_arr[j], _arr[j + 1]);         }     }     PRINT(_arr); } /* 1.한번 for문 돌았을떄 어디부분부터 정렬되기 시작하는지 생각한다..  2.인덱스가 아주 중요! 인덱스를 넘는지 안넘는지 확인꼭 바란다. */   void selection(vector<int> _arr) {     int size = _arr.size();     for (int i = 0; i < size - 1; i++)     {         int key_idx = i;         for (int j = i + 1; j < size; j++)             key_idx = (compare(_arr[key_idx], _arr[j])) ? j : key_idx;         swap(_arr[key_idx], _arr[i]);     }     PRINT(_arr); } /* 대표값 : max든 min든,, 을 가지는 인덱스를 찾는다. 그다음 정렬이 차근차근 진행되는 위치랑 스왑한다. */   void insertion(vector<int> _arr) {     int size = _arr.size();     for (int i = 1; i < size; i++)     {         int key = _arr[i]; int key_idx = i-1;         while (key_idx >= 0 && compare(_arr[key_idx], key))         {             _arr[key_idx + 1] = _arr[key_idx]; key_idx--;         }         _arr[key_idx+1] = key;     }     PRINT(_arr); } /* 이미 정렬 되었다고 가정한뒤.. key 값의 위치를 찾으러 두번쨰 for을 돌면서 진행 */     int _part(int _p, int _e, vector<int> &_arr) {     int bench = _p; int low = _p + 1; int high = _e; int left = _p + 1; int right = _e;     while (low <= high)     {         while (low <= right && compare(_arr[_p] ,_arr[low])) { low++; }         while (high >= left && !compare(_arr[_p] ,_arr[high])) { high--; }         if(low <= high)             swap(_arr[low],_arr[high]);     }     swap(_arr[high], _arr[bench]);     return high; } void quick(int _s, int _e,vector<int> &_arr) {     if (_s < _e) {         int pivot = _part(_s, _e, _arr);         quick(_s, pivot-1, _arr);         quick(pivot + 1, _e, _arr);     } } void quicksort(int _s, int _e, vector<int> _arr) {     //주소 참조에 의한 호출     quick(_s, _e, _arr);     PRINT(_arr); } /*  함수를 동시에 여러번 사용하면서 배열의 참조에 의한 호출, 포인터 공부를 하게 되었다.     //https://soyoonique.tistory.com/32     1.퀵 소트는 파티션으로 피봇 기준점을 찾고     그 기준점을 중간으로 두고 왼쪽을 나누고 오른쪽을 나눈다     2. */   void conquer(int _L, int _M, int _R, vector<int> &_arr) {     int LPART_S = _L; int RPART_S = _M+1;     vector<int> _TEMP;     while (LPART_S <= _M && RPART_S <= _R)     {         if (!compare(_arr[LPART_S], _arr[RPART_S]))             _TEMP.push_back(_arr[LPART_S++]);         else             _TEMP.push_back(_arr[RPART_S++]);     }     if (LPART_S <= _M)         for (int i = LPART_S; i <= _M; i++)             _TEMP.push_back(_arr[i]);     else         for (int i = RPART_S; i <= _R; i++)             _TEMP.push_back(_arr[i]);       for (int e : _TEMP)         _arr[_L++] = e; } void merge(int _S, int _E, vector<int>& _arr) {     if (_S < _E)     {         int _M = (_S + _E) / 2;         merge(_S, _M, _arr);         merge(_M + 1, _E, _arr);         conquer(_S, _M, _E, _arr);     } } void mergesort(int _S, int _E, vector<int> _arr) {     merge(_S, _E, _arr);     PRINT(_arr); } /* * https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html merge의      1번 집합은 left 부터 mid 까지     2번 집합은 mid+1부터 right까지인거 확실히 기억해라! */ struct _cmp {     bool operator() (int& a, int& b) {         return compare(a, b);     } }; void heapsort(vector<int> _arr) {     priority_queue<int,vector<int>,_cmp> HEAP;     for (int i : _arr)         HEAP.push(i);     int HSIZE = HEAP.size();     for (int i = 0; i < HSIZE; i++) {         cout << HEAP.top() << ' ';         HEAP.pop();     }     cout << '\n'; } /* * https://codingdog.tistory.com/entry/c-priority-queue-%EC%98%88%EC%A0%9C-compare-%EA%B5%AC%EC%A1%B0%EC%B2%B4%EB%A7%8C-%EC%9E%98-%EC%A0%95%EC%9D%98%ED%95%A9%EC%8B%9C%EB%8B%A4 */   int main() {     //https://prosto.tistory.com/88     FILE* fp;      fp = fopen("random_num.txt", "rt");      vector<int> arr;     while (feof(fp) == 0)     {         int tmpnum = 0; fscanf(fp, "%d", &tmpnum);         arr.push_back(tmpnum);     }     fclose(fp);     //     int N;     printf("버블 삽입 선택 퀵 힙 머지\n");     do {         cin >> N;         switch (N)         {         case 1:             bubble(arr);             break;         case 2:             selection(arr);             break;         case 3:             insertion(arr);             break;         case 4:             quicksort(0,arr.size()-1,arr);             break;         case 5:             heapsort(arr);             break;         case 6:             mergesort(0, arr.size()-1, arr);             break;         default:             break;         }     } while (N != 0);          return 0; } Colored by Color Scripter

cs

※(힙소트는 날로 먹었다..)