/* code from cpl 6.6 * changes: renames and sorts the input using the pattern */ void ADDTYPE(heapSort)(int n, MIDAS_TYPE self[], int sort_pattern[]) { int i; int reverse = 0; if (n == 0) return; /* by zero indexing, but contents are by one, added later */ for (i = 0; i < n; i++) { sort_pattern[i] = i; } /* * Heap sort */ for (i = n / 2 - 1; i >= 0; i--) { int done = 0; int root = i; int bottom = n - 1; while ((root*2 + 1 <= bottom) && (!done)) { int child = root*2 + 1; if (child+1 <= bottom) { if ((!reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child]], self[sort_pattern[child + 1]])) || (reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child + 1]], self[sort_pattern[child]])) ) { child += 1; } } if ((!reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[root]], self[sort_pattern[child]])) || (reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child]], self[sort_pattern[root]])) ) { MIDAS_INT_SWAP(sort_pattern[root], sort_pattern[child]); root = child; } else { done = 1; } } } for (i = n - 1; i >= 1; i--) { int done = 0; int root = 0; int bottom = i - 1; MIDAS_INT_SWAP(sort_pattern[0], sort_pattern[i]); while ((root*2 + 1 <= bottom) && (!done)) { int child = root*2 + 1; if (child+1 <= bottom) { if ((!reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child]], self[sort_pattern[child + 1]])) || (reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child + 1]], self[sort_pattern[child]])) ) { child += 1; } } if ((!reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[root]], self[sort_pattern[child]])) || (reverse && MIDAS_TOOLS_SORT_LT( self[sort_pattern[child]], self[sort_pattern[root]])) ) { MIDAS_INT_SWAP(sort_pattern[root], sort_pattern[child]); root = child; } else { done = 1; } } } /* sort data array */ MIDAS_TYPE * nself = malloc(sizeof(*nself) * n); memcpy(nself, self, sizeof(*nself) * n); for (i = 0; i < n; i++) { self[i] = nself[sort_pattern[i]]; } free(nself); /* change pattern content to by one indexing */ for (i = 0; i < n; i++) { sort_pattern[i] += 1; } return; }