퀵 정렬 - Quick Sorting
- 다른 정렬 알고리즘에 비해 빠르다
- 분할, 정렬 알고리즘 사용(divide and conquer)
- pivot 이라는 요소를 지정하고 나누어 각각 리스트를 비교한 후 합친다
- 재귀함수 호출 사용
- 다른 알고리즘에 비해 복잡하게 느껴진다(me too...)
1. QuickSorting.class
1) 초기화
12private int[] arry;private int length;
- 배열, 배열 크기를 정의
2) sort()
1 2 3 4 5 6 | public void sort(int[] arry){ this.arry = arry; this.length = arry.length; quickSort(0, length-1);} |
- 생성자 함수와 같이 값을 초기화 한다
- 퀵 정렬 호출
3) quickSort()
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 35 36 | private void quickSort(int lowIndex, int highIndex){ int pivot = arry[(lowIndex+(highIndex - lowIndex)/2)]; int low = lowIndex; int high = highIndex; //pivot을 기준으로 리스트를 분할 한다 while(low <= high){ //pivot 보다 작은 값이라면 계속진행, 크다면 멈추고 low에 값이 저장된다 while(pivot > arry[low]){ low++; } //pivot 보다 큰 값 while(pivot < arry[high]){ high--; } //만약 low가 high 보다 크다면, 그것은 pivot을 기준으로 양쪽 값이 잘 정렬됬다는 것을 뜻 한다, 위치 바꿀 필요없음 if(low <= high){ //위에서 멈춘 위치의 값들을 서로 교환한다 exchange(low,high); //교환했다면 다시 진행을 위해 증가/감소 한다 low++; high--; } } print(); if(lowIndex < high){ quickSort(lowIndex, high); } if(low < highIndex){ quickSort(low, highIndex); } } |
4) exchange(), print()
1 2 3 4 5 6 7 8 9 10 11 12 | public void exchange(int low, int high){ int temp = arry[low]; arry[low] = arry[high]; arry[high] = temp;}public void print(){ for(int i = 0; i< length; i++){ System.out.print(arry[i]+" "); } System.out.println();} |
- 값 교환하는 부분과 상태를 표시
5) main()
1 2 3 4 5 6 7 8 9 10 11 | public static void main(String[]args){ QuickSorting aa = new QuickSorting(); int bb[] = {10,2,3,99,1,7,-1,100}; for(int a: bb){ System.out.print(a+" "); } System.out.println(); aa.sort(bb);} |
'Algorithm&DataStructures > Sorting' 카테고리의 다른 글
| [Algorithm] 인서트정렬 - Insertion sorting (0) | 2016.12.01 |
|---|---|
| [Algorithm] 선택 정렬(Selection sorting) - Selection sorting (0) | 2016.11.28 |
| [Algorithm] 버블정렬 - bubble sorting (0) | 2016.11.28 |
리딩리드
