갑자기 왠 퀵 정렬이냐 라곤 하지만,
그나마 정렬에선 퀵 정렬이 빠르고 그만큼 저도 자주 애용하는 정렬 기법입니다.
정리해 두었다가 필요할 때 잽싸게 훑어볼 목적으로 글을 남깁니다. 크크크.
먼저 정렬을 할 배열 중에서 어느 기준의 값을 하나 정합니다. 우리는 그것을 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_);
}
c.tld
