Bubble Sort Exercises in Java

Modified on Friday, 25-Jan-2002 12:12:12 MST.

This set of exercises builds skills in creating and calling static methods, reusing static methods, working with int arrays, getting time values, and solving a real programming problem in Java.

Exercise 1

Make a program to print out an array of integers. The printing should be in its own method that takes an int[] as an argument. Remember, array indices start counting at 0! Here is an example of what the main() function should look like:

public static void main(String[] args)
{
  int[] values = {25, -3, 88, 37, 53, -46, 90};
  print(values);
}

Exercise 2

Write a method that takes an int[] and two integers that represent items in that array, and swaps the values at those indices. The main method should look something like this:

public static void main(String[] args)
{
  int[] values = {25, -3, 88, 37, 53, -46, 90};
  swap(values, 1, 5);
  print(values);
}

Exercise 3

Expand the program from Exercise 2 to include a method that performs a bubble sort. A list is sorted when a[i] < a[i+1] for the entire list. The method should take an int[] as an argument, and sort it. The swap() method written in Exercise 2 should be useful! The main() method should simply look like:

public static void main(String[] args)
{
  int[] values = {25, -3, 88, 37, 53, -46, 90};
  bubbleSort(values);
  print(values);
}

A bubble sort works by iteratively comparing neighboring pairs (a[i] and a[i+1]) and swapping them as needed to enforce a less-than relationship from beginning (left) to end (right). For example, the values at the first two indexes would be compared; if the first one is higher than the second, the two are swapped. Then going on to the next two, if the first is higher than the second, they are swapped. This goes on to the end of the list. At this point, the highest value has percolated or "bubbled" up to the end of the list. This process is repeated multiple times until the list is sorted.

Exercise 4

Write a function that takes an int[] and tells whether it is sorted. Then add a check to Exercise 3 to make sure that the resulting list of integers is really sorted, and print something out if it is not sorted.

Exercise 5

Write a method that takes an integer and returns an int[] with the number of entries specified in the argument. The array should be filled with values between -10000 and 10000. The main() method should look like:

public static void main(String[] args)
{
  int[] values = allocateIntArray(8);
  bubbleSort(values);
  print(values);
}

Exercise 6

Modify the main() method from Exercise 5 to calculate the number of milliseconds the sort took.

Exercise 7

Modify the main() method from Exercise 6 to perform the sort for 0 items, 1 item, 2 items, 4 items, 8 items, etc. (multiply by two each time) up to 65536 items. Be sure to print out the times. Then use a spreadsheet program such as StarOffice or Excel to enter those numbers and plot them.

Exercise 8

Look at your algorithm for the bubble sort. It can probably be optimized in a few ways. Some things to look at include:

  1. Notice that after the first pass, the highest item is in the highest position. After the second pass, the second highest item is in the second highest position. Is there a way to avoid recomputing these values?

  2. Does the algorithm go faster if you go backwards through the numbers? What about forwards on every other pass, backwards on the inbetween passes?

Create one (or more) new method(s) (perhaps "bubblesort2", "bubblesort3", etc.), and try variations on the bubblesort algorithm. Run the test from Exercise 7 using this new bubblesort2 method to see if you get improvements.