Hello, I'm trying to sort an array of pointer to structures. The structures look like this: Code: typdef struct { double coord[3]; }vector; Here's my program. Pretty much every thing is standard as what we do in quicksort except that there is a entity called axis. axis is nothing but an index into the coord array. It can take values 0, 1, 2. MY doubt is as follows: I tried to make left, right, i, j as size_t or even unsigned long and the program abruptly terminated (it failed). Why is this happening ? Please help me out this problem has bothered me for long and has weared me out totally. Is there a flaw in my algo ? If yes, please can you suggest me a better one ? Code: void quicksort(vector **parent_vpa, long left, long right, int axis) { long i, j; vector *pivotpoint; vector *tempstore; if (left < right) { i = left; j = right; pivotpoint = parent_vpa[(left+right)/2]; while (i <= j) { while (parent_vpa[i]->coord[axis] < pivotpoint->coord[axis]) { i++; } while (parent_vpa[j]->coord[axis] > pivotpoint->coord[axis]) { j--; } if (i <= j) { tempstore = parent_vpa[i]; parent_vpa[i] = parent_vpa[j]; parent_vpa[j] = tempstore; i++; j--; } } if (left < j) { quicksort(parent_vpa, left, j, axis); } if (i < right) { quicksort(parent_vpa, i, right, axis); } } else return; }
sorry heres the code with tags: Code: void quicksort(vector **parent_vpa, long left, long right, int axis) { long i, j; vector *pivotpoint; vector *tempstore; if (left < right) { i = left; j = right; pivotpoint = parent_vpa[(left+right)/2]; while (i <= j) { while (parent_vpa[i]->coord[axis] < pivotpoint->coord[axis]) { i++; } while (parent_vpa[j]->coord[axis] > pivotpoint->coord[axis]) { j--; } if (i <= j) { tempstore = parent_vpa[i]; parent_vpa[i] = parent_vpa[j]; parent_vpa[j] = tempstore; i++; j--; } } if (left < j) { quicksort(parent_vpa, left, j, axis); } if (i < right) { quicksort(parent_vpa, i, right, axis); } } else return; }
Why don't try this code? Code: void QuickSort(int start, int end, int arr[]) { if (start >= end) return; int p = (start + end) / 2; int i = start; int j = end; while (i<j) { while(arr[i]<arr[p] && i<p) i++; while(arr[j]>arr[p] && j>p) j--; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; if (p == j ) { p = i; j--; } else if (p==i) { p = j; i++; } else { i++; j--; } } QuickSort(start, p-1, arr); QuickSort(p+1, end, arr); }