部分排序的大小爲500000的排序的快速排序分段錯誤

Question

我必須編寫並測試排序在25％，50％，75％，95％，99％和99.7％以及隨機填充的數組時的快排。當我使用大小爲500k的數組時，我的程序通過隨機數組和25％排序的數組沒有任何問題（但25％的排序數組需要它158s），但是對於50％的排序數組，它會引發分段錯誤和「返回過程139（0x8b）」。 「 對於較小的數組，例如100k，甚至排序，一切正常。 我如何生成（無需參數「zakres」，我知道）我的數組：

void generujTablice(int zakres,float sorted, int size_of_array) 
    { 
     Tablica = new int[size_of_array];   //allocating space for array 
     if(sorted == -1)       //when array have to be sorted, but inverted 
      for(int i=0;i<size_of_array;i++) 
       Tablica[i] = size_of_array-i; 
     else 
     { 
      for(int i=0;i<sorted * size_of_array;i++) //example: if sorted is 0.25 array have to be sorted in 25% from beginning 
       Tablica[i] = i; 
      for(int i=sorted * size_of_array;i<size_of_array;i++) //rest of array is filled randomly but values have to be bigger than these in sorted part of array 
       Tablica[i] = rand()%int(size_of_array)+sorted * size_of_array; 
     } 
    } 

我的快速排序： （注：我選擇的第一個元素爲支點，因爲我要檢查算法的最壞情況。我曾評論符合第一個元素隨機混合另外一個，當我用這個交換一切正常，非常非常快。離開路易==，prawy ==右）

#include <algorithm> 
void quicksort(int * Tablica, int lewy, int prawy) 
{ 
    if(lewy<prawy) 
    { 
     //swap(Tablica[lewy], Tablica[rand()%(prawy-lewy)+lewy]); 
     int x = Tablica[lewy]; 
     int i = lewy, j = prawy; 
     do{ 
      while(Tablica[i] < x) i++; 
      while(Tablica[j] > x) j--; 
      if(i<=j) swap(Tablica[i++], Tablica[j--]); 
     }while(i<=j); 
     quicksort(Tablica,lewy,j); 
     quicksort(Tablica,i,prawy); 
    } 
} 

我正在使用Ubuntu。我試圖谷歌什麼是錯的，但在我看來，我的算法幾乎與我發現的一些相同，所以我不知道如何解決它。 對不起，我的英語不幸，我不經常使用它。

感謝您的幫助。

Answer 1

我缺少一個範圍檢查或sentinel value這裏

while(Tablica[i] < x) i++; 
while(Tablica[j] > x) j--; 

因此，可能會在離開分配的邊界發生分段錯誤。

Answer 2

由於您選擇第一個元素作爲數據透視表，因此遞歸太深;你用盡了堆棧並崩潰並燃燒。對於大部分按排序順序排列的數據，您將對數組中的最小元素進行分區，因此您的QuickSort將在二次時間內運行。通過在較小的分區上遞歸，然後循環對較大的分區進行排序，可以提高代碼生存的可能性。

您可以通過檢查排序代碼來證明這一點，每次輸入排序時遞增並打印一個計數器，並在您離開時遞減計數器。隨着更小的陣列尺寸和更少的預先分類的材料，你不會太深;隨着大數組大小和更有序的數據，你只是溢出你的堆棧。

下面是一個使用最小的元素爲支點和C快速排序功能迭代和遞歸：

/* Fat pivot algorithm with tail recursion replaced by loop */ 
/* Pivot is low element */ 
static void fpquicksort3(Data a[], size_t low, size_t high) 
{ 
    sort_enter(__func__, a, low, high); 

    while (low + 1 < high) 
    { 
     Data pivot = a[low]; 
     size_t i = low + 1; 
     size_t j = high; 
     size_t k = high; 
     while (i < j) 
     { 
      inc_comps(); 
      if (a[i] < pivot) 
       i++; 
      else if (a[i] > pivot) 
      { 
       if (--j != --k || i != k || i != k) 
        sort_swap3(__func__, a, i, j, k); 
      } 
      else 
      { 
       if (i != --j) 
        sort_swap2(a, i, j); 
      } 
     } 
     if (low != --i) 
      sort_swap2(a, low, i); 
     if (i - low <= high - k) 
     { 
      if (i - low > 1) 
       fpquicksort3(a, low, i); 
      low = k; 
     } 
     else 
     { 
      if (k - high > 1) 
       fpquicksort3(a, k, high); 
      high = i; 
     } 
    } 
    sort_exit(__func__, a, low, high); 
} 

的sort_enter，sort_exit，sort_swap2，sort_swap3和inc_comps功能在這個代碼來自儀表掛鉤（他們做事情就像計算遞歸的深度）。