솔

https://sol248.tistory.com/50 MergeSort (병합 정렬)이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하sol248.tistory.comhttps://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com  앞서 살펴본 퀵정렬과 병합정렬을 비교해보겠습니다. 먼저, 퀵정렬은 난수를 사..

https://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com퀵정렬은 중복된 값이 많을수록 느리다는 단점이 있기 때문에 앞에서는 중복된 값이 없다는 가정을 하고 진행했습니다. 이것을 극복할 수 있는 방법이 3-way partitioning 입니다. 앞에서는 pivot 값보다 작은것과 큰 것 두 묶음으로 나누었지만, 여기서는key 값보다 작은 값,key 값과 같은 값,key 값보다 큰 값이렇게 3가지로 나눕니다. 구현 자체는 어렵지 않습니다. 코드) void Quick3way(..

이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬은 pivot 값을 중심으로 배열을 두 개로 나눕니다. 이떄 pivot 값은 어떤 값이 되어도 상관 없습니다. (pivot 값에 따라 시간 복잡도가 달라집니다) -퀵정렬 코드(난수x)int Partition(int* arr, int low, int high, int n) { int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low]; int i = low; int j = high; while (true) { while (arr[i] pivot) j--; if (..