Question

GETTING STARTED

Create an Eclipse Java project containing package “bubble”. Import the 3 starter files BubbleSorter.java, BubbleSortTestCaseMaker.java, and Statistician.java.

PART 1: Implementing BubbleSorter

Implement a very simple BubbleSorter class that records how many array visits and how many swaps are performed. Look at the starter file before reading on.

This class has an instance variable called “a”. Its type is int[]. This is the array that will be bubble-sorted in place. Usually a single letter is a bad variable name, especially for an instance variable. But in literature about sorting algorithms it’s common to use “a” for an array that will be sorted.

In the sort() method, the outer loop should execute n times, where n is the length of the array. The inner loop should compare all adjacent pairs of elements, starting with a[n-1] vs. a[n-2], and ending with a[1] vs. a[0]. If comparison determines that the elements should be swapped, the inner loop should do the swap and increment nSwaps. Whether or not the elements are swapped, the inner loop should increment nVisits by 2. Note that this isn’t the most efficient way to control the loops, but it’s simple so it’s ok for now.

Complete the isSorted() method, which you can later use to test your code. After you sort an array, analyze it with isSorted() to make sure it’s really sorted. Before testing, look at BubbleSortTestCaseMaker.java. It provides 4 methods that return test case arrays. The first 3 methods are obvious. The last method builds an array containing random ints; its contents will be different every time the method is called.

Test your BubbleSorter code in main(). The starter file sorts a tiny test array. When that works, replace getTiny() with getAlreadySorted(), then with getBackward(). For each case, record the number of visits and swaps; you’ll need them later.

When your first 3 test cases are correctly sorted, test several times with a larger input array, returned by BubbleSortTestCaseMaker.buildRandom(100, 1000). Caution: this method returns a different random array every time it is called. Large random test cases are good for increasing confidence that an algorithm is correct, but they are difficult to debug because of their size and because they aren’t repeatable. So it’s good practice to start with simple test cases that make debugging easy, then move on to bigger cases after you have fixed all the bugs you can find with simple cases. Run the test 3 times, and record the number of visits and swaps for both runs.

Make a table like the following, and enter the counts that you observed.

Test case	Number of visits	Number of swaps
Tiny
Already sorted
Backward
Random #1
Random #2
Random #3

PART 2: BubbleSorter complexity

Complete the Statistician class, and use it to do experiments on your bubble sorter to determine if its complexity is O(n²). You can't draw valid conclusions from a single observation, or from a small number of observations. You need to execute a statistically large number of times, so that your conclusions have statistical strength. For this lab, an experiment will be 1000 executions. Define a private final static int called N_REPETITIONS, whose value is 1000.

The getStats() method of the Statistician class has an arg for specifying an array length. In that method’s loop, a random array of the specified length is created. Then a BubbleSorter sorts the array. Replace the “Assert …” comment line with a line that asserts that the sorter has correctly sorted. Paste that line into your report. Remember to configure Eclipse to run with assertions enabled (Run -> Run Configurations, then “Arguments tab” and type “-ea” into VM Arguments). If an assertion error is ever thrown, go back and fix your sorter. After the assertion line, replace the next comment with lines that retrieve the number of visits and swaps from the sorter, and store those numbers in the appropriate array lists.

After the loop in getStats(), write code that analyzes the 2 array lists, and prints the minimum, average, and maximum observed number of visits and number of swaps. Think about the benefit of creating a helper method that computes and prints min/avg/max for any array list of longs. Did you use a helper method?

Before running the statistician, think about what you expect to see. You haven’t been told the complexity of the bubble sort algorithm, but for now suppose that for an input array of length n, both the number of visits and the number of swaps are O(n²). If sorting an array of length=1000 requires v visits and s swaps, approximately how many visits and swaps are required to sort an array of length=3000?

In main(), the starter code calls getStats() for array lengths 1000 and 3000. Run main(). If it takes more than 2-3 minutes, try with shorter array lengths (e.g. 500 and 1500); the second length should be 3x the first length. Paste your output into your report. Does the output support the hypothesis that bubble sort is O(n²)?

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

package bubble;

public class BubbleSorter
{
   private int[]       a;
   private long       nVisits;
   private long       nSwaps;
  
  
   public BubbleSorter(int[] a)
   {
       this.a = a;
   }
  
  
   public void sort()
   {
       for (/* control the outer loop */)
       {
           for (/* control the inner loop */)
           {
               // Increment number of visits by 2.
               if (/* if 2 elements you're visiting need to be swapped */)
               {
                   // Swap the elements and increment nSwaps.
               }
           }
       }
   }
  
  
   public String toString()
   {
       String s = nVisits + " visits, " + nSwaps + " swaps\n{";
       for (int n: a)
           s += " " + n;
       s += " }";
       return s;
   }
  
  
   public boolean isSorted()
   {
       /* Implement this */
   }
  
  
   public long getNVisits()
   {
       /* Implement this */
   }
  
  
   public long getNSwaps()
   {
       /* Implement this */
   }
  
  
   public int[] getArray()
   {
       return a;
   }
  
  
   public static void main(String[] args)
   {
       int[] a = BubbleSortTestCaseMaker.getTiny();
      
       BubbleSorter sorter = new BubbleSorter(a);
       sorter.sort();
       System.out.println(sorter);
       System.out.println(sorter.isSorted() ? "SORTED" : "NOT SORTED");
   }
}
---------------------------------------------------------------------------------------------------------

package bubble;

import java.util.*;

public class Statistician
{
   private static void getStats(int arrayLength)
   {
       ArrayList<Long> visitCounts = new ArrayList<>();
       ArrayList<Long> swapCounts = new ArrayList<>();
      
       for (int i=0; i<N_REPETITIONS; i++)
       {
           int[] array = BubbleSortTestCaseMaker.buildRandom(arrayLength, arrayLength*100);
           BubbleSorter sorter = new BubbleSorter(array);
           sorter.sort();
           // Assert that the sorter sorted correctly.
           // Append # visits and # swaps to the array lists.
       }

       // Compute and print min/average/max number of visits.
       // Compute and print min/average/max number of swaps.
   }
  
  
   public static void main(String[] args)
   {
       System.out.println("1000:");
       getStats(1000);
      
       System.out.println("3000:");
       getStats(3000);
   }
}
----------------------------------------------------------------------------------------------------------------------------------------

package bubble;

public class BubbleSortTestCaseMaker
{
   private final static int[]       TINY =
   {
       1000, 1, 2, 3
   };
  
   public static int[] getTiny()
   {
       return TINY;
   }
  
  
   private final static int[]       ALREADY_SORTED =
   {
       1, 2, 3, 4, 5, 6, 7, 8, 9, 10
   };
  
   public static int[] getAlreadySorted()
   {
       return ALREADY_SORTED;
   }
  
  
   private final static int[]       BACKWARD =
   {
       10, 9, 8, 7, 6, 5, 4, 3, 2, 1
   };
  
   public static int[] getBackward()
   {
       return BACKWARD;
   }
  
  
   public static int[] buildRandom(int length, int maxValue)
   {
       int[] array = new int[length];
       for (int i=0; i<length; i++)
           array[i] = (int)(Math.random()*(maxValue + 1));
       return array;
   }
  
  
   public static void main(String[] args)
   {
       for (int i: buildRandom(10, 100))
           System.out.println(i);
   }
}

Answer 1

Desired changes are made in below BubbleSorter class:

public class BubbleSorter
{
   private int[]       a;
   private long       nVisits;
   private long       nSwaps;
  
  
   public BubbleSorter(int[] a)
   {
       this.a = a;
   }
  
  
   public void sort()
   {   
       int n=a.length;

       for (int i=0;i<n;i++)
       {
           for (int j=n-1;j>=1;j--)
           {
               // Increment number of visits by 2.
                  nVisits+=2;

               if (a[j-1]>a[j])
               {   
                   //  a[j-1] and a[j] should be swapped
                   nSwaps++;
                   int temp=a[j];
                   a[j]=a[j-1];
                   a[j-1]=temp;
               }
           }
       }
   }
  
  
   public String toString()
   {
       String s = nVisits + " visits, " + nSwaps + " swaps\n{";
       for (int n: a)
           s += " " + n;
       s += " }";
       return s;
   }
  
  
   public boolean isSorted()
   {
       int n=a.length;
       boolean result=true;

       for(int i=1;i<n;i++)
       {
           if(a[i-1]>a[i])
           result=false;
       }
       
       return true;

   }
  
  
   public long getNVisits()
   {
       return nVisits;
   }
  
  
   public long getNSwaps()
   {
       return nSwaps;
   }
  
  
   public int[] getArray()
   {
       return a;
   }
  
  
   public static void main(String[] args)
   {
       // replace getTiny() with getAlreadySorted() or getBackward() or buildRandom(100, 1000) for different test array input

       int[] a = BubbleSortTestCaseMaker.getTiny();
      
       BubbleSorter sorter = new BubbleSorter(a);
       sorter.sort();
       System.out.println(sorter);
       System.out.println(sorter.isSorted() ? "SORTED" : "NOT SORTED");
   }
}

Output with getTiny() method:

Output with getAlreadySorted() method:

Output with getBackward() method:

Output with buildRandom(100, 1000) method: