Why is selection sort faster than bubble sort?

Question

Using Java I have conducted an experiment to determine which sorting method's (bubble or selection) runtime is faster. The program prompts the user to enter a number n which is the number of items in the array to sort. Then it creates and sorts 500 different arrays of this size and times the run to get an average time to sort using both sort methods. I used 500, 1000, and 2500 as test inputs for n. My results below show that selection sort runs faster than bubble sort, but both algorithms have a time complexity of O(n^2), so why is selection sort running so much faster?

TimeBubbleSort Class

public class TimeBubbleSort {
    public static void main(String[] args) {

        System.out.print("Enter a number of items in array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        long start_time = 0;
        long end_time = 0;
        long running_time = 0;
        long final_time = 0;
        BubbleSort bubbleSort = new BubbleSort();

        for(int i = 0; i < 500; i++) {
            int[] array = new int[n];
            for(int j = 0; j < array.length; j++) {
                array[j] = (int)(Math.random() * n) + 1;
            }
            start_time = System.nanoTime();
            bubbleSort.bubbleSort(array);
            end_time = System.nanoTime();
            running_time = end_time - start_time;
            final_time = final_time + running_time;
        }
        System.out.println("The average time of each array took " + 
(final_time / 500) + " nanoseconds");
    }
}

BubbleSort Class

public class BubbleSort {

    void bubbleSort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        for (int i = 0; i < n; i++)
            for (int j = 1; j < (n - i); j++)
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
    }

    void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

TimeSelectionSort Class

public class TimeBubbleSort {
    public static void main(String[] args) {

        System.out.print("Enter a number of items in array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        long start_time = 0;
        long end_time = 0;
        long running_time = 0;
        long final_time = 0;
        SelectionSort selectionSort = new SelectionSort();

        for(int i = 0; i < 500; i++) {
            int[] array = new int[n];
            for(int j = 0; j < array.length; j++) {
                array[j] = (int)(Math.random() * n) + 1;
            }
            start_time = System.nanoTime();
            selectionSort.selectionSort(array);
            end_time = System.nanoTime();
            running_time = end_time - start_time;
            final_time = final_time + running_time;
        }
        System.out.println("The average time of each array took " + 
(final_time / 500) + " nanoseconds");
    }
}

SelectionSort Class

public class SelectionSort {
    void sort(int arr[]) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    void printArray(int arr[]) {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
}

Results Using Bubble Sort

Array Size of 500: took 284,979 nanoseconds

Array Size of 1000: took 960,067 nanoseconds

Array Size of 2500: took 7,448,865 nanoseconds

Results Using Selection Sort

Array Size of 500: took 107,035 nanoseconds

Array Size of 100: took 342,464 nanoseconds

Array Size of 2500: took 1,880,215 nanoseconds

This is not an accurate benchmark: https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Jacob G., Sep 22 '18 at 01:13
If two algorithms are both `O(n^2)` it doesn't follow that their run times are the same. For one thing, there is an asymptotic constant of proportionality inherent in `O(n^2)` which will differ depending on the algorithm and the details of its implementation. — John Coleman, Sep 22 '18 at 01:16
Wow, this goes back - memories of teaching people in the 1980s how to write selection sort in COBOL. — Don Branson, Sep 22 '18 at 01:31

Brij Raj Kishore · Accepted Answer · 2018-09-22T01:26:53.463

3

First of all comparing against the system time is not the correct way of analysing the time complexity of two algorithms because remember - your's program is not the only program running on the system. And hence even if the algorithm and input is same the two running time can be entirely different.

Now coming onto your answer, bubble sort has more number of swap compared to the selection sort in which we only swap at last step in each iteration. So it might be the reason.

And the two algorithms having same time complexity doesn't suggest that their running time would be same. First of all their time complexity is taken approximately which is the largest factor which contributes the most. In both of the above case the largest factor is n^2 but there are other smaller powers of n and the constant which will make the difference.

edited Sep 22 '18 at 01:26

answered Sep 22 '18 at 01:21

Brij Raj Kishore

1,595
1
11
24

While using the system timer isn't good practice he's doing it 500 times, it should average out. – Loren Pechtel Sep 22 '18 at 01:30
that's what I said. There are many processes running besides and their scheduling and other factors will the running time never be same – Brij Raj Kishore Sep 22 '18 at 01:31
@KevinAnderson No--note that his termination condition is n - i. There are approximately the same number of comparisons here. – Loren Pechtel Sep 22 '18 at 01:32
@KevinAnderson the comparison will also be reduced in the bubble sort. We will not go till the end in case of bubble sort every time while in selection sort we will not consider the elements from starting – Brij Raj Kishore Sep 22 '18 at 01:33
the difference will be that in case of ascending (non -decreasing )sorting we will start to left out first few elements in selection sort while in case of bubble sort we will left the few last. I hope you got exactly what the few meant here – Brij Raj Kishore Sep 22 '18 at 01:37

score -1 · Answer 2 · answered Sep 22 '18 at 01:34

While your use of the system timer here is iffy you are doing enough trials that I don't think it's the culprit. I also have a hard time believing the swap is consuming nearly 2/3 of the total time which would be required for Brij Raj Kishore's answer to be right.

While your loop structures aren't completely identical both run about n^2/2 times so there shouldn't be any big difference there, either.

Thus, I think more digging is in order. I have no idea what profilers you have available on your system but unless someone finds something big here that would be my next step. See where your routine is actually spending it's time.

Why is selection sort faster than bubble sort?

2 Answers2