快速排序實現，找不到錯誤

我想用一些不同的樞軸策略來實現這種快速排序算法，但其中存在一些邏輯錯誤。你能幫我找到它嗎？快速排序實現，找不到錯誤

#include <iostream.h> 
#include<stdlib.h> 
#include<stdio.h> 
#include<conio.h> 
int arr[100],i,pivot,left,right,sum=0,a,n=10; 

int partition(); 
void quickSort(int* ,int ,int); 



void main() 
{ 
    clrscr(); 
    int i,n=20; 
    for(i=0;i<=n;i++) 
    { 
     arr[i]=rand()%100; 
    } 

    for(i=0;i<=n;i++) 
    { 
     cout<<"\t"<<arr[i]; 
    } 

    quickSort(arr,n,i); 

    for(i=1;i<n;i++) 
    { 
     cout<<"\n"<<arr[i]; 
    } 

    getch(); 
} 

int partition() 
{ 
    // int i; 
    // int sum=0; 
    // int pivot; 
    // stable_sort(arr,arr+3); 
    for(i=0;i<5;i++) 
    { 
     cout<<"\nsorted k elements\t"<<arr[i]; 
     // sum=sum+arr[i]; 
    } 
    // cout<<sum; 
    //cout<<"median is "<<sum/3; 
    pivot=arr[(i)/2]; 
    cout<<"pivotis value at position "<<pivot ; 
    return pivot; 
} 

void quickSort(int arr[],int left,int right) 
{ 
     partition(); 
     right=n,left=0; 
     int i = right, j =left; 

     int tmp; 
     int p=pivot; 
     cout<<" m array of p"<<p; 
     while (i <= j) { 
     while (arr[i] < p) 
      i++; 
     while (arr[j] > p) 
      j--; 
     if (i <= j) { 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    if (left < j) 
    { 
     quickSort(arr, left, j); 
    } 
    if (i < right) 
    { 
     quickSort(arr, i, right); 
    } 
}

來源

2011-04-13 james

你怎麼知道你有一個邏輯上的錯誤？你能提供一個小樣本輸入數據集的結果嗎？ – 2011-04-13 13:57:24

標題'沒有想法問題'沒有幫助你，所以我，呃 - 拋光它。你嘗試過調試嗎？找到錯誤？ – slezica 2011-04-13 13:58:22

我沒有在分區中聲明 – 2011-04-13 14:05:41

你的支點價值永遠是arr[(i)/2]的價值，這是arr[2]，不管你碰巧該陣列的一部分的時候被排序。將left和right的值傳遞給partition，以便知道當前調用quickSort需要考慮哪些值。

而且，left和right您傳遞的初始呼叫quickSort值是20和21，分別，這肯定不是你預期什麼。你有一個長度爲100的數組，並且你已經初始化了前21個元素，所以你可能想要爲這些參數傳遞0和21。

但你可能應該做的，如果你想與一個不同樞紐戰略，以測試快速排序的第一件事，是得到它的工作第一有典型支點策略，如一個在教科書證明。從開始工作的實施，只有然後應該開始試驗變化。您應該能夠在教科書或課堂筆記中找到工作實施。

來源

2011-04-13 14:00:34

謝謝。但是你能否告訴我是否已經在不同的函數之間正確傳遞了值（函數參數）。或者在調用這些函數時？ – james 2011-04-13 14:22:25

當你調用'quickSort'時，唯一的地方就是將*值傳遞給任何東西。我已經告訴過你在第一次通話時傳遞了錯誤的值。如果你正確計算'i'和'j'，那麼我認爲遞歸調用可能是好的，但你不是。（'j'開始等於'left'，並且之後所做的所有事情都會減少它;當你確實希望它會變得更大*然後是'left'？）你沒有傳遞任何*值到'分區'，這是這個代碼中的許多問題之一。 – 2011-04-13 14:45:45

我沒有找到任何地方比較數組中的值。

我想你應該檢查這個地方：

if (i <= j) { 
     tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
     i++; 
     j--; 
    }

也許應該是：

if (arr[i] < arr[j]) { 
     tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
     i++; 
     j--; 
    }

來源

2011-04-13 14:02:55 Elalfer

快速排序實現，找不到錯誤

回答

相關問題