I have written some sort routines for PROGRESS 4GL/ABL and wanting to get some input whether these sorts can be improved. And whether my sorts are true to name. And I would also be very interested in any suggestions how to change the Quick sort to do a proper numeric sort as well. The combsort was easy enough to write for ASCII sort and to make a version to do numeric sorts.
I found the Comb sort to be about 3 - 5 times faster than Bubble Sort and the Quick Sort to be about 7 - 9 times faster than the bubble sort. The Numeric Comb sort is a bit slower than the normal comb sort, due to having to convert data from string to integer and placing it in an array and then converting back to string list.
All the Sort functions receive a comma delimited list of data and returns data in same way after sort.
I have found CombSort to be
funcFloor - basically a function to return Floor funcCeiling - basically a function to return Ceiling
/============================================================/
FUNCTION funcBubbleSort RETURNS CHARACTER
(INPUT pcList AS CHARACTER):
DEFINE VARIABLE cTempValue AS CHARACTER NO-UNDO. /* holding place for swap */
DEFINE VARIABLE i AS INTEGER NO-UNDO. /* outer loop counter */
DEFINE VARIABLE j AS INTEGER NO-UNDO. /* inner loop counter */
/* if 0 or 1 item in list then list is sorted */
IF NUM-ENTRIES(pcList) < 2 THEN
RETURN pcList.
DO i = NUM-ENTRIES(pcList) TO 1 BY -1:
DO j = 1 TO i - 1:
IF ENTRY(j, pcList) > ENTRY(j + 1, pcList) THEN
DO:
cTempValue = ENTRY(j, pcList).
ENTRY(j, pcList) = ENTRY(j + 1, pcList).
ENTRY(j + 1, pcList) = cTempValue.
END.
END.
END.
RETURN TRIM(pcList,",").
END FUNCTION.
/* ======================================================== */
FUNCTION funcCombSort RETURNS CHARACTER
(INPUT pcList AS CHARACTER):
DEFINE VARIABLE cTempValue AS CHARACTER NO-UNDO.
DEFINE VARIABLE dShrink AS DECIMAL NO-UNDO.
DEFINE VARIABLE iNumEntries AS INTEGER NO-UNDO.
DEFINE VARIABLE iGap AS INTEGER NO-UNDO.
DEFINE VARIABLE i AS INTEGER NO-UNDO.
DEFINE VARIABLE lSwapped AS LOGICAL NO-UNDO.
/* if 0 or 1 item in list then list is sorted */
IF NUM-ENTRIES(pcList) < 2 THEN
RETURN pcList.
/* be careful with dShrink size
too large and too small are both bad
*/
ASSIGN
dShrink = 1.3
iNumEntries = NUM-ENTRIES(pcList)
iGap = iNumEntries
lSwapped = TRUE
.
DO WHILE lSwapped = TRUE OR iGap > 1 :
/*update the gap value for a next comb.*/
ASSIGN
iGap = funcFloor(iGap / dShrink)
i = 1
lSwapped = FALSE.
IF iGap < 1 THEN
iGap = 1. /*minimum gap is 1 */
/* a single "comb" over the input list */
DO WHILE (i + iGap) <= iNumEntries:
IF ENTRY(i, pcList) > ENTRY((i + iGap), pcList) THEN
DO:
ASSIGN
cTempValue = ENTRY(i, pcList)
ENTRY(i, pcList) = ENTRY((i + igap), pcList)
ENTRY((i + iGap), pcList) = cTempValue
lSwapped = TRUE /* Flag a swap has occurred */
.
END.
i = i + 1.
END.
END.
RETURN TRIM(pcList, ",").
END FUNCTION.
/* ==================================================== */
FUNCTION funcNumCombSort RETURNS CHARACTER
(INPUT pcList AS CHARACTER):
DEFINE VARIABLE iTempValue AS INTEGER NO-UNDO.
DEFINE VARIABLE dShrink AS DECIMAL NO-UNDO.
DEFINE VARIABLE iNumEntries AS INTEGER NO-UNDO.
DEFINE VARIABLE iGap AS INTEGER NO-UNDO.
DEFINE VARIABLE i AS INTEGER NO-UNDO.
DEFINE VARIABLE lSwapped AS LOGICAL NO-UNDO.
DEFINE VARIABLE iArray AS INTEGER NO-UNDO EXTENT.
DEFINE VARIABLE cList AS CHARACTER NO-UNDO.
/* if 0 or 1 item in list then list is sorted */
IF NUM-ENTRIES(pcList) < 2 THEN
RETURN pcList.
EXTENT (iArray) = NUM-ENTRIES(pcList).
/* be careful with dShrink size
too large and too small are both bad
*/
ASSIGN
dShrink = 1.3
iNumEntries = NUM-ENTRIES(pcList)
iGap = iNumEntries
lSwapped = TRUE.
/* populate array from list */
DO i = iNumEntries TO 1 BY -1:
iArray[i] = INTEGER(ENTRY(i,pcList)).
END.
DO WHILE lSwapped = TRUE OR iGap > 1 :
/*update the gap value for a next comb.*/
ASSIGN
iGap = funcFloor(iGap / dShrink)
i = 1
lSwapped = FALSE.
IF iGap < 1 THEN
iGap = 1. /*minimum gap is 1 */
/* a single "comb" over the input list - reverse order */
DO WHILE (i + iGap) <= iNumEntries:
IF iArray[i] < iArray[i + iGap] THEN
DO:
ASSIGN
iTempValue = iArray[i] /* swap two values */
iArray[i] = iArray[i + iGap]
iArray[i + iGap] = iTempValue
lSwapped = TRUE. /* Flag a swap has occurred */
END.
i = i + 1.
END.
END.
iNumEntries = EXTENT(iArray).
DO i = iNumEntries TO 1 BY -1:
IF cList = "" THEN
cList = STRING(iArray[i]).
ELSE
cList = cList + "," + STRING(iArray[i]).
END.
RETURN cList.
END FUNCTION.
/* =============================================================== */
FUNCTION funcQuickSort RETURNS CHARACTER
(INPUT pcList AS character):
DEFINE VARIABLE cListLess AS CHARACTER NO-UNDO.
DEFINE VARIABLE cListGreater AS CHARACTER NO-UNDO.
DEFINE VARIABLE cListMiddel AS CHARACTER NO-UNDO.
DEFINE VARIABLE cPivot AS CHARACTER NO-UNDO.
DEFINE VARIABLE iPivotPosition AS INTEGER NO-UNDO.
DEFINE VARIABLE iNumEntries AS INTEGER NO-UNDO.
DEFINE VARIABLE i AS INTEGER NO-UNDO.
/* if 0 or 1 item in list then list is sorted */
IF NUM-ENTRIES(pcList) < 2 THEN
RETURN pcList.
ASSIGN
iNumEntries = NUM-ENTRIES(pcList)
iPivotPosition = INTEGER (iNumEntries / 2)
cPivot = ENTRY(iPivotPosition, pcList).
DO i = 1 TO iNumEntries:
IF ENTRY(i, pcList) < cPivot THEN
IF cListLess = "" THEN
cListless = ENTRY(i, pcList).
ELSE
cListLess = cListLess + "," + ENTRY(i, pcList).
IF ENTRY(i, pcList) > cPivot THEN
IF cListGreater = "" THEN
cListGreater = ENTRY(i, pcList).
ELSE
cListGreater = cListGreater + "," + ENTRY(i, pcList).
IF ENTRY(i, pcList) = cPivot THEN
IF cListMiddel = "" THEN
cListMiddel = ENTRY(i, pcList).
ELSE
cListMiddel = cListMiddel + "," + ENTRY(i, pcList).
END.
RETURN (TRIM(funcQuickSort(cListLess),",") + "," + cListMiddel + "," +
TRIM(funcQuickSort(cListGreater),",")).
END FUNCTION. /* funcQuickSort */
