# HeapSort

From Pickwiki

Jump to navigationJump to search# Heap Sort

The first routine creates a heap ...

* HEAP.BUILD builds a heap to take further data from. ************************************************************************ SUBROUTINE HEAP.BUILD( DATA, MAT DATARRAY, ITEMCOUNT, DELIM, SORT) * Arguments: * DATA - a delimited dynamic array of data to sort * DATARRAY - supplied by the caller - a dimensioned array large enough to hold all the data * ITEMCOUNT - returned - the number of items in the array * DELIM - the dynamic array delimiter * SORT - the sort type eg AL or DR * If DELIM is "" then it assumes that the dimensioned array has already * been set up. Note that the dimensioned array must be correctly sized * by the caller. It's okay for it to be too big, but many (all?) MV's * can't resize an array passed as an argument, so if it's too small this * subroutine can't increase its size. ************************************************************************ * load the dynamic array IF DELIM NE "" THEN MATPARSE DATARRAY FROM DATA USING DELIM SETTING ITEMCOUNT END * return -1 as an error if there's no data IF ITEMCOUNT EQ 0 THEN ITEMCOUNT = -1 RETURN END * sort out justification, and whether the sort is ascending or descending SORTORDER = UPCASE( SORT[1,1] ) JUST = UPCASE( SORT[2,1] ) * for each item, bubble it up into position FOR II = 2 TO ITEMCOUNT CURRENTITEM = II NEXTITEM = INT( CURRENTITEM * 0.5) LOOP WHILE NEXTITEM * compare with the item half-way between current and the top of the array TEST = COMPARE( DATARRAY( NEXTITEM), DATARRAY( CURRENTITEM), JUST) IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order IF TEST LE 0 THEN * terminate bubble - this item is in position NEXTITEM = 0 END ELSE * swap item and loop to see if it goes higher TEMP = DATARRAY( NEXTITEM) DATARRAY( NEXTITEM) = DATARRAY( CURRENTITEM) DATARRAY( CURRENTITEM) = TEMP CURRENTITEM = NEXTITEM NEXTITEM = INT( CURRENTITEM * 0.5) END REPEAT NEXT RETURN END

The second routine returns items one by one, in sorted order

* HEAP.GETNEXT removes the next value from a heap ************************************************************************ SUBROUTINE HEAP.GETNEXT( RESULT, MAT DATARRAY, ITEMCOUNT, SORT, DEDUP) * Arguments: * RESULT - the value returned * DATARRAY - a heap created by HEAP.BUILD * ITEMCOUNT - the number of items in DATARRAY - modified by this routine * SORT - the sort type eg AL or DR * DEDUP - remove duplicates without returning them? * The calling routine needs to check ITEMCOUNT - when it gets to zero * there's nothing left to return. Don't rely on "RESULT EQ ''" because * the result could validly be null (or anything else, for that matter). ************************************************************************ IF ITEMCOUNT LE 0 THEN RETURN ;* don't do anything * sort out justification, and whether the sort is ascending or descending SORTORDER = UPCASE( SORT[1,1] ) JUST = UPCASE( SORT[2,1] ) * save the top entry as the result to be returned RESULT = DATARRAY( 1) CURRENTPOS = 1 * bubble the lower values up LOOP WHILE CURRENTPOS LT ITEMCOUNT NEXTPOS = CURRENTPOS * 2 IF NEXTPOS GE ITEMCOUNT THEN * next test position is off the end of the array (or is the last item) DATARRAY(CURRENTPOS) = DATARRAY(ITEMCOUNT) IF NEXTPOS NE ITEMCOUNT THEN * this bit is necessary because we shrink the array every time. It's not * necessary in a standard heap sort, but because we're moving the bottom * element to some place at "random" in the array, we need to make sure it * is correctly placed again in the heap. So just bubble this item up the * heap like when we built it in the first place. PREVPOS = INT( CURRENTPOS * 0.5) LOOP WHILE PREVPOS TEST = COMPARE( DATARRAY( PREVPOS), DATARRAY( CURRENTPOS), JUST) IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order IF TEST LE 0 THEN PREVPOS = 0 ELSE TEMP = DATARRAY( PREVPOS) DATARRAY( PREVPOS) = DATARRAY( CURRENTPOS) DATARRAY( CURRENTPOS) = TEMP END REPEAT END CURRENTPOS = ITEMCOUNT ;* loop will terminate END ELSE * Okay, we haven't fallen off the end of the heap - compare next two * items. Whichever is smallest, move up to replace current entry, then * loop to replace the item we've just moved up. TEST = COMPARE( DATARRAY( NEXTPOS), DATARRAY( NEXTPOS+1), JUST) IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order IF TEST LT 0 THEN DATARRAY(CURRENTPOS) = DATARRAY(NEXTPOS) CURRENTPOS = NEXTPOS END ELSE DATARRAY(CURRENTPOS) = DATARRAY(NEXTPOS+1) CURRENTPOS = NEXTPOS+1 END END REPEAT ITEMCOUNT -= 1 IF DEDUP THEN * if top entry in heap is identical to current result, then call self to * throw it away. ITEMCOUNT test is needed because the first test will * always be true on the last entry. LOOP WHILE RESULT EQ DATARRAY( 1) AND ITEMCOUNT GT 0 CALL *HEAP.GETNEXT( JUNK, MAT DATARRAY, ITEMCOUNT, SORT, 0) REPEAT END RETURN END

These two routines could easily be combined into a proper sort routine.