[오라클자바강좌]JAVA Sort 알고리즘(퀵정렬-재귀호출이용) 예제 입니다. JAVA강좌

java,java교육,java강좌,oraclejava,javaoracle,오라클자바,자바,자바교육,자바강좌,구로디지털자바,구로디지털오라클,오라클자바교육


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


오라클자바커뮤니티에서 설립한 오엔제이프로그래밍 실무교육센터

(신입사원채용무료교육, 오라클SQL, 튜닝, 힌트,자바프레임워크, 안드로이드, 아이폰, 닷넷)  

www.onjprogramming.co.kr

다음의 예제를 보자... 

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

[출처] 오라클자바커뮤니티 - http://www.oraclejavanew.kr/bbs/board.php?bo_table=LecJavaAlgorithm&wr_id=40