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

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 */
• Why not use a temp-table? May 31, 2013 at 19:55
• 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. Jun 5, 2013 at 7:16

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.
• +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. Nov 14, 2013 at 18:32
• 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. Nov 14, 2013 at 21:37

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 ) :
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 ,

• 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. Nov 14, 2013 at 18:02