Sort 알고리즘(퀵정렬-재귀호출이용)

퀵 정렬(Quick Sort) 이란 주어진 입력리스트를 특정한 키(Control Key, Pivot)로 분리하여 왼쪽에는 키 값보다 작은 값, 우측에는 키 값보다 큰 값을 갖는 서브 리스트로 분리한다. 그런 다음 각각의 서브리스트에서도 같은 방법을 반복적으로 수행하여 정렬하는 방법이다.


다음의 예제를 보자...

import java.util.Random;
class QuickSort3{
//퀵 정렬(재귀방법)
int[] qsort(int a[]) {
//low와 high 값을 parameter로 던지자.
quicksort(0, a.length-1, a);
return a;
}

void quicksort(int low, int high, int[] a) {
if (low < high){
//서브리스트로 분할
int pivot = split(low, high, a);
//생성된 pivot값을 기준으로 재귀호출
quicksort(low, pivot-1, a);
quicksort(pivot+1, high, a);
}
}

//pivot 값이 제위치에 정렬되도록 위치를 계산하고  
//입력된 레코드를 재배열
private int split(int low, int high, int[] a) {
int avg = (low + high)/2;  //pivot위치를 찾는다.
exchange(low, avg, a);
int last = low;
for(int i=low+1; i<=high; i++) {
//i값이 pivot값(low위치 값) 보다
//작으면 바꾼다.
//last를 1증가후 i위치값과 low위치값을 바꿈
if (a[i] < a[low]){  
last++;
exchange(last, i, a);
}
}
exchange(low, last, a);
return last;
}

private void exchange(int low, int high, int[] a) {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}


public static void main(String[] args){
int nansu[] = new int[10000];
int[] sortedArray = new int[10000];
int[] halfSortedArray = new int[10000];
int[] reverseArray = new int[10000];
int[] temp = new int[10000];
long startTime, elapsedTime, counter;

QuickSort3 mySort = new QuickSort3();  
//----------------- 난수 발생시킴
Random r = new Random();
for(int i=0; i<10000; i++) {
nansu[i] = r.nextInt(100000);
}
//-----------------------------------

//------------------------------------------------------------------------------
//난수를 정렬
//------------------------------------------------------------------------------
counter=0;
startTime = System.currentTimeMillis();
do {
counter++;
sortedArray = mySort.qsort(nansu);
} while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[난수일때의 수행시간] " + elapsedTime + "ms");

//------------------------------------------------------------------------------
// 정렬된 상태(최선의상황)을 다시 정렬시킴
//------------------------------------------------------------------------------
counter=0;
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.qsort(sortedArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[최선의 상황 수행시간] " + elapsedTime + "ms");
//-------------------------------------------------------------------------------

//-------------------------------------------------------------------------------
//반쯤 정열후 ...
//-------------------------------------------------------------------------------
counter=0;
halfSortedArray = sortedArray;
for(int i=0; i<5000; i++) {
halfSortedArray[i] = r.nextInt()*10000;
}
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.qsort(halfSortedArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[반쯤 정렬 수행시간] " + elapsedTime + "ms");
//-------------------------------------------------------------------------------

//-------------------------------------------------------------------------------
//역순상태
//-------------------------------------------------------------------------------
counter=0;
for(int i=0;i<sortedArray.length;i++) {
reverseArray[sortedArray.length-i-1] = sortedArray[i];
}
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.qsort(reverseArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[역순 상태 수행시간] " + elapsedTime + "ms");
//--------------------------------------------------------------------------------
}
}