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.add(vsc);
frame.setVisible(true);
1Modified from Wikipedia
CS 0445 — Data Structures Page 1
Lab 8: Gnome Sort
Thread.sleep(5000);
bubbleSort(data,vsc);
//gnomeSort(data,vsc);
}
Note that the method bubbleSort() requires two arguments, data which is an array of
integer to be sorted, and vsc of type VisualSortingComponent. vsc is used for sorting
visualization. To see the sorting visualization, every time you swap two values in the array,
you should call vsc.repaint(); follows by Thread.sleep(100); as shown in the method
bubbleSort() below:
public static void bubbleSort(int[] data, VisualSortingComponent vsc)
throws InterruptedException
{
int size = data.length;
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size - 1; j++)
{
if(data[j] > data[j + 1])
{
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
vsc.repaint();
Thread.sleep(100);
}
}
}
}
Your job is to develop the method gnomeSort() (marked TO DO). DO NOT modify the signature of the method gnomeSort(). To see the visualization of your Gnome Sort algorithm,
modify the last two lines in the main method as shown below:
//bubbleSort(data,vsc);
gnomeSort(data,vsc);
Test Class
There is no test class for this lab. We will test by looking at the animation.
CS 0445 (Fall 2013) — Data Structures Page 2
Lab 8: Gnome Sort
Due Date and Submission
For the due date, please check the lab in the CourseWeb. Submit your SortingFrame.java
to the CourseWeb under this lab by the due date. No late submission will be accepted.
CS 0445 — Data Structures Page 3
