퀵소트
-
퀵소트 알고리즘 :: 마이구미알고리즘 2018. 4. 10. 15:51
이 글은 정렬 중 퀵소트(Quick Sort), 퀵정렬이라고 불리는 정렬을 다뤄본다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 기본적인 버블 정렬처럼 많이 언급되는 정렬이다. 1. 퀵소트란 무엇인가?2. 퀵소트는 어떻게 구현하는가?3. 퀵소트는 어떻게 개선할 수 있는가? -위키- 퀵소트는 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다. 시간복잡도는 최악의 경우 O(n^2), 평균적으로 O(nlogn) 을 가진다.시간복잡도가 O(n^2) 임에도 불구하고 퀵소트가 빠른 정렬에 속하는 이유에 대해 의문을 가질 수 있다.하지만 O(n^2) 은 설계를 통해 개선이 가능한 부분이다. 관련 내용은 아래에서 다루니 끝까지 읽는다..