[Algorithm] 퀵 정렬 - Quick Sorting

퀵 정렬  - Quick Sorting

- 다른 정렬 알고리즘에 비해 빠르다

- 분할, 정렬 알고리즘 사용(divide and conquer)

- pivot 이라는 요소를 지정하고 나누어 각각 리스트를 비교한 후 합친다

- 재귀함수 호출 사용

- 다른 알고리즘에 비해 복잡하게 느껴진다(me too...)

1. QuickSorting.class

1) 초기화

private int[] arry; private int length;

- 배열, 배열 크기를 정의

2) sort()

public void sort(int[] arry){ this.arry = arry; this.length = arry.length; quickSort(0, length-1); }  

- 생성자 함수와 같이 값을 초기화 한다

- 퀵 정렬 호출

3) quickSort()

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()

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()

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); }