퀵정렬

[JAVA] 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick sort) 퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 시간복잡도가 비교적 빠르기 때문에 코딩테스트에서도 종종 응용한다. 평균 시간복잡도는 O(nlogn)이고, 최악은 O(n^2)이다. 이미 정렬돼 있는 배열에 적용할 때 최악의 시간복잡도를 가진다. 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고, 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에..