This Python program implements Gnome Sort, a simple sorting algorithm that works as follows:
Gnome Sort is a simple, comparison-based sorting algorithm that is named after the way a garden gnome sorts a line of flower pots. It is not particularly efficient for large datasets, but it offers an interesting insight into the process of sorting algorithms and can be useful for educational purposes.
You are given an unsorted list of integers. Implement the Gnome Sort algorithm to sort the list in ascending order. Write a Python function
gnome_sort(arr) that takes an unsorted list
arr as input and returns the list sorted in ascending order.
Python Program to Implement Gnome Sort
def gnome_sort(arr): n = len(arr) index = 0 while index < n: if index == 0: index += 1 if arr[index] >= arr[index - 1]: index += 1 else: arr[index], arr[index - 1] = arr[index - 1], arr[index] index -= 1 return arr # Example usage input_list = [5, 2, 9, 1, 5, 6] sorted_list = gnome_sort(input_list) print("Sorted list:", sorted_list)
How it Works
- Start at the Beginning: The algorithm starts by initializing an index
iat 0, which represents the current position in the list.
- Compare Adjacent Elements: It compares the element at index
iwith the element at index
i - 1.
- Correct Order Check: If the element at index
iis greater than or equal to the element at index
i - 1, it means they are in the correct order, and the algorithm moves to the next index
i + 1.
- Swapping Elements: If the element at index
iis smaller than the element at index
i - 1, it means they are in the wrong order. The algorithm swaps these two elements and then moves back one step by decrementing
i = i - 1).
- Repeat or Move Forward: Now, the algorithm repeats steps 2-4 for the new value of
i. This process continues until the element at index
iis in the correct position relative to the previous element.
- Advancing the Index: Once the element at index
iis in the correct place, the algorithm moves forward by incrementing
i = i + 1).
- End of List Check: The algorithm continues this process until it reaches the end of the list. At this point, the list is considered sorted.
- Repeat Until Sorted: The algorithm repeats these steps until the entire list is sorted. If at any point the index
ibecomes 0, the algorithm advances
iby 1 to prevent getting stuck.
This process of comparing, swapping, and moving the index back or forward continues until the entire list is sorted. Essentially, Gnome Sort gradually moves smaller elements towards their correct positions by repeatedly swapping adjacent pairs that are in the wrong order, and it moves the index back and forth to ensure proper sorting.
However, Gnome Sort’s efficiency is limited due to its worst-case and average-case time complexity of O(n^2), making it less practical for large datasets compared to more efficient sorting algorithms like Quick Sort or Merge Sort. It’s mainly used for educational purposes or for understanding the basic concepts of sorting algorithms.