# Lab 8: Gnome Sort solution

\$19.99

Original Work ?

## Description

Introduction to Gnome Sort1
Gnome sort is a sorting algorithm which is similar to insertion sort, except that moving
an element to its proper place is accomplished by a series of swaps, as in bubble sort. It
is conceptually simple, requiring no nested loops. The running time is O(n
2
), but tends
towards O(n) if the list is initially almost sorted. In practice the algorithm can run as fast
as insertion sort. The average runtime is O(n
2
).
The algorithm always finds the first place where two adjacent elements are in the wrong
order, and swaps them. It takes advantage of the fact that performing a swap can introduce
a new out-of-order adjacent pair only right before or after the two swapped elements. It
does not assume that elements forward of the current position are sorted, so it only needs
to check the position directly before the swapped elements.
Simply speaking, first we compare the first pair (let’s call them left elemenet and right
element), if the left element is less than or equal to the right element, move on the the next
pair. If the left element of a pair is greater than the right element, we swap them. But after
we swap, nothing guarantee that the previous pair is in order. So, we have to move back to
the previous pair and perform the same process all over again.
What to Do?
For this lab, you are going to implement the Gnome Sort algorithm to sort arrays of integers
with visualizations. First, simply run SortingFrame.java and you will see a visualization of
a sorting algorithm called Bubble sort. The main method of SortingFrame.java is shown
below:
public static void main(String[] args) throws InterruptedException
{
JFrame frame = new JFrame();
int[] data = randomIntArray(40);
VisualSortingComponent vsc = new VisualSortingComponent(data);
frame.setTitle(“Sorting Visualization”);
frame.setSize(500,500);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
1Modified from Wikipedia
CS 0445 (Fall 2013) — Data Structures Page 1
Lab 8: Gnome Sort