L'implementazione di quicksort sembra richiedere più tempo rispetto a Mergesort

Question

Stavo cercando di implementare QuickSort (con mediana di 3 elementi di partizionamento e di inserimento per piccoli array) e confrontarlo con un'implementazione di MergeSort, ma anche quando Il tempo medio di QuickSort dovrebbe essere migliore di quello di MergeSort, ogni volta che lo eseguo, sembra che ci voglia più tempo per ordinare un array (anche uno in ordine casuale). Qualche idea sul perché questo possa accadere?

QuickSort:

public class Quick { 

    private static final int M = 10; 
    private static Random random = new Random(); 

    public void sort(int[] a) { 
     sort(a, 0, a.length - 1); 
     insertionSort(a, 0, a.length - 1); 
    } 

    private void sort(int[] a, int lo, int hi) { 
     if (hi - lo <= 10) return; 
     swap(a, lo, pivot(a, lo, hi)); 
     int lt = lo, gt = hi; 
     int v = a[lo]; 
     int i = lo; 
     while (i <= gt) { 
      if  (a[i] < v) swap(a, lt++, i++); 
      else if (a[i] > v) swap(a, i, gt--); 
      else    i++; 
     } 

     // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
     sort(a, lo, lt-1); 
     sort(a, gt+1, hi); 
    } 

    private int pivot(int[] a, int lo, int hi) { 
     int  r1 = random.nextInt(hi - lo) + lo, 
       r2 = random.nextInt(hi - lo) + lo, 
       r3 = random.nextInt(hi - lo) + lo; 
     return median3(a, r1, r2, r3); 
    } 

    private void swap(int[] a, int i, int j) { 
     if (i == j) return; 
     int tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = tmp; 
    } 

    private static int median3(int[] a, int i, int j, int k) { 
     return (a[i] < a[j] ? 
       (a[j] < a[k] ? j : a[i] < a[k] ? k : i) : 
       (a[k] < a[j] ? j : a[k] < a[i] ? k : i)); 
    } 

    private void insertionSort(int[] a, int lo, int hi) { 
     for (int i = lo; i <= hi; i++) 
      for (int j = i; j > lo && a[j] < a[j-1]; j--) 
       swap(a, j, j-1); 
    } 
} 

MergeSort:

public class Merge { 

    public void sort(int[] a) { 
     int[] aux = new int[a.length]; 
     sort(a, aux, 0, a.length - 1); 
    } 

    private void sort(int[] a, int[] aux, int lo, int hi) { 
     if (hi <= lo) return; 
     int mid = lo + (hi - lo)/2; 
     sort(a, aux, lo, mid); 
     sort(a, aux, mid + 1, hi); 
     merge(a, aux, lo, mid, hi); 
    } 

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) { 
     System.arraycopy(a, lo, aux, lo, hi + 1 - lo); 
     // Merge 
     int i = lo, j = mid + 1; 
     for (int k = lo; k <= hi; k++) { 
      if  (i > mid)   a[k] = aux[j++]; 
      else if (j > hi)   a[k] = aux[i++]; 
      else if (aux[j] < aux[i]) a[k] = aux[j++]; 
      else      a[k] = aux[i++]; 
     } 
    } 
} 

Ad esempio, quando eseguito questo algoritmi per 10 matrici casuali di lunghezza 10^8, MergeSort ha una media di 13385.8 ms per eseguire, mentre QuickSort ha una media di 14096,7 ms.

Per chiarire, questo è il modo ho misurato i tempi di esecuzione

public static void main(String[] args) { 
    int pow = (int) Math.pow(10, 8); 
    int[] a, b; 
    double[] m1 = new double[10], 
       m2 = m1.clone(), 
    double st, et; 
    Merge merge = new Merge(); 
    Quick quick = new Quick(); 
    for (int i = 0; i < 10; i++) { 
     a = randomArray(pow); 
     b = a.clone(); 
     st = currentTimeMillis(); 
     merge.sort(a); 
     et = currentTimeMillis(); 
     m1[i] = et - st; 
     st = currentTimeMillis(); 
     quick.sort(b); 
     et = currentTimeMillis(); 
     m2[i] = et - st; 
    } 
    out.println("MergeSort: " + mean(m1)); 
    out.println("QuickSort: " + mean(m2)); 
} 
private static int[] randomArray(int n) { 
    r = new Random(); 
    int[] a = new int[n]; 
    for (int i = 0; i < a.length; i++) a[i] = r.nextInt(); 
    return a; 
} 

Answer 1

Dopo aver provato un sacco di cose per scoprire dove il problema è stato, ho cambiato la funzione che ha creato l'array casuale, e si scopre QuickSort attualmente funziona più velocemente ora. Non so davvero perché, ma sembra che il modo in cui ho creato l'array abbia influito negativamente sulle prestazioni di QuickSort. Ora, quello che ho fatto è stato che invece di generare un array di interi casuali, ho generato una forma di matrice 1 a n e, mischia, come segue:

public static int[] permutation(int n) { 
    int[] a = new int[n]; 

    for (int i = 0; i < n; ++i) a[i] = i + 1; 

    for (int i = 0; i < n; i++) { 
     int r = i + rnd.nextInt(n - i), 
      tmp = a[i]; 

     a[i] = a[r]; 
     a[r] = tmp; 
    } 

    return a; 
}