sorting

Gnome Sort is a simple comparison-based sorting algorithm, often considered inefficient for large datasets. It is similar to insertion sort but with a different approach to moving elements into their correct positions. Here’s how it works:

Steps:

1. Start with the first element of the array.

2. Compare the current element with the previous one.

   • If they are in order (current element ≥ previous element), move forward by one step.

   • If they are not in order (current element < previous element), swap them and move one step backward.

3. Repeat this process until the entire array is sorted.

It’s called “Gnome Sort” because it behaves like a gnome walking through a garden and fixing problems (swapping) as it goes along, stepping forward and backward.

---

• Gnome Sort aka stupid sort is a simple comparison-based sorting algorithm.
• It’s similar to insertion sort but with a different approach.
• It’s inefficient for large datasets.
• popularized in 2000 by iranian CS prof Hamid SarbAzi-Azad

Steps:

1. Start with the first element of the array.
2. Compare the current element with the previous one.
   • If the current element ≥ previous element, move forward by one step.
   • If the current element < previous element, swap them and move one step backward.
3. Repeat the process until the entire array is sorted.

• Named “Gnome Sort” because it behaves like a gnome walking through a garden and fixing problems (swapping) as it goes along, stepping forward and backward.

psudocode

procedure gnomeSort(a[]):
   pos := 0
   while pos < length(a):
       if (pos == 0 or a[pos] >= a[pos-1]):
           pos := pos + 1
       else
           swap a[pos] and a[pos-1]
           pos := pos - 1