- 리스트 가운데서 하나의 원소를 고름(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 |
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));
}
}
정말 대단합니다..ㄷㄷ
한 가지 궁금한 점이 있는데 아래 코드에서 스왑 하기전에 left <= right 비교를 하는 이유가 무엇인지 좀 헷갈립니다 ..ㅠㅠ
if(left <= right){
int temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}