Python Program for Gnome Sort

Last Updated : 28 Aug, 2023

In this article we are going to see Gnome Sort with Python.

Algorithm Steps:

If you are at the start of the array then go to the right element (from arr[0] to arr[1]).
If the current array element is larger or equal to the previous array element then go one step right

                   if (arr[i] >= arr[i-1])
                      i++;

If the current array element is smaller than the previous array element then swap these two elements and go one step backwards

                       if (arr[i] < arr[i-1])
                       {
                           swap(arr[i], arr[i-1]);
                           i--;
                       }

Repeat steps 2) and 3) till ‘i’ reaches the end of the array (i.e- ‘n-1’)
If the end of the array is reached then stop and the array is sorted.

Python3

# Python program to implement Gnome Sort
 
# A function to sort the given list using Gnome sort
def gnomeSort(arr, n):
    index = 0
    while index < n:
        if index == 0:
            index = index + 1
        if arr[index] >= arr[index - 1]:
            index = index + 1
        else:
            arr[index], arr[index - 1] = arr[index - 1], arr[index]
            index = index - 1
 
    return arr
 
# Driver Code
arr = [34, 2, 10, -9]
n = len(arr)
 
arr = gnomeSort(arr, n)
print("Sorted sequence after applying Gnome Sort:", end=" ")
for i in arr:
    print(i, end=" ")
 
# Contributed By Harshit Agrawal

Output

Sorted sequence after applying Gnome Sort : -9 2 10 34

Time Complexity: O(n²)

Auxiliary Space: O(1)
Please refer complete article on Gnome Sort for more details!

GeeksforGeeks

Improve

Previous Article

Python Program for Odd-Even Sort / Brick Sort

Python Program for Cocktail Sort

Similar Reads

Python Program for Odd-Even Sort / Brick Sort

This is basically a variation of bubble-sort. This algorithm is divided into two phases- Odd and Even Phase. The algorithm runs until the array elements are sorted and in each iteration two phases occurs- Odd and Even Phases. In the odd phase, we perform a bubble sort on odd indexed elements and in the even phase, we perform a bubble sort on even i

Sort a Dictionary Without Using Sort Function in Python

As we all know Dictionaries in Python are unordered by default, which means they can’t be sorted directly. However, we can sort the keys or values of a dictionary and create a new sorted dictionary from the sorted keys or values. We can sort a list in a Dictionary using the inbuilt dictionary sort() function. But in this article, we will learn how

Python program to Sort a List of Tuples in Increasing Order by the Last Element in Each Tuple

The task is to write a Python Program to sort a list of tuples in increasing order by the last element in each tuple. Input: [(1, 3), (3, 2), (2, 1)] Output: [(2, 1), (3, 2), (1, 3)] Explanation: sort tuple based on the last digit of each tuple. Methods #1: Using sorted(). Sorted() method sorts a list and always returns a list with the elements in

Python Program for Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array. Python Program for Selection SortThe provided Python code demonstrates the Selection Sort algorithm. Selection Sort has a time

Python Program for Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. Python Program for Insertion SortThe insertionSort function takes an array arr as input. It first calculates the length of the array (n). If the length is 0 or 1, the function returns immediately as an array with 0 or 1 element is considered already

Python Program for Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each object in the output sequence. Python Program for Counting SortThe provided Python code demonstrates Counting Sort, a non-comp

Python Program for Radix Sort

In this article we are going to see Radix Sort with Python Radix Sort Algorithm PythonThe provided Python code implements Radix Sort, a non-comparative sorting algorithm that works by distributing elements into buckets based on their individual digits. The code defines a countingSort function, which performs counting sort based on the digit represe

Python Program for Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. C/C++ Code # Python program for counting sort # The main function that sort the given string

Python Program for Bitonic Sort

Bitonic Sequence: A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i] is Bitonic if there exists an index i where 0<=i<=n-1 such that x0 <= x1 …..<= xi and xi >= xi+1….. >= xn-1 A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty.

Python Program for Bitonic Sort

Bitonic Sequence: A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i] is Bitonic if there exists an index i where 0<=i<=n-1 such that x0 <= x1 …..<= xi and xi >= xi+1….. >= xn-1 A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty.

Article Tags :