快速排序調試

-1

我試圖調試故意刪除重要行的quicksort版本，並且我無法理解它。快速排序調試

破碎的版本：

void quicksort(char *v [], int n) 
{ 
    int i, last; 
    if (n <= 1)       /* nothing to do */ 
     return; 
    last = 0; 
    for (i = 1; i < n; i++)   /* partition */ 
      if (strcmp(v[i],v[0]) < 0) 
       swap(v,++last, i); 
    swap(v, 0, last);     /* restore pivot */ 
    quicksort(v,last);    /* recursively sort each part. */ 
    quicksort(v+last-1, n-last-1); 
}

正確的版本：

void quicksort(char *v [], int n) 
{ 
    int i, last; 
    if (n <= 1)       /* nothing to do */ 
     return; 
    swap(v,0,rand() % n);  /* move pivot element to v[0] */ 
    last = 0; 
    for (i = 1; i < n; i++)   /* partition */ 
      if (strcmp(v[i],v[0]) < 0) 
       swap(v,++last, i); 
    assert((last >= 0) && (last < n)); 
    swap(v, 0, last);     /* restore pivot */ 
    quicksort(v,last);    /* recursively sort each part. */ 
    quicksort(v+last-1, n-last-1); 
}

正如你所看到的，第一個版本不包括第一次調用切換（）。當它以明文方式運行時，會引發段錯誤。

來源

2014-11-24 Zach

雖然你的問題是什麼？ – 2014-11-24 05:33:24

爲什麼需要第一次調用swap才能使函數正常運行。我認爲它可能會強制第二次調用quicksort移過數組v的邊界，但我不知道爲什麼。我也不知道你爲什麼可以給數組添加一個整數。 – Zach 2014-11-24 05:35:23

你的兩個快速排序都是錯誤的。這條線：

quicksort(v+last-1, n-last-1);

應該是：

quicksort(v+last+1, n-last-1);

我不明白爲什麼一個與rand()是任何一個比另一個更好，雖然。

來源

2014-11-24 07:05:13 JS1

快速排序調試

回答

相關問題