Suggestions on improving Sorting Algorithm (Progress ABL/4GL)

Question

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 */

• Tim Kuehn: Why not use a temp-table?
• AquaAlex: Because temp-tables are over used for this. A temp table is the only way in Progress to sort data when you have more than 1 field in a record and want to maybe even sort on multiple fields. A list or array sort is basically used to sort a list of values quickly and efficiently with as little resources as possible.

Answer 1

Depending on how long strings you have to work with I really would consider sorting via TEMP-TABLE instead. On longer strings (lets say 1000 integers or more) the TEMP-TABLE sort is around twice as quick. For short strings (10 integers) quicksort is faster. Also the difference between the largest and lowest value to sort seems to impact quicksort quite a alog (but not sorting via TEMP-TABLE).

I'm really not sure that any one of those sorting algorithms really use less resources than a sort via TEMP-TABLES (especially not recursive ones) but that would need be verified.

I've tested using this code:

DEFINE TEMP-TABLE ttSort NO-UNDO
 FIELD val AS INTEGER
 INDEX id1 IS PRIMARY val .
FUNCTION funcTempTableSort RETURNS CHARACTER
 (INPUT pcList AS CHARACTER):
 EMPTY TEMP-TABLE ttSort.
 DEFINE VARIABLE i AS INTEGER NO-UNDO.
 DEFINE VARIABLE cReturn AS CHARACTER NO-UNDO.
 DO i = 1 TO NUM-ENTRIES(pcList).
 CREATE ttSort.
 ASSIGN ttSort.val = INTEGER(ENTRY(i, pcList)).
 END.
 FOR EACH ttSort NO-LOCK BY ttSort.val:
 cReturn = cReturn + STRING(ttSort.val) + ",".
 END.
 RETURN TRIM(cReturn, ",").
END FUNCTION.

• AquaAlex: +1 made it into a decimal sort, I also created a character version. But writing code to solve various algorithms are not always the same as doing something the fastest :-) It is more like solving puzzles. I am still new to Progress (7 months) and learning a lot, but I know there are some issues with temp tables in large systems using a lot of them.
• Jensd: Feel free to use code as you like of course. Note that you can use INT64 instead of DECIMAL if large numbers is what your after and not decimals. No issues with temp tables as far as I know, they have (like all things) some kind of impact on your system.

Answer 2

as a sample made the quicksort into a class and a static method:

class common.util.strings:

method public static character AddToList(input cNew as character, input cOld as character ) :
 return AddToList(cNew, cOld, ','). 
end method. 
method public static character AddToList(input cNew as character, input cOld as character, input cSep as character ) :
 if cNew = '' then return cOld. 
 if cOld = '' then return cNew. 
 return substitute('&1&2&3', cOld,cSep,cNew). 
end method. 
method public static character QuickSortListOfIntegers (input ListToSort as character):
 define variable ListLesser as character no-undo. 
 define variable ListGreater as character no-undo. 
 define variable ListMiddle as character no-undo.
 define variable Pivot as integer no-undo. 
 define variable PivotPosition as integer no-undo. 
 define variable NumEntries as integer no-undo. 
 define variable Work as integer no-undo. 
 define variable WorkVal as integer no-undo.
 assign NumEntries = num-entries(ListToSort).
 /* if 0 or 1 item in list then list is sorted */
 if NumEntries < 2 then return ListToSort.
 assign PivotPosition = integer(NumEntries / 2)
 Pivot = integer(entry(PivotPosition, ListToSort)).
 do Work = 1 to NumEntries:
 WorkVal = integer(entry(Work, ListToSort)). 
 if WorkVal < Pivot then ListLesser = AddToList(ListLesser,string(WorkVal)).
 else if WorkVal > Pivot then ListGreater = AddToList(ListGreater,string(WorkVal)).
 else if WorkVal = Pivot then ListMiddle = AddToList(ListMiddle,string(WorkVal)).
 end.
 return trim((trim(QuickSortListOfIntegers(ListLesser),",":U) + ",":U + trim(ListMiddle,",":U) + ",":U + trim(QuickSortListOfIntegers(ListGreater),",":U)),",":U).
end method. 

end class.

Als fixed a small feature when the pivot is also the smallest or largest element in the intial pass you would return a additional ,

• AquaAlex: I actually changed my quicksort to also pass in a delimiter and I am busy making a numeric quick sort version using an array (decimal) instead of a list.