Why is Bubble sort performing better than Selection sort in average case

Question

I am benching marking sorting algorithms using java. When I compare average case Bubble sort with Selection sort using randomised arrays ranging for 0 to 99 the Bubble sort performs noticeably better. Most references to performance I have read state the Section sort is the better of the two.

This my Selection implementation:

public static void selectionSort(int[] arr) {
        /*
         * Selection sort sorting algorithm. Cycle: The minimum element form the
         * unsorted sub-array on he right is picked and moved to the sorted sub-array on
         * the left.
         * 
         * The outer loop runs n-1 times. Inner loop n/2 on average. this results in
         * (𝑛−1)×𝑛2≈𝑛2 best, worst and average cases.
         * 
         */

        // Count outer
        for (int i = 0; i < arr.length; i++) {
            // Assign the default min index
            int min = i;
            // Find the index with smallest value
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // Swap index arr[min] with a[i]
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

My Bubble Sort:

public static void optimalBubbleSort(int[] arr) {
          /**
           * The optimized version will check whether the list
           * is sorted at each iteration. If the list is sorted the 
           * program will exist.
           * Thus the best case for the optimized bubble sort 
           * is O{n). Conversely the above algorithm
           * the best case will always be the same as the average case.
           * 
           */
        boolean sorted = false;
        int n = arr.length;
        while (!sorted) {
          sorted = true;
          for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
              int temp = arr[i + 1];
              arr[i + 1] = arr[i];
              arr[i] = temp;
              sorted = false;
            }
          }
          n--;
        }
      }

My implementation of Bubble sort not optimised to exit if the list is sorted:

for (int i = 0; i < arr.length - 1; i++) {
          /*
           * Iteration of the outer loop will ensure
           * that at the end the largest element is in the 
           * (array.lenght-(i+1))th index.
           * Thus the loop invariant is that 

           * In other words, the loop invariant is that
           * the subsection bounded by the indices
           * [arr.length - i, arr.length] is sorted and
           * contains the i biggest elements in array.
           */

          for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
              /*
               * In the case where an inversion exists in 
               * arr[j] > arr[j + 1],
               * arr[j] and arr[j + 1] are
               * thus swapped.
               */
              int temp = arr[j + 1];
              arr[j + 1] = arr[j];
              arr[j] = temp;
            }
          }
        }

This is how I generate the randomised array for inout:

int[] random = new int[n];
        for (int i = 0; i < n; i++) {
            random[i] = randomInteger.nextInt(100);
        }

Any input as to why the Bubble sort is faster appreciated.

Answer 1

If I am right, you are sorting values in range [0, 99] and arrays of length up to 100000. Which means that every value can be repeated up to 1000 times on average.

IMO you can discard all your results as you are testing very special cases where a big amount of keys are equal and the algorithms can have a non-standard behavior. Their performance will be more sensitive to usually unimportant implementation details. The classical sorting algorithms were not designed for such extreme situations.

I would like to add that comparing slow sorts to fast sorts on big data sets does not make much sense (the curves for the fast sorts are so closely packed that you can't compare any of them.)

Answer 2

As you've found, the main difference between bubble and selection sort is that the bubble sort can work much faster than the selection sort, when the array is (nearly) sorted. In your case, as you select your random number between 0 and 100, if the chosen length of the array n is much less than 100, the probability of (nearly) sorted sample will be increased. In this sense, you can find that the average complexity of the bubble sort is better than the selection sort.

Therefore, you should be aware that this comparison depends on n, and if you increase the value of n, as the probability of sorted arrays is decreased, you will find these two curves closer.

Answer 3

So if we compare the number of comparisons, the both algorithms will have something around n*(n+1)/2 (or just the sum of all numbers from n to 1), which is approximately n^2 as you stated.

The selection sort surely does have less swaps than the bubble sort, but the thing is that it will go over the whole array and sort even if it's already sorted. The bubble sort would actually do around n comparisons when the array is sorted, which makes it have O(n) time complexity in the best case. It will also be faster when the array is nearly sorted, which on average results in bubble sort being faster than insertion sort. You can find the big O of each case on this site

And on this site you can see what actually happens if the array is already or nearly sorted.