Python Program for Gnome Sort

Stupid Sort is another name for the Gnome Sort. It is named after a garden gnome's way of sorting flower pots. In this tutorial, we are going to sort the elements in an array using the gnome sort method.

Gnome Sort - Basic Introduction

This algorithm works by comparing the current thing to the preceding item, you may put the items in the correct sequence. Proceed to the following item if everything is in order (or stop if the end is reached). Swap them and go back to the preceding item if they're out of sequence. Move on to the next item if there is no preceding item.

Let us now understand the working of gnome sorting:

1. From 0 to 1, traverse the element.
2. Move one step right if the element is greater and equal to the previous element.
3. Swap the items and take a step backward if the current element is less than the preceding element.
4. Return the sorted array by repeating the preceding steps for all of the items.

Algorithm

As of now, we have a rough understanding of the Gnome sort operation. Let's have a look at the Algorithm followed by code for better understanding:

1. Create a function gnome_sort
2. Takes an array as argument
3. Initiate a loop with loop variable position that iterates from 1 to the length of the array – 1
4. Initiate a while loop while-loop that runs as long as position != 0 and array[position] and array[position – 1] are out of order
5. In the while loop, swap array[position] and array[pos – 1] and decrement position
6. The array is now sorted
7. Print the sorted array

Program for Gnome Sort

The source code for a Python program that implements Gnome sort is given below. The output of the program is displayed below. In this program, the user is asked to enter the list and after that, the sorted form of the list is prompted by the compiler:

def gnome_sort(array):
    for position in range(1, len(array)):
        while (position != 0 and array[position] < array[position - 1]):
            array[position], array[position - 1] = array[position - 1], array[position]
            position = position - 1 
 
 #driver code
array = input('Enter the numbers: ').split()
array = [int(a) for a in array]
gnome_sort(array)
print('The sorted array is: ', end='')
print(array)

Enter the numbers: 8 9 6 5 4 3 2 1
The sorted array is: [1, 2, 3, 4, 5, 6, 8, 9]

Conclusion

In this tutorial, we have performed a gnome sort operation in python to sort an array. It is a stable program having the time complexity of O(n²) and the space complexity of the gnome sort is O(1).