퀵소팅 소스에서 문제가 있는 것 같아서요.
글쓴이: yangam / 작성시간: 월, 2005/05/09 - 1:43오후
#include <stdio.h> #define SWAP(x,y,t) ((t = x), (x = y), (y = t)) void quicksort(int *list, int left, int right); void printarray(int *list, int len); int main() { int list[] = { 30, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int len = sizeof(list) / sizeof(int) - 1; printarray(list, 3); quicksort(list, 0, 3); printarray(list, 3); return 0; } void quicksort(int *list, int left, int right) { int pivot; int i, j, t; if (left < right) { pivot = list[left]; i = left + 1; j = right; do { while (list[i] < pivot) i++; while (list[j] > pivot) j--; if (i < j) SWAP(list[i], list[j], t); printf("\ti = %d, j = %d\n", i, j); } while (i < j); SWAP(list[left], list[j], t); quicksort(list, left, j-1); quicksort(list, j+1, right); } } void printarray(int *list, int len) { int i; for (i = 0; i <= len; i++) printf("%3d", list[i]); puts(""); }
while (list[i] < pivot) i++;
의도적으로 0 - 3 까지의 요소만 정렬하도록 하였습니다.
실행을 해보시면 아시겠지만, i 의 인덱스는 0 - 4 의 범위 안의
값들만 갖어야 합니다. 그런데, 그렇게 되지 않죠.
while (list[i] < pivot && i <= right) i++;
위의 소스코드처럼 i 의 범위를 지정해주어야 하는 것 아닌가요?
list[0] - list[i] 까지가 배열의 범위인데
정말 운이 없게도 배열 요소 범위의 바깥인
list[i+1], list[i+2], ..., list[i+n] 의 값들이
설정된 피봇의 값보다 작다면.. i 는 한없이 커지는 것 아닌가요?
질문이 이해가 가실지 모르겠네요;
작문 실력을 늘려야겠다는... ㅠㅠ
제가 제기한 문제에 대해서 설명이 부족하다 싶은 부분은
답글 달아주시면, 제가 리플을 달겠습니다.
의견 부탁드립니다.
참고로, 참고한 소스는 FUNDAMENTALS OF DATA STRUCTURES IN C 입니다.
(그러나, 책의 소스와는 좀 다릅니다.. 수정을 했기 때문에..)
Forums:
문제가 없는건가요;;; 제가 잘못 생각하고 있는건가요;;;
문제가 없는건가요;;; 제가 잘못 생각하고 있는건가요;;;
i<right로 범위를 지정해주는 것이 맞습니다.덤으로, j&g
i<right로 범위를 지정해주는 것이 맞습니다.
덤으로, j>left로 j의 범위도 지정해주는게 좋겠죠.
댓글 달기