Dwarf Sort

Illustration of the action of the gnome sorting algorithm

Gnome sort is a sorting algorithm similar to sorting by inserts , but unlike the latter, a series of exchanges take place before inserting to the desired place, as in bubble sorting . The name comes from the alleged behavior of garden gnomes when sorting the line of garden pots.

Dwarf sorting is based on the technique used by the usual Dutch garden gnome ( Dutch tuinkabouter ). This is the way a garden gnome sorts a line of flower pots. Essentially, he looks at the current and previous garden pots: if they are in the correct order, he steps forward one pot, otherwise he swaps them and steps back one pot. Boundary conditions: if there is no previous pot, he steps forward; if there is no next pot, he is done.
Dick grun

The algorithm is conceptually simple, does not require nested loops. Working hours $O\left(n^{2}\right)$ ${\ displaystyle O \ left (n ^ {2} \ right)}$ $O \ left (n ^ {2} \ right)$ . In practice, an algorithm can work as fast as insert sorting.

The algorithm finds the first place where two adjacent elements are in the wrong order and swaps them. He takes advantage of the fact that an exchange can spawn a new pair, standing in the wrong order, only before or after rearranged elements. He does not allow that the elements after the current position are sorted, so you only need to check the position before the rearranged elements.

Description

The pseudo sort code is written below. This is an optimized version using the j variable to allow a jump forward to where it stopped before moving to the left, avoiding unnecessary iterations and comparisons:

  gnomeSort (a [0..size - 1])
     i = 1;
     j = 2;
     while i <size
         if a [i - 1]> a [i] // to sort ascending, change the comparison sign to <
             i = j;
             j = j + 1;
         else
             swap a [i - 1] and a [i]
             i = i - 1;
             if i == 0
                 i = j;
                 j = j + 1;

Example:

If we want to sort an array with elements [4] [2] [7] [3] from larger to smaller, then at the iterations of the while loop the following will happen:

[4] [2] [7] [3] (initial state: i == 1, j == 2);
[4] [2] [7] [3] (nothing happened, but now i == 2, j == 3);
[4] [7] [2] [3] (exchange a [2] and a [1], now i == 1, and j == 3 as before);
[7] [4] [2] [3] (exchange a [1] and a [0], now i == 3, j == 4);
[7] [4] [3] [2] (exchange a [3] and a [2], now i == 2, j == 4);
[7] [4] [3] [2] (nothing happened, but now i == 4, j == 5);
the cycle is over, because i is not <4.

C ++ Implementation

  template < class T >
 void gnome_sort ( T A [], std :: size_t N )
 {
     for ( std :: size_t i = 0 ; i + 1 < N ; ++ i ) if ( A [ i ] > A [ i + 1 ])
         {
             std :: swap ( A [ i ], A [ i + 1 ]);
             if ( i ! = 0 ) i - = 2 ;  // two are subtracted and then one is added
         }
 }

Java Implementation

  1 void gnomeSort ( int [] a )
 2 {
 3 int i = 1 , tmp ;
 4 while ( i < a . Length ) if ( i == 0 || a [ i - 1 ] <= a [ i ]) i ++;
 5 else
 6 {
 7 tmp = a [ i ];  a [ i ] = a [ i - 1 ];  a [ i - 1 ] = tmp ;
 8 i -;
 9 }
 10 }

Python implementation

  def gnome_sort ( arr ):
     i = 1
     while i < len ( arr ):
         if not i or arr [ i - 1 ] <= arr [ i ]:
             i + = 1
         else :
             arr [ i ], arr [ i - 1 ] = arr [ i - 1 ], arr [ i ]
             i - = 1
     return arr

Optimization

As a result of optimization, the gnome sorting naturally transforms into sorting by inserts . Each time, the “gnome” runs into a new number, all the values to the left of the “gnome” are already sorted.

Links

Description of the method and listing of the gnome sorting programs.