수다닷컴

#includestdio.h
#includestdlib.h
#includetime.h
int partition(int Data[], int begin, int end);
int QuickSort(int Data[], int begin, int end);
int select(int Data[], int begin, int end, int search);
int main(){
int Data[20] = {0, };
int end, result, search;
int i, j, key;

srand(time(NULL));

for(i=0; i20; i++){
key =Data[i]= rand()%20;
for(j=i-1; j=0; j--){
if(key == Data[j]){
i--;
break;
}}}
end = sizeof(Data)/4;

printf(정렬전 Data : );
for(i=0; iend; ++i)
printf(%d , Data[i]);
printf(\n);

printf(원소에서 몇번째 작은 값을 찾으시겠습니까? : );
scanf(%d, &search);

result = select(Data, 0, end-1, search);

printf(Select Data is : %d\n,result);

QuickSort(Data, 0, end-1);

printf(정렬후 배열의 Data\n);
for(i = 0; iend; i++)
printf(%3d,Data[i]);
printf(\n);

return 0;
}
int partition(int Data[], int left, int right)
{
int mid, tmp;
mid = (left+right)/2;//가운데 기준점
while(leftright){//left와 right가 같아지면
//더이상 mid를 기준으로 양분할수 없음을 나타낸다
for(;Data[left] Data[mid] && left right; left++);
for(;Data[right] Data[mid] && left right; right--);
//왼쪽에서 기준점보다 큰 수를 오른쪽에서 작은 수를 찾는다
//왼쪽에서 기준점보다 작으면 left++하면서 다음 Data를 검사
if(leftright){
tmp = Data[left];
Data[left] = Data[right];
Data[right] = tmp;
}
}
//두 데이터를 sort한다.
//while(leftright)
tmp = Data[mid];
Data[mid] = Data[right];
Data[right] = tmp;

//leftright가 거짓이 되면 right와 mid를 바꿔준다.
//그 말인즉 Data[mid]를 기준으로하는 정렬은 끝난셈이다.
//mid와 right의 위치를 바꿔줌으로써 정렬이 끝나고 right는 기준점이 된다.
return right;
}
int select(int Data[], int begin, int end, int search){
int mid, small_num;
if(begin == end) return Data[begin-1];
mid = partition(Data, begin, end);
small_num = mid-begin+1;
if(search small_num)
return select(Data, begin, small_num-1, search);
else if(search == small_num){
return Data[mid];
}
else return select(Data, small_num+1, end, search-small_num);
}
int QuickSort(int *Data, int begin, int end){
int mid;
if (begin end){
mid = partition(Data, begin, end);
QuickSort(Data, begin, mid-1);
QuickSort(Data, mid+1, end);
}
return 0;
}

일단 소스는 저런식인데요

프로그램이 돌아가기 시작하면
파티션 부분이 기준값을 찾아서 큰값과 작은값 2부분으로 나누게 됩니다.
그런데 나눌때 문제가 생기는게
M
L R
1, 4, 6 , 7, 9, 10, 0, 11, 13, 15
왼쪽에서 오른쪽으로 점점 가면서 큰값을 찾고
오른쪽에서 왼쪽으로 값을 찾다가
위 상황처럼 기준값과 L이 같아진 상황에서 오른쪽이 작은 값을 찾아내면 저놈을 소트 해버립니다.
그 결과 기준값은 0으로 둔갑하고 왼쪽이나 오른쪽 모두가 기준값보다 큰 값의 집합이 되어 정렬이 안된 상태로 돌아가는데
프로그램은 그 상태를 인지 못하고 L이 기준값인0보다 큰값을 찾아서 쉬프트 하다가 조건이 깨져서 while루프가 종료하면
정렬되지 않은 상태로 리턴시켜 버립니다.
select부분에서도 재귀호출에서 문제가 있어 값을 찾지 못하는 부분이 있습니다.
문제점과 그 해결에 대한 자세한 설명좀 부탁드립니다.

신청하기