CODEWITHSUNDEEP
javaarraysalgorithmsorting
Blued00d
Blued00d

Reputation: 170

Java Execution Run Time of Bubble vs Selection Sort

I am a novice programmer and am currently on break so I am just trying to polish up on my skills before I start school again. I have written some code that will create an array of 100 elements and populate all 100 indexes with a random number between 0 and 250.

I have written code to sort this array using bubble sorting algorithm and also selection sorting algorithm (I plan to do all known array sorting algorithms and compare execution times.) I have notice that my run time for selection sorting is MUCH faster than bubble sort.

Example run: Bubble sort time: 7.45 ms ------ Selection sort time: 0.15 ms

So my question is.. Have I messed something up or are these results normal?

Here is my code:

import java.util.*;

public class Bubble {

        private static int[] myArray;
        private static int[] myBubbleArray;
        private static int[] mySelectionArray;


public static void main(String args[]){

    createList();
    fillArray();
    print("Original Array: ", myArray);
    long selectionStartTime = System.nanoTime();
    selectionSortArray(mySelectionArray);
    double selectionElapsedTime = (System.nanoTime() - selectionStartTime) / 1000000.0;     
    print("Selection Sorted Array: ", mySelectionArray);
    System.out.printf("Total execution time for selection sort is %.2f ms\n", selectionElapsedTime);
    long bubbleStartTime = System.nanoTime();
    bubbleSortArray(myBubbleArray);
    double bubbleElapsedTime = (System.nanoTime() - bubbleStartTime) / 1000000.0;
    print("Bubble Sorted Array: ", myBubbleArray);
    System.out.printf("Total execution time for bubble sort is %.2f ms\n", bubbleElapsedTime);
}

private static int[] selectionSortArray(int[] array) {
    int first;
    int temp;
    for(int i=array.length -1; i > 0; i--){
        first = 0;
        for(int j = 1; j <= i; j++){
            if(array[j] > array[first]) first = j;
        }
        temp = array[first];
        array[first] = array[i];
        array[i] = temp;
    }
    return mySelectionArray;
}

private static int[] bubbleSortArray(int[] array) {
    boolean swapped = true;
    int temp;
    while(swapped){
        swapped = false;
        for(int i = 0; i < array.length-1; i ++){
            for(int j = 1; j < array.length - i; j++){
                if(array[i] > array[i+1]){
                    temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                    swapped = true;
                }
            }
        }
    }
    return myBubbleArray;
}

public static int[] createList(){
    myArray = new int[100];
    return myArray;
}

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

public static void fillArray(){
    for(int i = 0; i < myArray.length-1; i ++){
        Random rand = new Random();
        myArray[i] = rand.nextInt(250);
    }
    myBubbleArray = Arrays.copyOf(myArray, myArray.length);
    mySelectionArray = Arrays.copyOf(myArray, myArray.length);
}
}

Upvotes: 1

Views: 1200

Answers (1)

Shawn Mehan
Shawn Mehan

Reputation: 4568

For an in-depth answer, go here. The summary is specifically, Bubble sort requires, on average, n/4 swaps per entry (each entry is moved element-wise from its initial position to its final position, and each swap involves two entries), while Selection sort requires only 1 (once the minimum/maximum has been found, it is swapped once to the end of the array).

In terms of the number of comparisons, Bubble sort requires k×n comparisons, where k is the maximum distance between an entry's initial position and its final position, which is usually larger than n/2 for uniformly distributed initial values. Selection sort, however, always requires (n−1)×(n−2)/2 comparisons.

Upvotes: 2

Related Questions