선택알고리즘을 짜는데 논리적인 오류를 못잡겠네요.
날위해
#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부분에서도 재귀호출에서 문제가 있어 값을 찾지 못하는 부분이 있습니다.
문제점과 그 해결에 대한 자세한 설명좀 부탁드립니다.
번호 | 제 목 | 글쓴이 | 날짜 |
---|---|---|---|
2700400 | 원넓이를 계산이요 ㅜㅜ | 천칭자리 | 2025-07-04 |
2700368 | if에 관해서 질문이요... | Orange | 2025-07-04 |
2700339 | 이거 결과값이 왜이런건지.. (4) | 그댸와나 | 2025-07-04 |
2700313 | 파일 읽어서 저장하는데 빈파일일 경우 문재가 발생하네요.. (2) | 크나 | 2025-07-03 |
2700287 | 구조체 동적할당 연습을 하는데 오류가 뜹니다...(해결) (3) | 아련나래 | 2025-07-03 |
2700264 | 문자와 숫자 동시에 입력??? | 글고운 | 2025-07-03 |
2700236 | txt파일로만 쓰고 읽게 하려면 어떻게 해야 하나요..?? (8) | 미국녀 | 2025-07-03 |
2700211 | 전위 연산자 (2) | 어른처럼 | 2025-07-02 |
2700183 | C에서 파일이름을 받고, 그 파일의 사이즈를 출력해줘야하는데 내용이 출력이 안되네요 ;ㅅ; | 피스케스 | 2025-07-02 |
2700150 | 꼭좀 도와주세요ㅠㅠㅠ | 호습다 | 2025-07-02 |
2700095 | 연산문제...질문... | 오빤테앵겨 | 2025-07-01 |
2700070 | while문 , 3의배수 출력하는 프로그램좀 짜주세욤. | 횃불 | 2025-07-01 |
2700041 | 초보인데요 ㅎ 배열안에 배열을 집어넣을수 있나요?? | 헛장사 | 2025-07-01 |
2700012 | 배열// (1) | 전갈자리 | 2025-07-01 |
2699895 | 무한루프에 빠집니다.!! 해결좀부탁드려요 (10) | 선아 | 2025-06-30 |
2699842 | 질문을 너무 많이 하네여.....죄송.... (2) | 해님꽃 | 2025-06-29 |
2699816 | 오류 질문입니다.. (1) | 해비치 | 2025-06-29 |
2699763 | 질문입니다 ! 꼭 좀 도와주세요ㅠㅠ (2) | 미라 | 2025-06-28 |
2699555 | c언어 다항식을 입력을 했는데 왜 출력이 안될까요? | 피스케스 | 2025-06-27 |
2699528 | C언어 포인터연산 질문입니다. (3) | 안녕나야 | 2025-06-26 |