Question

Using this BubbleSort implementation in Java:

public class BubbleSort<T extends Comparable<T>>
{

   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;
   }
   public void sort(T[] data)
   {
      int position, scan;

      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);
         }
      }
   }
}

Modify the code to reflect the following: If the inner loop completes without performing any exchanges, the array must already be sorted, so the sort can stop. Introduce a flag set to false before the inner loop starts, but which the inner loop sets true when it calls swap. Then have the outer loop stop when the inner loop completes without doing a swap.

Answer 1

Required solution is

Steps :-

1.) declare a variable flag of boolean type which is initialized as true.

boolean flag = true;

2.) in outer loop, add flag with loop condition with AND(&&)

for (position = data.length - 1; position >= 0 && flag ; position--)

3.) before start at the inner loop, set flag to false value

4.) while swapping occurred set the flag to true value

Explanation:

Complete program will be

BubbleSort.java

public class BubbleSort<T extends Comparable<T>>


{


        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;


        }


        public void sort(T[] data)


        {


                int position, scan;


                boolean flag = true;


                for (position = data.length - 1; position >= 0 && flag; position--)


                {
                        flag = false; // a flag set to false before the inner loop starts


                        for (scan = 0; scan <= position - 1; scan++)


                        {


                                if (data[scan].compareTo(data[scan + 1]) > 0) {


                                        swap(data, scan, scan + 1);
                                        flag = true; // inner loop sets true when it calls swap
                                }


                        }


                }


        }


}