2015. 10. 26. 21:06
- 리스트 가운데서 하나의 원소를 고름(pivot 선정)
- pivot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 리스트를 둘로 분할한다.
- 분할된 두 개의 리스트에 대해 재귀함수를 통해 이 과정을 반복한다.
- 시간복잡도 : 최악 O(n^2), 평균 O(nlogn)
JAVA 소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public class Quick { public void sort(int[] data, int l, int r){ int left = l; int right = r; int pivot = data[(l+r)/2]; do{ while(data[left] < pivot) left++; while(data[right] > pivot) right--; if(left <= right){ int temp = data[left]; data[left] = data[right]; data[right] = temp; left++; right--; } }while (left <= right); if(l < right) sort(data, l, right); if(r > left) sort(data, left, r); } public static void main(String[] args) { int data[] = {66, 10, 1, 34, 5, -10}; Quick quick = new Quick(); quick.sort(data, 0, data.length - 1); for(int i=0; i<data.length; i++){ System.out.println("data["+i+"] : "+data[i]); } } } | cs |
'JAVA > 정렬' 카테고리의 다른 글
| 퀵 정렬(Quick Sort) (9) | 2015.10.26 |
|---|---|
| 삽입 정렬(Insertion Sort) (5) | 2015.10.26 |
| 선택 정렬(Selection Sort) (5) | 2015.10.26 |
| 버블 정렬(Bubble Sort) (2) | 2015.10.25 |
2016.09.23 10:16 신고
좋은 글이어서 출처 명확히 하여 퍼가겠습니다.
2017.02.06 16:37
비밀댓글입니다
2017.03.18 08:42
좋은 자료 잘 보고 갑니다. 감사합니다.
import java.util.Arrays;
public class QuickSort {
public void sort(Integer[] array, int left, int right) {
int pivot = array[(left + right) / 2];
do {
for(;array[left]>pivot;left++) ; //for문 두곳의 >대소 비교 연산자를 바꾸면
for(;array[right]<pivot;right--); //오름차순 내림차순으로 정렬가능하다.
if (left <= right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
} while (left <= right);
if (left < right)
sort(array, left, right);
if (right > left)
sort(array, left, right);
}
public static void main(String[] args) {
Integer[] array = { 65, 12, 1, 41, -5, -1 };
QuickSort quick = new QuickSort();
quick.sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}
2017.06.19 08:24
최적화된 소스를 보고 많은 것을 배웠습니다. 감사합니다.
2018.09.22 07:54
스킨깔끔하네요 사신건가요?
2019.03.11 22:30
비밀댓글입니다
2020.05.28 19:47
지금까지 본 소스중에 제일 깔끔하고 이해하기 쉽네요.. 잘봤습니다.
2020.10.05 19:32
다른 블로그에서 봐왔던 유사 퀵정렬이랑은 다르게 성능이 정말 좋네여.. ㄷㄷ
정말 대단합니다..ㄷㄷ
2021.05.18 15:26
선생님 안녕하세요. 퀵 정렬 공부 중에 좋은 자료 보고 갑니다!
한 가지 궁금한 점이 있는데 아래 코드에서 스왑 하기전에 left <= right 비교를 하는 이유가 무엇인지 좀 헷갈립니다 ..ㅠㅠ
if(left <= right){
int temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}