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

Question

The bubble sort algorithm shown in this chapter is less efficient than it could be. If a pass is made through the list without ex- changing 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. Do not use a break statement! Make it to where it compiles succesfully. Thanks

Program:

public class bubblesort
{
public static void bubbleSort (Comparable[] data, int maxlength)
{
int position, scan;
Comparable temp;

for (int i = maxlength-1; i >= 1; i--)
{
for (scan = 0; scan <= maxlength-i ; scan++)
{
if (data[scan].compareTo(data[scan+i]) > 0)
{
// Swap the values
temp = data[scan];
data[scan] = data[scan + i];
data[scan + i] = temp;
  
}
}
}
}
}

Explanation / Answer

//Java program that analysis the ordinary sorting
//and effcient bubble sorting that displays the number of
//comparisions made by each ordinary and efficient sorting
//methods display the results.
import java.util.Arrays;
public class bubblesort
{
   public static void main(String[] args)
   {
       Comparable[] elementsSet1={4,6,3,9,1,8,2};
       System.out.println("Ordinary Bubble sort");
       System.out.println(Arrays.toString(elementsSet1));
       System.out.println("Number of comparions : "+bubbleSort(elementsSet1, elementsSet1.length-1));
       System.out.println("Sorted : "+Arrays.toString(elementsSet1));
              
      
      
       Comparable[] elementsSet2={4,6,3,9,1,8,2};
       System.out.println("Effcient Bubble sort");
       System.out.println(Arrays.toString(elementsSet2));
       System.out.println("Number of comparions : "+efficientBubbleSort(elementsSet2, elementsSet2.length-1));
       System.out.println("Sorted : "+Arrays.toString(elementsSet1));

   }

  
   //Efficient bubble sort that returns the number of comparision are made
   //for sorting elements in ascending order.
   public static int efficientBubbleSort (Comparable[] data, int maxlength)
   {
      
       boolean swap=true;
       int comparision=0;
       Comparable temp;
       int i=0;
      

       while(swap)
       {
           swap=false;
           i++;
           for (int scan = 0; scan < maxlength-i ; scan++)
           {
               //increment the number of comparisions by one
               comparision++;
               if (data[scan].compareTo(data[scan+1]) > 0)
               {
                   // Swap the values
                   temp = data[scan];
                   data[scan] = data[scan + 1];
                   data[scan + 1] = temp;
                   //after swapping set to swap to true
                   swap=true;
                  
               }
           }
       }
       //returns the number of comparisions
       return comparision;
   }

  
   //Ordinary bubble sort that returns the number of comparision are made
       //for sorting elements in ascending order.
   public static int bubbleSort (Comparable[] data, int maxlength)
   {
       int position, scan;
       Comparable temp;
       int comparisions=0;

       for (int i = maxlength-1; i >= 1; i--)
       {
           for (scan = 0; scan <= maxlength-i ; scan++)
           {      
               //increment the number of comparisions by one
               comparisions++;
               if (data[scan].compareTo(data[scan+i]) > 0)
               {
                   // Swap the values
                   temp = data[scan];
                   data[scan] = data[scan + i];
                   data[scan + i] = temp;
                  

               }
           }
       }
       //returns the number of comparisions
       return comparisions;
   }
}

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

Sample output:

Ordinary Bubble sort
[4, 6, 3, 9, 1, 8, 2]
Number of comparions : 20
Sorted : [1, 2, 3, 4, 6, 8, 9]
Effcient Bubble sort
[4, 6, 3, 9, 1, 8, 2]
Number of comparions : 15
Sorted : [1, 2, 3, 4, 6, 8, 9]

Hope this helps you

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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