/*----------------------------------------------------------------------*/ /* QUICKSORT */ /* Adapted by J. Teuhola from G. H. Gonnet & */ /* R. Baeza-Yates: Handbook of Algorithms and Data Structures, */ /* 2nd Edition, Addison-Wesley Publishing Company, 1991. */ /*----------------------------------------------------------------------*/ #ifndef element #define element float #endif #define limit 15 /*----------------------------------------------------------------------*/ /* The following procedure sorts the subvector r[lo..up] by repeated */ /* partitioning, using r[lo] as pivot. The left partition is sorted */ /* recursively and the right part iteratively. Subvectors smaller than */ /* limit are sorted later by insertion sort. */ /*----------------------------------------------------------------------*/ static void q_sort(r, lo, up) element r[]; int lo, up; { int i, j; element pivot; while (up >= (lo+limit)) { i = lo; j = up; pivot = r[lo]; while (i pivot) j--; r[i] = r[j]; while ((i aux; j--) r[j+1] = r[j]; r[j+1] = aux; } } /* End of i_sort */ /*----------------------------------------------------------------------*/ /* Gather up the sort procedure by using the above tools. */ /*----------------------------------------------------------------------*/ void quicksort(r, n) element r[]; int n; { q_sort(r, 0, n-1); i_sort_after_q_sort(r, n); } /* End of quicksort */