gnomesort.py
#

This is an implementation of the Gnome sort algorithm in Python 


      		
    

      
        

          #
        

        
Dick Grune describes Gnome sort as follows:
Gnome Sort is based on the technique used by Dutch Garden Gnomes. Here 
is how a garden gnome sorts a line of flower pots. 

      		
      
        
def gnomesort(lst):
    pos = 0
    while True: 

      		
    

      
        

          #
        

        
Boundary conditions: if there is no previous pot, he steps forwards;

      		
      
        
        if pos == 0:
            pos += 1

      		
    

      
        

          #
        

        
if there is no pot next to him, he is done.

      		
      
        
        if pos >= len(lst):
            break

      		
    

      
        

          #
        

        
Basically, he looks at the flower pot next to him and the previous one; if
they are in the right order he steps one pot forward, 

      		
      
        
        if lst[pos] >=  lst[pos-1] :
            pos += 1

      		
    

      
        

          #
        

        
otherwise   he swaps them and steps one pot backwards. 

      		
      
        
        else:
            lst[pos-1], lst[pos]  = lst[pos], lst[pos-1] 
            pos -= 1