QuickSortのピボットの選択

Question

私はコードを見つけました。しかし、私はそれがどのように機能しているのか理解していません。 私はピボットを知っている - その配列の中間要素。 しかしここでピボットはint pivot = quickSortArray[p]です。int i = pなので、p = 0と0です。これは配列の真中ではありません。

public int partition(int p, int q) { 
    int i = p; 
    int j = q + 1; 
    // Get the pivot element from the middle of the list 
    int pivot = quickSortArray[p]; 
    // Divide into two lists 
    do { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     do { 
      i++;// As we not get we can increase i 
     } while (quickSortArray[i] < pivot && i<q); 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     do { 
      j--;// As we not get we can increase j 
     } while (quickSortArray[j] > pivot); 
     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     if (i < j) { 
      swap(i, j); 
     } 

    } while (i < j); 
    // swap the pivot element and j th element 
    swap(p, j); 
    quickSortComparisons++; 
    return j; 

} 

private void swap(int p, int j) { 
    // exchange the elements 
    int temp = quickSortArray[p]; 
    quickSortArray[p] = quickSortArray[j]; 
    quickSortArray[j] = temp; 
    quickSortSwaps++; 
} 

public void quicksort() { 
    // Recursion 
    quicksort(0, quickSortCounter - 1); 
} 

public void quicksort(int p, int q) { 
    int j; 
    if (p < q) { 
     // Divide into two lists 
     j = partition(p, q); 
     // Recursion 
     quicksort(p, j - 1); 
     quicksort(j + 1, q); 
    } 
    quickSortComparisons++; 
} 

Answer 1

ピボットは中間要素である必要はありません。ただランダムな要素でなければなりません。このコードはピボットを常に最初の要素にすることでコードを簡単にします。降順でソートされた配列を持つ場合、O(n log n)ではなくO(n^2)が必要になるため、最適ではありません。最適なのは、要素をランダムに選択することです。