5
\$\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\$
1
  • 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, 2015 at 9:27

1 Answer 1

3
\$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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