implement the bubble sort algorithm. The bubble sort is so called because it com

Question

implement the bubble sort algorithm.

The bubble sort is so called because it compares adjacent items, "bubbling" the smaller one up toward the beginning of the array. By comparing all pairs of adjacent items starting at the end of the array, the smallest item is guaranteed to reach the beginning of the array at the end of the first pass.

The second pass begins again at the end of the array, ultimately placing the second smallest item in the second position. During the second pass, there is no need to compare the first and second items, because the smallest element is guaranteed to be in the first position.

Bubble sort takes at most n - 1 passes for an array of n items. During the first pass, n - 1 pairs need to be compared. During the second pass, n - 2 pairs need to be compared. During the ith pass, n - i pairs need to be compared. During the last pass, n - (n - 1) or one pair needs to be compared. If, during any pass, no two adjacent items need to be interchanged, the array is in order and the sort can terminate. If it continues, no further interchanges will occur.

Complete the BubbleSorter class, below:

/**
   This class sorts an array, using the bubble sort algorithm.
*/
public class BubbleSorter
{
   private int[] a;

   /**
      Constructs a bubble sorter.
      @param anArray the array to sort
   */
   public BubbleSorter(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this bubble sorter.
   */
   public void sort()
   {
      // *** ADD CODE HERE ***
   }

   /**
      Swaps two entries of the array.
      @param i the first position to swap
      @param j the second position to swap
   */
   private void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }
}

You can test your BubbleSorter with the following test class:

import java.util.Arrays;

public class BubbleSortTester
{
    public static void main(String[] args)
    {
        final int ARRAY_SIZE = 20;
        int[] a = new int[ARRAY_SIZE];
       
        // fill array with random numbers
        for (int i=0; i<ARRAY_SIZE; i++)
        { a[i] = 1 + (int)(ARRAY_SIZE * Math.random()); }
       
        // display the array
        System.out.print("Original Array: ");
        System.out.println( Arrays.toString( a ) );
       
        // create BubbleSorter and sort array
        BubbleSorter sorter = new BubbleSorter( a );
        sorter.sort();
       
        // display the sorted array
        System.out.print("Sorted Array: ");
        System.out.println( Arrays.toString( a ) );
    } // end main
} // end class BubbleSortTester

Explanation / Answer

public class BubbleSorter {
   private int[] a;

   /**
   * Constructs a bubble sorter.
   *
   * @param anArray
   *            the array to sort
   */
   public BubbleSorter(int[] anArray) {
       a = anArray;
   }

   /**
   * Sorts the array managed by this bubble sorter.
   */
   public void sort() {
       for (int i = 1; i < a.length; i++) {
           boolean is_sorted = true;

           for (int j = 0; j < a.length - i; j++) { // skip the already sorted
                                                       // largest elements
               if (a[j] > a[j + 1]) {
                   swap(j, j + 1); // swapping
                   is_sorted = false;
               }
           }

           if (is_sorted) // if we did not swapped any pair, then array is sorted now
               return;
       }
   }

   /**
   * Swaps two entries of the array.
   *
   * @param i
   *            the first position to swap
   * @param j
   *            the second position to swap
   */
   private void swap(int i, int j) {
       int temp = a[i];
       a[i] = a[j];
       a[j] = temp;
   }
}

import java.util.Arrays;

public class BubbleSortTester
{
    public static void main(String[] args)
    {
        final int ARRAY_SIZE = 20;
        int[] a = new int[ARRAY_SIZE];
     
        // fill array with random numbers
        for (int i=0; i<ARRAY_SIZE; i++)
        { a[i] = 1 + (int)(ARRAY_SIZE * Math.random()); }
     
        // display the array
        System.out.print("Original Array: ");
        System.out.println( Arrays.toString( a ) );
     
        // create BubbleSorter and sort array
        BubbleSorter sorter = new BubbleSorter( a );
        sorter.sort();
     
        // display the sorted array
        System.out.print("Sorted Array: ");
        System.out.println( Arrays.toString( a ) );
    } // end main
} // end class BubbleSortTester

/*

output:

Original Array: [1, 14, 7, 6, 17, 10, 12, 18, 1, 14, 8, 6, 10, 5, 20, 3, 14, 16, 3, 9]
Sorted Array: [1, 1, 3, 3, 5, 6, 6, 7, 8, 9, 10, 10, 12, 14, 14, 14, 16, 17, 18, 20]

*/

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.