오랜만에 자료처리를 다루다가 소트를 해야할 일이 발생했습니다.
오래전 기억만 남은 도스시절에 짜둔 퀵소트 소스를 찾아낼리가 없었습니다 ㅠㅜ
이거저거 찾아보다가 여러 예제를 보아도
비교하고 바꾸는 루틴을 외부에서 정의하는 예제는 찾을 수 없었습니다. (게을러서 못찾았을수도;)
찾기 귀찮아서 하는 수 없이 새로 만들었습니다.
//==============================================================================
//2022.06.12
저작권 weenist
사용권 개인사용자 무제한
주의점
int64형의 인덱스변수들은 int, int32형으로 바꿔도 가능하지만
unsigned형인 uint64, uint32 DWORD 등으로하면 인덱스 체크하는 과정을 따로 넣어야합니다.
그렇지않으면 실행시 인덱스 범위 오류가 나타납니다!!
//==============================================================================
//사용자 정의 함수 비교, 스왑 루틴 함수포인터 선언 (개인취향 코딩 스타일임을 참고)
typedef int (*__wmQScompare)(void *data, int64_t i1, int64_t i2);
typedef void (*__wmQSswap)(void *data, int64_t i1, int64_t i2);
//==============================================================================
//퀵소트 메인함수
void wmQuickSort(void *data, int64_t start, int64_t end, __wmQScompare wmQScompare, __wmQSswap wmQSswap)
{
int64_t pivot,left,right;
if(start>=end) return;
pivot = start; left = pivot+1; right = end;
while(left<=right){
while(left<=end && wmQScompare(data,left,pivot)>=0) left++;
while(right>start && wmQScompare(data,right,pivot)<=0) right--;
if(left>=right) break;
wmQSswap(data,left,right);
}
wmQSswap(data,right,pivot);
wmQuickSort(data, start, right-1, wmQScompare, wmQSswap);
wmQuickSort(data, right+1, end, wmQScompare, wmQSswap);
}
//==============================================================================
//각종 예제 함수
//구조체 형이거나 메모리 포인터이거나 어떠한 자료형이라도 그 자료형에 맞게
//비교 스왑 함수만 적절하게 작성해주면 어떠한 자료구조에서도 사용가능합니다
/* __wmQScompare 예제 int[] 형으로 작성 테스트
// 오름차순...i1<i2 return 1, i1>i2 return -1
// 내림차순...i1<i2 return -1, i1>i2 return 1
int qsc(void *data, int64_t i1, int64_t i2)
{
int *arr;
arr = (int*)data;
if( *(arr+i1) < *(arr+i2)) return 1;
if( *(arr+i1) > *(arr+i2)) return -1;
return 0;
}
*/
/* __wmQSswap 예제 int[] 형으로 작성 테스트
void qss(void *data, int64_t i1, int64_t i2)
{
int *arr, temp;
arr = (int*)data;
temp = *(arr+i1);
*(arr+i1) = *(arr+i2);
*(arr+i2) = temp;
}
*/
/* wmQuickSort 테스트 예제 int[] 형으로 작성 테스트
void TestQS(void)
{
int ct, arr[100];
for(ct=0;ct<100;ct++) arr[ct] = rand()%1000;
for(ct=0;ct<100;ct++){
wbDebugPrint(LogFN,"[%02d]=%d",ct,arr[ct]);
}
wmQuickSort(&(arr[0]),0,99,qsc,qss);
for(ct=0;ct<100;ct++){
wbDebugPrint(LogFN,"[%02d]=%d",ct,arr[ct]);
}
*/
//==============================================================================
최근 덧글