자바 퀵 정렬
-
[JAVA/자료구조] 퀵 정렬(Quick Sort)Language/Java 2021. 6. 13. 17:27
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 퀵 정렬(Quick Sort) 퀵 정렬은 n개의 데이터를 정렬할 때 최악의 경우 O(n^2)번의 비교를 수행하고, 평균적으로 O(logN)번의 비교를 수행한다. 퀵 정렬은 찰스 앤터니 리처드호어가 개발한 정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있기 때문에 불안정 정렬에 속한다. 퀵 정렬(Quick Sort) 구현 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한..