i trying figure out how implement quick sort without having create arrays. yet, implementation works when use 1 pivot. program seg faults when use other number. cannot figure out variable getting out of bounds cause infinite loop. appreciate criticism/help on function.
void quick_sort(item a[], int max, int pivot) { int i, j, p, t; printf("%d", pivot); if (max < 2) { return; } p = a[pivot]; printf("%d", p); (i = 0, j = max-1;; i++, j--) { while (a[i] < p) { i++; } while (p < a[j]) { j--; } if (i >= j) { break; } t = a[i]; a[i] = a[j]; a[j] = t; } quick_sort(a, i, pivot); quick_sort(a+i, max-i, pivot); }
your program segfaulting because if choose hard pivot, 2, example, if quick_sort called in partition 2 items on right of array, a[2] out of bounds.
i think best option solution choose pivot inside function, either randomly or getting arbitrary value, max/2. have sure 0 <= pivot < max:
void quick_sort(int a[], int max) { int pivot = max/2; int i, j, p, t; if (max < 2) { return; } p = a[pivot]; (i = 0, j = max-1;; i++, j--) { while (a[i] < p) { i++; } while (p < a[j]) { j--; } if (i >= j) { break; } t = a[i]; a[i] = a[j]; a[j] = t; } quick_sort(a, i); quick_sort(a+i, max-i); } 