Dlaczego mój Bubble oparty na Javie sortuje przewyższające moje sortowanie sortowanie i mój sortowanie wsunięcia

Question

Ok, więc mam implementację sortowania bąbelkowego, sortowania sortowania i sortowania wstawiania. Używam obiektu Java.Random do utworzenia trzech identycznych tablic ze stu tysięcy liczb. Przekazuję je kolejno do każdej metody sortowania. Czas na wyniki przy użyciu System.nanotime.

Dla niektórych informacji dodatkowych. Algorytmy sortowania, które stosowałem do sortowania i wstawiania, pochodzą z "Struktury danych i abstrakcji" autorstwa Franka Carano z trzeciej edycji Java. Bąbelkowy rodzaj był w mojej głowie.

Poniżej przedstawiam samodzielną klasę, która wykonuje to wszystko. Gdzie algorytmy Carana poszły nie tak, nie widzę?

Poniżej zobaczysz liczę cykle operacji podstawowych i czas zakończenia. W czasie wykonywania liczba cykli jest nieznacznie inna. Dla mnie, gdy patrzysz na czas ukończenia, Bubble jest 1st, Selection jest 2nd, a Insertion 3rd. To leci w obliczu konwencjonalnej mądrości. Czemu. Czy zrobiłem coś raczej głupiego?

BTW powinieneś być w stanie skompilować i uruchomić dostarczony kod bez żadnych zmian.

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

Spieprzyłeś sortowanie bąbelków. Spróbuj wydrukować wyniki dla prostych danych wejściowych, a zobaczysz to wyraźnie; na przykład próbowanie sortowania (3, 2, 1) daje (2, 3, 1). Zgubiłeś się 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============================================================