Java Program for Gnome Sort

0 0 1 minute read

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.

Java

// Java Program to implement Gnome Sort 
 
import java.util.Arrays; 
public class GFG { 
 static void gnomeSort(int arr[], int n) 
 { 
  int index = 0; 
 
  while (index < n) { 
   if (index == 0) 
    index++; 
   if (arr[index] >= arr[index - 1]) 
    index++; 
   else { 
    int temp = 0; 
    temp = arr[index]; 
    arr[index] = arr[index - 1]; 
    arr[index - 1] = temp; 
    index--; 
   } 
  } 
  return; 
 } 
 
 // Driver program to test above functions. 
 public static void main(String[] args) 
 { 
  int arr[] = { 34, 2, 10, -9 }; 
 
  gnomeSort(arr, arr.length); 
 
  System.out.print("Sorted sequence after applying Gnome sort: "); 
  System.out.println(Arrays.toString(arr)); 
 } 
} 
 
// Code Contributed by Mohit Gupta_OMG 

Output:

Sorted sequence after applying Gnome sort: [-9, 2, 10, 34]

Time Complexity: O(n²). As there is no nested loop (only one while) it may seem that this is a linear O(n) time algorithm. But the time complexity is O(n^2) as the variable ‘index’ in the program doesn’t always get incremented, it gets decremented too.
Auxiliary Space: O(n)

For understanding of Arrays.toString(), Please refer : https://www.zambiatek.com/arrays-tostring-in-java-with-examples/ Please refer complete article on Gnome Sort for more details!

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!