
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort




 This page uses content from Wikipedia. The original article was at Stooge sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Task

Show the   Stooge Sort   for an array of integers.



The Stooge Sort algorithm is as follows:

algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t := (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L



       >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. stooge-sort-test.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01  Arr-Len                             CONSTANT 7.
 
01  arr-area                            VALUE "00004001000020000005000230000000000".
    03  arr-elt                         PIC 9(5) OCCURS Arr-Len TIMES
                                        INDEXED BY arr-idx.
 
PROCEDURE DIVISION.
    DISPLAY "Unsorted: " NO ADVANCING
    PERFORM VARYING arr-idx FROM 1 BY 1 UNTIL Arr-Len < arr-idx
        DISPLAY arr-elt (arr-idx) " " NO ADVANCING
    END-PERFORM
    DISPLAY SPACE
 
    CALL "stooge-sort" USING arr-area, OMITTED, OMITTED
 
    DISPLAY "Sorted:   " NO ADVANCING
    PERFORM VARYING arr-idx FROM 1 BY 1 UNTIL Arr-Len < arr-idx
        DISPLAY arr-elt (arr-idx) " " NO ADVANCING
    END-PERFORM
    DISPLAY SPACE
    .
END PROGRAM stooge-sort-test.
 
 
IDENTIFICATION DIVISION.
PROGRAM-ID. stooge-sort RECURSIVE.
 
DATA DIVISION.
LOCAL-STORAGE SECTION.
01  Arr-Len                             CONSTANT 7.
 
01  i                                   PIC 99 COMP.
01  j                                   PIC 99 COMP.
 
01  temp                                PIC 9(5).
 
01  t                                   PIC 99 COMP.
 
LINKAGE SECTION.
01  arr-area.
    03  arr-elt                         PIC 9(5) OCCURS Arr-Len TIMES.
 
01  i-val                               PIC 99 COMP.
01  j-val                               PIC 99 COMP.
 
PROCEDURE DIVISION USING arr-area, OPTIONAL i-val, OPTIONAL j-val.
    IF i-val IS OMITTED
        MOVE 1 TO i
    ELSE
        MOVE i-val TO i
    END-IF
    IF j-val IS OMITTED
        MOVE Arr-Len TO j
    ELSE
        MOVE j-val TO j
    END-IF
 
    IF arr-elt (j) < arr-elt (i)
        MOVE arr-elt (i) TO temp
        MOVE arr-elt (j) TO arr-elt (i)
        MOVE temp TO arr-elt (j)
    END-IF   
 
    IF j - i + 1 >= 3
        COMPUTE t = (j - i + 1) / 3
        SUBTRACT t FROM j
        CALL "stooge-sort" USING arr-area, CONTENT i, j
        ADD t TO i, j
        CALL "stooge-sort" USING arr-area, CONTENT i, j
        SUBTRACT t FROM i, j
        CALL "stooge-sort" USING arr-area, CONTENT i, j
    END-IF
    .
END PROGRAM stooge-sort.