재귀형 퀵소트..소스..자바..

|
Private static void quickSort(Comparable [ ]a, int left, int right)
{
    if(left + CUTOFF <= right)
    {
        Comparable pivot = median3(a, left, right); // Pivot 값으로 중간값을 설정한다.
        //분할 시작
        int i=left, j=right-1;
        // i, j 는 배열의 처음과 끝을 나타내는 배열의 첨자(subscript)이다.
        for(;;)
        // Pivot 원소를 중심으로 두 부분으로 나눈다.
        {
            while(a[++i].compareTo(pivot) < 0) { }
            // 배열의 앞에서부터 차례대로 Pivot원소보다 작은 
원소들은 그대로 두고, 
            // 큰 원소를 만나면 i값을 늘리지 않고, 루프문을 빠져나간다. 

            while(a[--j].compareTo(pivot) > 0) { }
            // 배열의 앞에서부터 차례대로 Pivot원소보다 큰 
원소들은 그대로 두고, 
            // 작은 원소를 만나면 j값을 늘리지 않고, 루프문을 빠져나간다. 

            if(i<j)
                swapReferences(a, i, j);
                // 
위의 두 루프문에서 각 부분리스트에 속할 원소들이 아닌 원소들은
                // 서로 자리를 바꾸어 준다.

            else
                break;
        }
 
        swapReferences(a, i, right - 1);  // Pivot 원소를 두 부분리스트 사이에 위치시킨다.
        
        // 각 두 부분리스트에 대해서 위의 과정을 반복한다.
        quicksort(a, left, i-1);  // Pivot 보다 작은값들을 정렬한다.
        quicksort(a, i+1, right); // Pivot 보다 큰 값들 정렬한다.
    }
    else    // 작은 배열에서는 삽입정렬을 사용함으로서 효율을 증대시킨다.
        insertionSort(a, left, right)

--------------------------------------------

자바에서 퀵소트는 자바 API중 Java.util.* 에 포함되어있는 Arrys.sort()라는 함수를 이용하면

더 쉽게 퀵소트를 구현할수 있으나 API에 있는 퀵소트는 1차원 배열밖에 지원을 하지 않으므로

2차원 퀵소트를 할려면 아래와 같은 소스들을 이용하여 2차원 배열로 만들어 사용해야 한다.

퀵소트 소스들중 10000건 이상이되면 스택이 오버플로우가 생겨 소팅이 안되는 소스들이

웹상에 많이 있는것 같아서 다른 형태의 소스를 한번 작성해서 올려본다.

 

import java.util.*;

 

public class QSortAlgorithm {

 static int n = 30;  //소팅할 갯수
 static int sja[] = new int[n]; // 소팅을 할 배열  2차원일시에는 2차원배열로 선언한다.

 

/**

* 소팅 배열에 랜덤함수를 이용하여 숫자를 입력해넣는다.

*/

 public void randInit(){
   for (int i = 0; i < n; i++ ){
       int r = (int)(Math.random()*n+1);  //랜덤함수를 발생하여 배열을 초기화
       sja[i]=r;
   } 
   System.out.print("before : ");   
   for (int i = 0; i < sja.length; i++ ){
      System.out.print(sja[i] + " ");   //소팅전 데이타를 출력해본다.
    }
 }

 

/**

* 소팅 배열에 랜덤함수를 이용하여 숫자를 입력해넣는다.

*/

 public void QuickSort(int a[], int lo0, int hi0)
   {
      int lo = lo0;
      int hi = hi0;
      int mid;

      if ( hi0 > lo0)
      {

          mid = a[ ( lo0 + hi0 ) / 2 ];

         while( lo <= hi )
         {
            while( ( lo < hi0 ) && ( a[lo] < mid )) ++lo;

            while( ( hi > lo0 ) && ( a[hi] > mid )) --hi;

            if( lo <= hi )
            {
               swap(a, lo, hi);
               ++lo;
               --hi;
            }
         }

         if( lo0 < hi )
            QuickSort( a, lo0, hi );

         if( lo < hi0 )
            QuickSort( a, lo, hi0 );

      }
   }

/**

* 소팅데이타를 바꾸는 함수부분

*/

   private void swap(int a[], int i, int j)
   {
      int T;
      T = a[i];
      a[i] = a[j];
      a[j] = T;

   }

 

/**

* 소팅후 소팅된 데이타를 출력한다

*/

   public void PrintSort(){
      System.out.print("after :");
   for (int i = 0; i < sja.length; i++ ){
       System.out.print(sja[i]+ " ");
    }
 }

 

/**

* 메인함수

*/

 public static void main(String[] args) 
 {
    try{
    QSortAlgorithm quick = new QSortAlgorithm();
    quick.randInit();
    quick.QuickSort(sja, 0, sja.length - 1);
    System.out.println();
    quick.PrintSort();
    }catch(Exception ex){
     System.out.println(ex);
    }
   }

}

[출처] 자바 퀵소트(숫자)|작성자 제리

'개발/활용정보 > Java' 카테고리의 다른 글

Ubuntu 10.04 리눅스에서의 개발 환경 설정(JDK 6, Eclipse Galileo)  (0) 2011.12.13
Eclipse Memory Analyzer  (0) 2011.11.28
ant 사용법  (0) 2011.04.19
Ant 태스크  (0) 2011.04.19
Creating a Custom Event  (0) 2011.04.19
And