So, I have an implementation for sorting bubbles, sorting sorting, and sorting inserts. I use the Java.Random object to create three identical arrays of one hundred thousand numbers. I pass them to each sorting method in turn. I use System.nanotime in the search results.
For some background information. The sorting algorithms that I performed to sort the selection and insertion are taken from Frank Carano "Data Structures and Abstraction in Java 3rd Ed." The bubble variety was on my head.
Below I provide a separate class that does all this. Where are the Carano algorithms wrong, I do not see this?
Below you will see that I am calculating the cycles of basic operations and the completion time. At run time, the number of cycles is negligible. For me, looking at the completion time, Bubble is 1st, Selection is 2nd, and Insertion is 3rd. It flies before ordinary wisdom. What for. Did I do something pretty stupid?
By the way, 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 ); }//======================================================================== }//