Why is my Java based Bubble Sort Outperforming my Selection Sort and my Insertion Sort

Question

Ok, so I have an implementation of a bubble sort, selection sort and insertion sort. I'm using Java.Random object to create three identical arrays of one hundred thousand numbers. I am passing these to each sort method in turn. I am timing the results using System.nanotime.

For some background information. The sort algorithms I followed for Selection and Insertion sort come from Frank Carano's "Data Structures and Abstraction's in Java 3rd Ed" The bubble sort, was off the top of my head.

Below I provide a self contained class that performs all this. Where have Carano's algorithms gone wrong I do not see it?

Below you will see I am counting the cycles of the base operations and timing the completion. At run time the number of cycles is negligibly different. For me when looking at completion time, Bubble is 1st, Selection is 2nd and Insertion is 3rd. This flies in the face of conventional wisdom. Why. Have I done something rather daft?

BTW you should be able to compile and run the provided code without any changes.

import java.util.Random;


/**
 * 
 * Performs sorts on generic data, here using Integers.
 */
public class GenSorts {

    static int selectionCount = 0, bubbleCount = 0, insertionCount = 0;;

    //=========================================================================
    /**
     * Do an insertion sort.
     * @param data The array to sort
     * @param first The index of the first element
     * @param lasr The index of the last element
     */
    //=========================================================================
    public static <T extends Comparable<? super T>> void insertionSort(T[]array, int first, int last){

        for(int untouch = first + 1; untouch < last; untouch++){
            T nextToInsert = array[untouch];

            insertInOrder(nextToInsert, array, first, untouch-1);

        }//end for
    }//=========================================================================

    //=========================================================================
    /**
     * Performs the shuffle and insert part of the insertion sort.
     * @param anEntry The value to insert
     * @param array The target array
     * @param begin The begin of the unsorted part.
     * @param end The end of the unsorted part.
     */
    //=========================================================================
    public static <T extends Comparable<? super T>> void insertInOrder(T anEntry, T[]array, int begin, int end){

         int index = end;
         //Do a shunt while an entry is less than the value at the index
         while( ( index >= begin )  && (anEntry.compareTo(array[index]) < 0)  ){
             array[index+1] = array[index];
             index --;
             insertionCount++;
         }

         array[index+1] = anEntry;//Insert
    }//======================================================================


    //======================================================================
    /**
     *  BUBBLE SORT///////////////////////////////////////////////////////////
     * Perform a bubble sort on the data.
     * @param data The array to be sorted.
     */
    //======================================================================
    public static <T extends Comparable <? super T> >void bubbleSort  (T[] data)
    {
        Boolean swapped = true;
        int stop = data.length -1;


         while (swapped) {
            swapped = false;

            for (int x = 0; x < stop ; x++ ) {
                 bubbleCount++;
                //if x smaller than x +1 swap
               if ( data[x].compareTo(  data[x+1]   ) > 0 ) { 

                      swap(x, x+1, data );
                      swapped = true;
               }//end if 

               stop --;

           }//end for 

        }//end while
    }//end  method============================================================


    //========================================================================
    /**
     * SELECTION SORT/////////////////////////////////////////////////////////
     * A selection sort algorithm to sort data.
     * @param data
     * @return
     */
    //========================================================================
    public static <T extends Comparable<? super T> >  void selectionSort(T[] data, int n){

         for (int index = 0; index < n - 1; index++)
          {
             selectionCount++;
             int min = getSmallestIndex( index, n,data);

             swap(  index, min, data);

             //DISPLAYME
           //  displaySelectionArray(index, min, data);
          }

    }//========================================================================



    //==========================================================================
    /**
     * Get the index of the smallest item in the array from start to end/
     * @param start The place in the array to start looking.
     * @param end The place in the array to end looking.
     * @param array The array to inspect.
     * @returnThe index of the smallest.
     */
    //==========================================================================
     private static <T extends Comparable<? super T>> int  getSmallestIndex( int start, int end, T[] array)
       {
          T min = array[start];//value of smallest
          int minIndex = start;//index of smallest
          for (int i = start + 1; i < end; i++)
          {

             // System.out.print(array[i].toString() + ", ");
             if (array[i].compareTo(min) < 0)
             {
                minIndex = i;
                min = array[i];
             }//end if
          }//end for

        //  System.out.println("");
          return minIndex;
       }//========================================================================


    //=========================================================================
    /**
     * Swap emelement numbers j and iMin in array data.
     * @param j
     * @param iMin
     * @param data
     */
    //=========================================================================
    public static<T extends Comparable <? super T> > void swap(int j, int iMin, T[]  data){

         T temp = data[j];
         data[j] = data[iMin];
         data[iMin] = temp;
    }//end swap================================================================


    public static Integer[] largeRandom1, largeRandom2, largeRandom3;

    //========================================================================
    /**
     * Generate large integers for sorting.
     * @param n The value of n.
     */
    //========================================================================
    public static void genLargeRandom(int n){
        Random r = new Random();
        largeRandom1 = new Integer[n];
        largeRandom2 = new Integer[n];
        largeRandom3 = new Integer[n];


        for(int i = 0; i < n; i++){
            largeRandom1[i] = r.nextInt(100);
            largeRandom2[i] = largeRandom1[i];
            largeRandom3[i] = largeRandom1[i];
        }//end for
    }//end genLarge//==========================================================

    //=========================================================================
    /**
     * Sort a large numvber.
     * @param args
     */
    //=========================================================================
    public static void main(String[] args){

        genLargeRandom(100000);//one hundred thousand
        Integer[] data = largeRandom1;///{40, 3, 2, 7, 4}; 
        Integer[] data2 = largeRandom2;
        Integer[] data3 =  largeRandom3;


        System.out.println("BUBBLE SORT!!");
        Long t1s = System.nanoTime();
        bubbleSort(data);///////////////Bubble  Sort
        Long t1e = System.nanoTime();

        System.out.println("SELECTION SORT!!");
        Long t2s = System.nanoTime();
        selectionSort(data2, data2.length);///////////////Selection Sort
        Long t2e = System.nanoTime();


        System.out.println("INSERTION SORT!!");
        Long t3s = System.nanoTime();
        insertionSort(data3,0, data3.length);////////////Insertion Sort
        Long t3e = System.nanoTime();


        System.out.println("Bubble Time: " + (t1e - t1s));
        System.out.println("Selection Time: " + (t2e - t2s));
        System.out.println("insertion Time: " + (t3e - t3s));

        System.out.println("Bubble count: " + bubbleCount );
        System.out.println("Selection ccount :" + selectionCount );
        System.out.println("Insertion ccount :" + selectionCount );


    }//========================================================================

}//############################################################################

Answer 1

You've screwed up your bubble sort. Try to print the results for a simple input, and you'll see this clearly; for example, trying to sort (3, 2, 1) gives (2, 3, 1). You've misplaced the stop--:

public static <T extends Comparable <? super T> >void bubbleSort  (T[] data)
{
    Boolean swapped = true;
    int stop = data.length -1;


     while (swapped) {
        swapped = false;

        for (int x = 0; x < stop ; x++ ) {
             bubbleCount++;
            //if x smaller than x +1 swap
           if ( data[x].compareTo(  data[x+1]   ) > 0 ) { 

                  swap(x, x+1, data );
                  swapped = true;
           }//end if 

           stop --; // needs to go outside the for

       }//end for 

    }//end while
}//end  method============================================================