수다닷컴

질문 제목 : 퀵소트 관련 질문입니다.퀵소트 구현시 워스트 케이스를 개선하기 위해 두 수중 작은 부분에 대해서 재귀호출을 하고 또 배열중 가운데 값을 찾아 array[left]와 교환하게 하는 법이 좀 헷갈립니다.질문 내용 : 일단 소스 부분인데요....

void quick_sort(int* array, int left, int right)
{
int temp;
if(left right){
temp = partition(array, left, right);

quick_sort(array, left, temp-1);//왼쪽부분 quick sort
quick_sort(array, temp+1, right);//오른쪽부분 quick sort
}
}
int partition(int* array, int left, int right)
{
int i = left;
int j = right+1;
int temp;//swap시 필요한 변수

int pivot = array[left];//가장 왼쪽의 값을 기준값으로 설정
int new_pivot;

new_pivot = median(array, left, right);//메디안 값을 찾아서 new_pivot에 저장
swap(new_pivot, /*array[left]*/pivot, temp);//array[left]가 저장되어 있는 pivot 함수와 swap
pivot = array[left];//교환 후 array[left] 값을 기준으로 정렬 수행 준비.
do{
do i++; while(array[i] pivot);
do j--;while(array[j] pivot);

if(i j)
swap(array[i],array[j],temp);//i pivot, j pivot
}while(i j);
swap(array[left], array[j], temp);

return j;
}
int median(int* array, int left, int right)
{
int median = (left + right)/2 - 1;
int i, j;
int temp;
int temp2[3] = {array[left], array[median], array[right]};

for(i=0;i2;i++) //우선 left, right, median 값들을 순차적으로 정렬
{
for(j=0;j2;j++)
{
if(temp2[j]temp2[j+1]) //앞에있는 배열의 숫자가 뒤에 있는 배열의 숫자보다 크면 두개를 바꾸어줌
{
temp=temp2[j];
temp2[j]=temp2[j+1];
temp2[j+1]=temp;
}
}
}
return temp2[1];//temp 배열이 3개의 원소를 가지고 있으므로 두번째 값이 중간값 그러므로 temp[1]을 리턴한다.
}

파티션 함수가 워스트 케이스를 피하기 위해 작은 부분을 먼저 호출합니다.
그런다음 파티션 함수 내에서... 또다른 워스트 케이스를 피하기 위해 배열의 가운데 위치한 값하고 인자로 넘어온 left위치에
있는 array[left] 와 교환후 퀵소트를 해야 하는데요....

파티션 함수만 있음 잘 돌아가는데 median 함수를 추가해서는 자꾸 틀린 소팅을 하네요 ㅠ 파티션함수 내에서
메이안 함수를 호출 부분이 조금 이상한거 같은데 도통 원인을 모르겠습니다 ㅠ 좀 알려주세요

신청하기