JAVA: The bubble sort algorithm shown in this chapter is less efficient than it

Question

JAVA: The bubble sort algorithm shown in this chapter is less efficient than it can be. If a pass is made throught the list without exchanging any elements, this means that the list is sorted and there is no reason to continue. Modify this algorithm so that it will stop as soon as it recognizes that the list is sorted.

import java.util.Arrays;

public class Base_Bubble
{
    /**
     * Program entry point for bubblesort testing.
     * @param args Argument list.
     */   
    public static void main(String[] args)
    {
         Integer[] data = {72, 54, 31, 39, 53, 9, 81, 73, 98, 99};
        
         System.out.println("Before: " + Arrays.toString(data));
         bubbleSort(data);
         System.out.println("After: " + Arrays.toString(data));
    }
   
/**
* Swaps to elements in an array. Used by various sorting algorithms.
*
* @param data   the array in which the elements are swapped
* @param index1 the index of the first element to be swapped
* @param index2 the index of the second element to be swapped
*/
private static <T extends Comparable<T>>
  void swap(T[] data, int index1, int index2)
{
  T temp = data[index1];
  data[index1] = data[index2];
  data[index2] = temp;
}

    /**
     * Sorts the specified array of objects using a bubble sort
     * algorithm.
     * TODO: Stops the sort if a pass makes no changes.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
  void bubbleSort(T[] data)
    {
        int position, scan;
        T temp;
  
        for (position = data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
            }
        }
    }
}

Explanation / Answer

import java.util.Arrays;
public class Base_Bubble
{
/**
* Program entry point for bubblesort testing.
* @param args Argument list.
*/   
public static void main(String[] args)
{
Integer[] data = {72, 54, 31, 39, 53, 9, 81, 73, 98, 99};
  
System.out.println("Before: " + Arrays.toString(data));
bubbleSort(data);
System.out.println("After: " + Arrays.toString(data));
}

/**
* Swaps to elements in an array. Used by various sorting algorithms.
*
* @param data the array in which the elements are swapped
* @param index1 the index of the first element to be swapped
* @param index2 the index of the second element to be swapped
*/
private static <T extends Comparable<T>>
void swap(T[] data, int index1, int index2)
{
T temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}

/**
* Sorts the specified array of objects using a bubble sort
* algorithm.
* TODO: Stops the sort if a pass makes no changes.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void bubbleSort(T[] data)
{
int position, scan;
T temp;
  
boolean flag = true; // flag to check wether a swap has done or not
for (position = data.length - 1; position >= 0 && flag; position--)
{
   flag = false; // make flag false
for (scan = 0; scan <= position - 1; scan++)
{
if (data[scan].compareTo(data[scan+1]) > 0){
swap(data, scan, scan + 1);
// if a swap is done then make flag true, so we go for next iteration
flag = true;
}
}
  
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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