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

Answer 1

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.