드디어 quick sort~~
int Partition(int DataSet[], int Left, int Right){
int First = Left;
int Pivot = DataSet[First]; //맨 처음요소를 기준으로 잡는다
++Left;
while(Left <= Right){
while( DataSet[Left] <= Pivot && Left <= Right)
++Left; //왼쪽에서부터 출발해서 기준보다 큰 요소를 찾는다
while( DataSet[Right] >= Pivot && Left <= Right)
--Right; //오른쪽부터 출발해서 기준보다 작은 요소를 찾는다
if( Left < Right)
Swap(DataSet[Left], DataSet[Right]); //위에서 찾은 큰거와 작은거를 바꿔줌
else
break;
}
Swap(DataSet[First], DataSet[Right]); //기준과 왼쪽집합의 끝요소를 바꿔준다
return Right;
}
void QuickSort(int DataSet[], int Left, int Right){
if(Left < Right){
int Index = Partition(DataSet, Left, Right); //기존의 집합을 쪼갠후 쪼개진 인덱스를 반환
QuickSort(DataSet, Left, Index-1);
QuickSort(DataSet, Index+1, Right);
}
}
성능분석을 해보자
맨처음의 n개로 이루어진 집합을 하나하나씩 다 쪼개야하는데
2개로 쪼개는데 1번, 4개로 쪼개는데 2번, 8개로 쪼개는데 3번....
아 그럼 n개로 쪼개는데는 lon(2)n 번만큼의 호출이 필요하다
그리고 Partiton()에서는 앞에서, 뒤에서 각각 비교를 하는데 n번 비교한다 n개의 원소가 있으니까
2개로 쪼개지면 n/2 + n/2 = n, 4개로 쪼개지면 n/4 + n/4 + n/4 + n/4 = n 으로 결국 모두 n번 비교한다
그래서 총 회수는 nlog(2)n 이다<p>
디바이드 앤 퀀커의 한 종류란다<p>
그리고 스탠다드 라이브러리에 qsort()가 구현되어있다, 함수 원형은 다음과 같다
void qsort(void *base, size_t num, size_t width, int(_cdecl *compare)(const void *, const void *));
순서대로 데이터 집합의 배열주소, 데이터요소의 개수, 한 데이터의 크기, 비교함수에 대한 포인터이다
나머지는 다 알겠는데 맨 마지막에 인자가 뭔가 요상하다
다음과 같이 매번 작성해줘야 한다
int Compare(const void *_elem1, const void *_elem2){
int *elem1 = (int*)_elem1;
int *elem2 = (int*)_elem2;
if( *elem1 > *elem2 ) return 1;
else if( *elem1 < *elem2 ) return -1;
else return 0;
}
데이터의 자료형에 따라 첫째, 둘째 줄을 수정해주어야한다
하는 역할은 stl의 compare함수와 비슷한 것 같다
