수다닷컴

  • 해외여행
    • 괌
    • 태국
    • 유럽
    • 일본
    • 필리핀
    • 미국
    • 중국
    • 기타여행
    • 싱가폴
  • 건강
    • 다이어트
    • 당뇨
    • 헬스
    • 건강음식
    • 건강기타
  • 컴퓨터
    • 프로그램 개발일반
    • C언어
    • 비주얼베이직
  • 결혼생활
    • 출산/육아
    • 결혼준비
    • 엄마이야기방
  • 일상생활
    • 면접
    • 취업
    • 진로선택
  • 교육
    • 교육일반
    • 아이교육
    • 토익
    • 해외연수
    • 영어
  • 취미생활
    • 음악
    • 자전거
    • 수영
    • 바이크
    • 축구
  • 기타
    • 강아지
    • 제주도여행
    • 국내여행
    • 기타일상
    • 애플
    • 휴대폰관련
  • 프로그램 개발일반
  • C언어
  • 비주얼베이직

선택알고리즘을 짜는데 논리적인 오류를 못잡겠네요.

날위해

2024.12.27

#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부분에서도 재귀호출에서 문제가 있어 값을 찾지 못하는 부분이 있습니다.
문제점과 그 해결에 대한 자세한 설명좀 부탁드립니다.

신청하기





COMMENT

댓글을 입력해주세요. 비속어와 욕설은 삼가해주세요.

번호 제 목 글쓴이 날짜
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
<<  이전  1 2 3 4 5 6 7 8 9 10  다음  >>

수다닷컴 | 여러분과 함께하는 수다토크 커뮤니티 수다닷컴에 오신것을 환영합니다.
사업자등록번호 : 117-07-92748 상호 : 진달래여행사 대표자 : 명현재 서울시 강서구 방화동 890번지 푸르지오 107동 306호
copyright 2011 게시글 삭제 및 기타 문의 : clairacademy@naver.com