quick sort

갑자기 왠 퀵 정렬이냐 라곤 하지만,

그나마 정렬에선 퀵 정렬이 빠르고 그만큼 저도 자주 애용하는 정렬 기법입니다.

정리해 두었다가 필요할 때 잽싸게 훑어볼 목적으로 글을 남깁니다. 크크크.

먼저 정렬을 할 배열 중에서 어느 기준의 값을 하나 정합니다. 우리는 그것을 pivot(중심축)이라고 하죠.

그리고 배열의 왼쪽으로부터 검색하여(iLow) 배열의 값이 pivot보다 크거나 같은 값의 인덱스를 찾습니다.

역시 그 배열의 오른쪽으로부터 검색하여(iHigh) 배열의 값이 pivot보다 작은 값의 인덱스를 찾습니다.

-임의로 결정한 pivot은 5. 왼쪽 인덱싱의 값은 1, 오른쪽 인덱싱의 값은 8-

둘이 가리키는 데이터를 교체합니다.

이어서 같은 방식으로 계속 검색해 나갑니다.

- 0와 9를 교체-

그러다가 iLow와 iHigh가 엇갈리는 순간이 되면, pivot의 값과 iHigh의 값을 교체해 줍니다.

-pivot값 5와 iHigh의 4의 값과 교체-

여기까지 정렬의 1단계가 끝. 이제부터 분할 정복이 시작됩니다.

분할 정복에 대해 간단히 설명하자면,

배열의 범위를 마지막 iHigh의 인덱스를 기준으로 쪼개서 나눠진 둘의 범위에 대해 위의 과정을 반복하는 것이지요.

-1단계 마지막 iHigh 값을 기준으로 두 범위로 나눠서 각각 1단계를 적용-

 

-2단계 후. 이 예에서는 각각의 분할 축의 위치가 한쪽에 치우쳐 있어서 더 이상 분할되지가 않는다-

-3단계 후-

-4단계 후. 정렬 완료-

아래는 소스입니다. 주석이 있으니 이해하기엔 충분할 겁니다. (파일 첨부)

// pArray : 데이터가 들어있는 배열 // iLow_ : 정렬할 범위의 최하 인덱스 // iHigh_ : 정렬할 범위의 최상 인덱스 template< typename T > void quick_sort( T* pArray, int iLow_, int iHigh_ ) { //인덱스 점검 if( iLow_ >= iHigh_ ) { return ; } int iLow, iHigh; //인덱스 int pivot; //비교할 기준 값 iLow = iLow_; iHigh = iHigh_ + 1; pivot = pArray[ iLow_ ]; //기준 데이터는 최하 인덱스의 데이터로 do { //교체할 데이터 위치를 찾는다. do { }while( pArray[ ++iLow ] < pivot ); //교체할 데이터 위치를 찾는다. do { }while( pArray[ --iHigh ] > pivot ); //기준보다 큰 데이터와 적은 데이터를 서로 교환 if( iLow < iHigh ) { // pArray[ iLow ] ^= pArray[ iHigh ] ^= pArray[ iLow ] ^= pArray[ iHigh ]; //Swap! only integer, short available T temp = pArray[ iLow ]; pArray[ iLow ] = pArray[ iHigh ]; pArray[ iHigh ] = temp; }else { break; } }while( TRUE ); //정렬 후, pivot과 iHigh 교체 pArray[ iLow_ ] = pArray[ iHigh ]; pArray[ iHigh ] = pivot; //분할 정복 quick_sort( pArray, iLow_, iHigh - 1 ); quick_sort( pArray, iHigh + 1, iHigh_ ); }//void quick_sort

[출처] Quick Sort ( 퀵 정렬 )|작성자 Hermet

Change JAVA


public List<Integer> sort(List<Integer> target) {
  List<Integer> returnValue = new ArrayList<Integer>(target);
  
  quickSort(returnValue,0,returnValue.size()-1);

  return returnValue;
 }

private void quickSort(List<Integer> target, int iLow_, int iHigh_) {
  
  if (iLow_ >= iHigh_) {
   return;
  }

  int iLow, iHigh;
  int pivot;

  iLow = iLow_;
  iHigh = iHigh_ + 1;
  pivot = target.get(iLow_);

  do {

   do {
   } while (target.get(++iLow) < pivot);

   do {
   } while (target.get(--iHigh) > pivot);

   if (iLow < iHigh) {

    int temp = target.get(iLow);

    target.set(iLow,target.get(iHigh));

    target.set(iHigh,temp);
   } else {
    break;
   }

  } while (true);

  target.set(iLow_,target.get(iHigh));
  target.set(iHigh,pivot);

  quickSort(target, iLow_, iHigh - 1);
  quickSort(target, iHigh + 1, iHigh_);
 }