[데이터 구조] 퀵소트(Quick Sort)

오늘은 정렬 알고리즘 중에서 퀵소트(Quick Sort)에 대해 공부해보았다. 실제 많은 곳에서 사용된다는 퀵소트는 무엇이고, 어떠한 방식으로 구현이 되는지를 알아보았고, 시간복잡도와 최악의 경우, 또 그 해결법을 살펴보았다. 퀵소트(Quick Sort)란 무엇일까? - 출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 퀵소트는 분할 정복 방식을 이용한 정렬 알고리즘으로, 하나의 큰 문제를 여러 개의 작은 문제로 쪼개어 풀어나가는 것이 특징이다. 퀵소트는 아이러니하게도 시간복잡도가 최악의 경우 O(n^2)라는 매우 느린 값을 가지면서도 빠른 정렬 알고리즘이라고 알려져 있다. 또한, 특이하게 BIG-O Notation을 최악의 경우가 아닌 평..

2021.04.22