Algol 68 Genie

gnome-sort.a68

     
   1  COMMENT
   2  
   3  @section Synopsis
   4  
   5  How a garden gnome sorts a line of flower pots. 
   6  
   7  The term 'gnome sort' comes from Dick Grune, but a same algorithm was described earlier: 
   8  
   9     [1] Hamid Sarbazi-Azad, Stupid Sort: A new sorting algorithm, 
  10         Department of Computing Science Newsletter, University of Glasgow, 599:4, 
  11         2 October 2000.
  12  
  13  This variant uses the top-down stepwise-refinement technique from:
  14  
  15     [2] C.H.A. Koster, Th.A. Zoethout. 
  16         Systematisch programmeren in Algol 68, Deel 1.
  17         Kluwer, Deventer [1978]. 
  18  
  19     [3] C.H.A. Koster, H. Meijer. 
  20         Systematisch programmeren in Algol 68, Deel 2.
  21         Kluwer, Deventer [1981]
  22    
  23  At Nijmegen University, refinements were implemented at the time by a simple 
  24  preprocessor to FLACC. A68G employs a similar preprocessor.
  25  
  26  COMMENT
  27  
  28  BEGIN PROC gnome sort = (REF [] POT flower) VOID:
  29             IF more than one pot
  30             THEN start at leftmost pot;
  31                  WHILE not all pots seen
  32                  DO IF at the leftmost pot
  33                     OREL flower correctly placed
  34                     THEN proceed to pot to the right
  35                     ELSE swap pot with pot to the left;
  36                          go back to pot to the left
  37                     FI
  38                  OD
  39             FI;
  40  
  41        sort shipment of flowers 
  42  END.
  43  
  44        more than one pot:
  45           UPB flower > 1.
  46        
  47        start at leftmost pot:
  48           POT pot := 1.
  49        
  50        not all pots seen:
  51           pot <= UPB flower.
  52        
  53        at the leftmost pot:
  54           pot = 1.
  55        
  56        flower correctly placed:
  57           flower[pot] > flower[pot - 1].
  58        
  59        proceed to pot to the right:
  60           pot +:= 1.
  61        
  62        go back to pot to the left:
  63           pot -:= 1.
  64        
  65        swap pot with pot to the left:
  66           POT side = flower[pot];
  67           flower[pot] := flower[pot - 1];
  68           flower[pot - 1] := side.
  69        
  70        sort shipment of flowers:
  71           MODE POT = INT;
  72           [10] POT shipment := (4, 3, 2, 5, 1, 9, 10, 8, 6, 7);
  73           gnome sort (shipment);
  74           printf (($gl$, shipment)).