1
\$\begingroup\$

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 */
\$\endgroup\$
  • \$\begingroup\$ Why not use a temp-table? \$\endgroup\$ – Tim Kuehn May 31 '13 at 19:55
  • \$\begingroup\$ 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. \$\endgroup\$ – AquaAlex Jun 5 '13 at 7:16
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ +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. \$\endgroup\$ – AquaAlex Nov 14 '13 at 18:32
  • \$\begingroup\$ 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. \$\endgroup\$ – Jensd Nov 14 '13 at 21:37
2
\$\begingroup\$

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 ,

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – AquaAlex Nov 14 '13 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.