MergeSort (병합 정렬)
이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하
sol248.tistory.com
QuickSort (퀵정렬)
이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만, 배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬
sol248.tistory.com
앞서 살펴본 퀵정렬과 병합정렬을 비교해보겠습니다.
먼저, 퀵정렬은 난수를 사용했기 때문에 결정적인 알고리즘 이라고 할 수 없습니다.
(non-deterministic algorithm)
위의 표의 내용들은 코드를 어떻게 짜느냐에 따라 조금씩 달라질 수 있습니다.
번거로울 수 있지만 QuickSort 로도 LinkedList를 만들 수 있고,
pivot 값을 어떻게 설정하느냐에 따라 시간 복잡도 또한 달라질 수 있습니다.