728x90
반응형
- 리스트 가운데서 하나의 원소를 고름(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 |
출처: http://hahahoho5915.tistory.com/9?category=653519 [넌 잘하고 있어]
728x90
반응형
'Web Programming > java-jsp' 카테고리의 다른 글
java 소수 구하기 + 실행시간 단축 (0) | 2018.08.29 |
---|---|
java 선형 큐(Linear Queue) (0) | 2018.08.29 |
java 삽입 정렬(Insertion Sort) (0) | 2018.08.29 |
java 버블 정렬(Bubble Sort) (0) | 2018.08.29 |
java 선택 정렬(Selection Sort) (0) | 2018.08.29 |