[알고리즘/정렬] Quick Sort 퀵 정렬 - C++ 코드, 시간/공간 복잡도
알고리즘에 대한 설명은 생략하고, 바로 코드로 넘어가겠다 void quickSort(vector& v, int s, int e) { int pivot = v[s]; // 임의 선택 int bs = s, be = e; while(s v[s] && s e) break; swap(v[s], v[e]); } if(bs e) // 오른쪽 quickSort(v, s+1, be); } 코드를 풀어서 설명하자면, v[s] < pivot < v[e] 는 정상이다. 그 경우 s++, e--를 해야한다. (그냥 넘어가야 하..
[알고리즘/정렬] Merge Sort 합병 정렬 - C++ 코드, 시간/공간 복잡도
알고리즘에 대한 설명은 많은 곳에 있으니 생략하고, 코드와 시간복잡도 및 공간복잡도만 살펴보겠다. void mergeSort(vector& v, int s, int e) { if(s >= e) return; int m = (s+e)/2; // divide mergeSort(v, s, m); // s ~ m mergeSort(v, m+1, e); // m+1 ~ e // conquer vector ret(e+1); int ret_idx = 0; int i = s, j = m+1; // i : s ~ m, j : m+1 ~ e // 결과를 저장할 배열에 하나씩 비교하여 저장 while(i
