title: Why is Bubble sort performing better than Selection sort in average case
body: <p>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.</p>
  
  <p><a href="https://i.stack.imgur.com/lFaQk.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lFaQk.png" alt="Selection vs Bubble vs Insertion"></a></p>
  
  <p>This my Selection implementation:</p>
  
  <pre><code>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 &lt; arr.length; i++) {
              // Assign the default min index
              int min = i;
              // Find the index with smallest value
              for (int j = i + 1; j &lt; arr.length; j++) {
                  if (arr[j] &lt; arr[min]) {
                      min = j;
                  }
              }
              // Swap index arr[min] with a[i]
              int temp = arr[min];
              arr[min] = arr[i];
              arr[i] = temp;
          }
      }
  </code></pre>
  
  <p>My Bubble Sort:</p>
  
  <pre><code>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 &lt; n - 1; i++) {
              if (arr[i] &gt; arr[i + 1]) {
                int temp = arr[i + 1];
                arr[i + 1] = arr[i];
                arr[i] = temp;
                sorted = false;
              }
            }
            n--;
          }
        }
  </code></pre>
  
  <p>My implementation of Bubble sort not optimised to exit if the list is sorted:</p>
  
  <pre><code>for (int i = 0; i &lt; 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 &lt; arr.length - i - 1; j++) {
              if (arr[j] &gt; arr[j + 1]) {
                /*
                 * In the case where an inversion exists in 
                 * arr[j] &gt; 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;
              }
            }
          }
  </code></pre>
  
  <p>This is how I generate the randomised array for inout:</p>
  
  <pre><code>int[] random = new int[n];
          for (int i = 0; i &lt; n; i++) {
              random[i] = randomInteger.nextInt(100);
          }
  </code></pre>
  
  <p>Any input as to why the Bubble sort is faster appreciated.</p>