is there a more sophisticated version of bubble sort algorithm in java?

Question

I created some code that sorts an array using bubble sort but I was told that there is a variation of bubble sort that performs better, so I was wondering if there is an better version of bubble sort. For example, I'm using the regular version if it below:

package termproject3;

import java.util.Random;
import java.util.Scanner;
import java.util.concurrent.TimeUnit;


public class TermProject3 {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here 
    Scanner sc = new Scanner(System.in);    
    System.out.println("please enter the size of the array:");
    int n = sc.nextInt();
     System.out.println("Enter the  number of iterations: ");
    int num_i = sc.nextInt();
    int swap;
    int array[] = new int[n];

    Random r = new Random();
    long startTime = System.nanoTime();
    for (int t = 0; t < num_i; t++){
     System.out.println();   
    System.out.println( t+1 + ".- Array to be sorted: ");

    for (int i = 0; i < n; i++) {
        array[i] = r.nextInt(array.length);

        System.out.print(array[i] + ", ");
    }

    System.out.println();

    for (int i = 0; i < (n - 1); i++) {
        for (int d = 0; d < n - i - 1; d++) {
            if (array[d] > array[d + 1]) {
                swap = array[d];
                array[d] = array[d + 1];
                array[d + 1] = swap;
            }
        }
    }

    System.out.println("Sorted list using bubble sort :");

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

}
 long running_time = System.nanoTime() - startTime;

System.out.println("elapsed time: " +running_time+ " nano seconds"); 

System.out.println("which is " + running_time/1E9 + " seconds");
}
}

Unless this is a school assignment, I'd probably just use the built-in sort. — xdhmoore, Feb 20 '14 at 15:27
it is, indeed, a school assignment, and I was told that there is an optimized version of it. @xdhmoore — UnPatoCuacCuac, Feb 20 '14 at 15:33
What do you mean optimized? consider that if it performs better than O(n^2) it isn't bubble sort anymore. — Nathan Hughes, Feb 20 '14 at 15:35
Bubble sort and variants: http://en.wikipedia.org/wiki/Sorting_algorithm#Bubble_sort_and_variants — starsplusplus, Feb 20 '14 at 15:39
by optimized, I mean that there is a variable of bubble sort that checks if the array is already sorted and if it is it goes to the next number instead of iterate over the entire array — UnPatoCuacCuac, Feb 20 '14 at 15:40
I think the key is where you are initializing d every time to 0. — xdhmoore, Feb 20 '14 at 15:45

score 4 · Answer 1 · answered Feb 20 '14 at 15:25

4

I don't know why you'd want to use bubble sort, but Collections.sort(List) and Collections.sort(List, Comparator) implement quicksort that you can use.

answered Feb 20 '14 at 15:25

Mureinik

297,002
52
306
350

the point of this is to optimize the current bubble sort with a optimized version of bubble sort. – UnPatoCuacCuac Feb 20 '14 at 15:34

score 0 · Answer 2 · edited May 23 '17 at 12:14

0

This answer may be helpful to you: Optimized Bubble Sort (Java)

It is notable to mention that optimizing a bubble sort is a silly exercise as much quicker, more elegant methods exist:

Collections.sort(List)

edited May 23 '17 at 12:14

Community

1
1

answered Feb 20 '14 at 15:51

TayTay

6,882
4
44
65

is there a more sophisticated version of bubble sort algorithm in java?

2 Answers2