Loading…

Gnome Sort, JavaScript

Initially, gnome sort was almost called stupid sort, but this awful name was assigned to another algorithm later. Nevertheless, gnome sort got quid’s worth as the author found out the name by analogy to the garden gnomes, rearranging the flower pots 🙂

 

The gnome sort algorithm is simultaneously similar to both insertion and bubble sort. The only difference from the insertion sort is that we do not use an additional variable for the current element, but drop it down like a bubble to the first element with a smaller value than the current one (for ascending sorting). This is clearly seen in the illustration:

 

 

Gnome sort visualisation

 

The sort code in JavaScript looks the following way:

 

const gnomeSort = arr => {

   const l = arr.length;

   let i = 1;

   while (i < l) {

       if (i > 0 && arr[i – 1] > arr[i]) {

           [arr[i], arr[i – 1]] = [arr[i – 1], arr[i]];

           i–;

       } else {

           i++;

       }

   }

   return arr;

};

 

Despite the fact that there is one cycle and it may seem that the complexity is O(n), in fact, the complexity of the algorithm is still O(n²), because we alternately move in two directions.

 

The work of the algorithm with a slightly lower speed can also be seen in the video:

 

 

I hope you have no questions left 🙂

 

In case you have some, feel free to provide feedback in comments.


Leave a Comment