I've been asked to create a bubble sort function that checks whether the array has been filled sorted before all passes are complete, thereby avoiding unnecessary passes. This is to involve "remembering" the last sort.
Below is the code I have for just a normal bubble sort that goes through all passes, and is quite inefficient. The parameter variables are 'a' for the generic array itself and n
, which is the number of passes. In this case we're doing a full set of passes for the array, which is 10 integers in length.
public static void main(String[] args) {
Integer[] myArray = new Integer[10];
System.out.println("Iterative Bubble Sort - Ch 8, Ex 8a on page 265");
generateRandonNumbers(myArray);
display(myArray);
bubbleSort(myArray,10);
display(myArray);
System.out.println("Recursive Bubble Sort - Ch 8, Ex 8b on page 265");
generateRandonNumbers(myArray);
display(myArray);
recursiveBubbleSort(myArray,10);
display(myArray);
System.out.println("Better Bubble Sort - Ch 8, Ex 10 on page 266");
generateRandonNumbers(myArray);
display(myArray);
betterBubbleSort(myArray,10);
display(myArray);
}
public static void display(Integer[] array)
{
for(int i=0; i<array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void generateRandonNumbers(Integer[] array)
{
Random randomNum = new Random();
for(int i=0; i<array.length; i++)
{
array[i] = randomNum.nextInt(100);
}
}
public static <T extends Comparable<? super T>> void bubbleSort(T[] a, int n)
{
int k = 0;
while (k <= n)
{
k++;
for (int i = 0; i < a.length - k; i++)
{
if (a[i].compareTo(a[i+1]) > 0)
{
T data = a[i];
a[i] = a[i + 1];
a[i + 1] = data;
}
}
}
}
The test results are:
9 36 59 60 40 28 71 95 90 56
(unsorted, displaying all values from the array)
9 28 36 40 56 59 60 71 90 95
(now sorted from the bubbleSort function)
How do I go about turning this into a more efficient sort function by avoiding unnecessary passes? I'm supposed to get the program to remember the last sort and I'm not sure how to go about doing this.