퀵정렬
-
Quick Sort (퀵정렬, 퀵소트)algorithm 2013. 6. 5. 10:34
참조 1. http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 2. http://en.wikipedia.org/wiki/Quicksort 3. http://codereview.stackexchange.com/questions/4022/java-implementation-of-quick-sort 시간복잡도 가장 나쁜 경우 : O(n^2) 가장 좋은 경우 : O(n log n) 평균 성능 : O(n log n) 장점 대부분의 경우에 빠르게 정렬이 가능. 단점 운이 없을때는 O(n^2) 만큼의 정렬 시간이 걸림. 알고리즘 1. 리스트에서 피봇(pivot)으로 사용할 원소를 선택 2. 리스트를 재정렬함. 이때 피봇보다 작은 값은 피봇 이전에 오게하고 피봇보다 ..