Gnome Sort
Logic of this sorting algo same as insertion sort, array at left hand of current position during sorting
is sorted and if element at current position violating sorted order then swap it with
next element on left side and keep on doing till it reaches its correct place.
In insertion sort we use two loops, but here with simple trick we avoided inner loop.
Here this single loop increments and decrements “i” based on the current element is in expected
order or not, and achieves same functionality and behavior as insertion sort.
Cons: In insertion sort after putting current element at proper place in left side sorted array outer
loop start from where it left, but in gnome there is only one iteration variable so it has to increment
i as many times as it decreased to come back again at position from where i started decreasing.
Pros: Less number of line, easy to remember and easy to write.
So complexity is also same as insertion sort: best case O(n) Worst case: O(n^2).
public class Main {
1 public static void gnomeSort(int[] arr) {
2 for (int i = 1; i < arr.length; ) {
3 if (0 == i || arr[i - 1] <= arr[i]) { //in expected order.
4 i++;
5 } else {
6 //swap
7 int temp = arr[i - 1];
8 arr[i - 1] = arr[i];
9 arr[i] = temp;
10 i--;
11 }
12 }
13 }
public static void main(String[] args) {
int[] arr = {4, 6, 3, 7, 89, 2, 4, 12, 34, 90, 100, -1, 0};
gnomeSort(arr);
for (int x : arr) {
System.out.print(" " + x);
}
}
}
Output:
-1 0 2 3 4 4 6 7 12 34 89 90 100
buddhaTech 