4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I think en.wikipedia.org/wiki/Bubble_sort contains enough information to optimize the algorithm. Are you having difficulties with implementing this? \$\endgroup\$ – Caramiriel Feb 24 '15 at 9:27
2
\$\begingroup\$

Instead of using a regular for loop to loop through array:

for(int i=0; i<array.length; i++)
{
    System.out.print(array[i] + " ");
}

you can use a nicer foreach loop:

for (int i : array)
{
    System.out.print(i + " ");
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.