使用插入排序算法 - 數組排序不準確。

-1

下面是一些工作代碼，它實現了對數組大小n > 8使用Insertion Sort的Quicksort算法的修改版本。我的測試數組排序不完全正確，我認爲它必須與我的實施Insertionsort和Insert。使用插入排序算法 - 數組排序不準確。

遞歸Insertionsort算法的一般形式是：

void Insertionsort(int S[], int n) 
{ 
     if(n>1) 
       Insertionsort(S,n-1); 
     Insert(S,n-1); 

} 

void Insert(int *S, int k) 
{ 
     int key = S[k]; 
     int j = k-1; 
     while(j>=0 && S[j] > key) 
     { 
       S[j+1] = S[j]; 
       j--; 
     } 

     S[j+1] = key; 
}

這裏是我完整的工作代碼，不排序相當完全正確：

#include <iostream> 
#include <string> 
#include <stdlib.h> 
using namespace std; 


int comparisons = 0;    
int compare_qs_m3_ins[12]; 


// Function prototypes 
int partition(int *S,int l, int u);           
void exchange(int list[], int p, int q); 
void Insert(int S[], int k);             
void Insertionsort(int S[], int low, int hi);       
void Quicksort_Insert_M3(int S[], int n, int p, int r);  



int main() 
{ 
    srand (time(NULL)); 
    // Declare all arrays used for testing 
    int S1_500[500]; 
    int S2_500[500]; 
    int S3_500[500]; 


    int S1_300[300]; 
    int S2_300[300]; 
    int S3_300[300]; 

    int S1_100[100]; 
    int S2_100[100]; 
    int S3_100[100]; 

    int S1_8[8]; 
    int S2_8[8]; 
    int S3_8[8]; 




    // Fill arrays with random integers 
    for(int i=0; i<500; i++) 
    { 
     S1_500[i] = rand()%1000; 
     S2_500[i] = rand()%1000; 
     S3_500[i] = rand()%1000; 
    } 


    for(int i=0; i<300; i++) 
    { 
     S1_300[i] = rand()%1000; 
     S2_300[i] = rand()%1000; 
     S3_300[i] = rand()%1000; 
    } 


    for(int i=0; i<100; i++) 
    { 
     S1_100[i] = rand()%500; 
     S2_100[i] = rand()%500; 
     S3_100[i] = rand()%500; 
    } 

    for(int i=0; i<8; i++) 
    { 
     S1_8[i] = rand()%100; 
     S2_8[i] = rand()%100; 
     S3_8[i] = rand()%100; 
    } 

    Quicksort_Insert_M3(S1_500,500,0,499); 
    compare_qs_m3_ins[0] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S2_500,500,0,499); 
    compare_qs_m3_ins[1] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S3_500,500,0,499); 
    compare_qs_m3_ins[2] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S1_300,300,0,299); 
    compare_qs_m3_ins[3] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S2_300,300,0,299); 
    compare_qs_m3_ins[4] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S3_300,300,0,299); 
    compare_qs_m3_ins[5] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S1_100,100,0,99); 
    compare_qs_m3_ins[6] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S2_100,100,0,99); 
    compare_qs_m3_ins[7] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S3_100,100,0,99); 
    compare_qs_m3_ins[8] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S1_8,8,0,7); 
    compare_qs_m3_ins[9] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S2_8,8,0,7); 
    compare_qs_m3_ins[10] = comparisons; 
    comparisons = 0; 
    Quicksort_Insert_M3(S3_8,8,0,7); 
    compare_qs_m3_ins[11] = comparisons; 
    comparisons = 0; 

    //for(int i=0; i<12; i++) 
     //cout << compare_qs_m3_ins[i] << endl; 



    for(int i=0;i<499;i++) 
     cout << S1_500[i] << endl; 





} 



int partition(int *S,int l, int u) 
{ 
    int x = S[l]; 
    int j = l; 
    for(int i=l+1; i<=u; i++) 
    { 
     comparisons++; 
     if(S[i] < x) 
     { 
      j++; 
      swap(S[i],S[j]); 
     } 

    } 
    int p = j; 
    swap(S[l],S[p]); 
    return p; 
} 

void swap(int &val1, int &val2) 
{ 
    int temp = val1; 
    val1 = val2; 
    val2 = temp; 
} 


void exchange(int list[], int p, int q) 
{ 
    int temp = list[p]; 
    list[p] = list[q]; 
    list[q] = temp; 
} 


int Sort3(int list[], int p, int r) 
{ 
    int median = (p + r)/2; 
    comparisons++; 
    if(list[p] <= list[median]) 
    { 
     comparisons++; 
     if(list[median]>list[r]) 
     { 
      comparisons++; 
      if(list[p]<list[r]) 
      { 
       int temp = list[p]; 
       list[p] = list[r]; 
       list[r] = list[median]; 
       list[median] = temp; 
      } 
      else 
      { 
       exchange(list,median,r); 
      } 
     } 
     else 
      ; 

    } 
    else 
    { 
     comparisons++; 
     if(list[p] > list[r]) 
     { 
      comparisons++; 
      if(list[median] < list[r]) 
      { 
       int temp = list[p]; 
       list[p] = list[median]; 
       list[median] = list[r]; 
       list[r] = temp; 
      } 
      else 
      { 
       exchange(list,p,r); 
      } 
     } 
     else 
     { 
      exchange(list,p,median); 
     } 

    } 


    return list[r]; 
} 


void Insert(int *S, int k) 
{ 
    int key = S[k]; 
    int j = k-1; 
    while(j>=0 && S[j] > key) 
    { 
     S[j+1] = S[j]; 
     j--; 
     comparisons++; 
    } 
    comparisons++; 
    S[j+1] = key; 
} 


void Insertionsort(int S[], int low, int hi) 
{ 
    if((hi-low)+1>1) 
     Insertionsort(S,low+1,hi); 
    Insert(S,hi-low); 

} 


void Quicksort_Insert_M3(int S[], int n, int low, int hi) 
{ 
    if((hi-low)<=8) 
     Insertionsort(S,low,hi); 
    else 
    { 
     if(low < hi) 
     { 
      if((low+1) == hi) 
      { 
       comparisons++; 
       if(S[low] > S[hi]) 
        swap(S[low],S[hi]); 
      } 
      else 
      { 
       Sort3(S,low,hi); 
       if((low+2)<hi) 
       { 
        swap(S[low+1],S[(low+hi)/2]); 
        int q = partition(S, low+1, hi-1); 
        Quicksort_Insert_M3(S, n, low, q-1); 
        Quicksort_Insert_M3(S, n, q+1, hi); 
       } 
      } 
     } 
    } 
}

來源

2012-11-21 Zack

您是否試過單步執行代碼？每次工作！（如果你知道在任何給定的行會發生什麼） – keyser

實際上，我運行了一個小測試用例，'Insertionsort'函數可以工作。它實際上是我的'Quicksort_Insert_M3'的實現，不是 - 不知道在哪裏。 – Zack

我建議在插入for循環中替換while循環...因爲您正在執行for循環。 – Dukeling

應該按升序順序的三個數組元素進行排序的功能不：

int Sort3(int list[], int p, int r) 
{

只調用了p + 2 <= r，所以

int median = (p + r)/2;

p < median < r這裏。讓a = list[p],b = list[median]和c = list[r]。

comparisons++; 
    if(list[p] <= list[median]) 
    { 
     comparisons++; 
     if(list[median]>list[r]) 
     { 
      comparisons++; 
      if(list[p]<list[r]) 
      {

所以在這裏我們有a <= b，c < b和a < c，一起a < c < b

   int temp = list[p]; 
       list[p] = list[r]; 
       list[r] = list[median]; 
       list[median] = temp;

，但將它們放在順序c, a, b。可能你打算在那裏使用if (list[r] < list[p])。

  } 
      else

c <= a <= b

  { 
       exchange(list,median,r);

使它們排列爲了a, c, b。

  } 
     } 
     else 
      ; 

    } 
    else

這裏，b < a。

{ 
     comparisons++; 
     if(list[p] > list[r]) 
     {

c < a

  comparisons++; 
      if(list[median] < list[r]) 
      {

然後b < c < a

   int temp = list[p]; 
       list[p] = list[median]; 
       list[median] = list[r]; 
       list[r] = temp;

是啊，這是正確的。

  } 
      else

c <= b < a

  { 
       exchange(list,p,r); 
      }

Okedoke。

 } 
     else 
     {

b < a <= c

  exchange(list,p,median);

好。

 } 

    } 


    return list[r]; 
}

爲什麼這個函數返回什麼？無論如何你都不使用返回值。

來源

2012-11-21 16:29:05

謝謝你發現錯誤 - 這是正確的。另外，我將它改爲'void'函數 - 不需要返回值。 – Zack

「遞歸插入排序的一般形式算法是「 - 如果您需要頭部遞歸算法，是的，否則更好的版本是：

void Insertionsort(int S[], int i, int n) 
{ 
    Insert(S, i, n); 
    if(i < n) 
     Insertionsort(S, i+1, n); 
}

這更容易理解。另外，你也可以將Insert的主體放入Insertionsort。

我不打算試圖弄清楚你的quicksort過於複雜的版本。一個體面的快速排隊大約20行或更少（像這樣 - www.algolist.net/Algorithms/Sorting/Quicksort）（並且爲插入排序再添加10個或更少）。我建議通過查看另一個實現並重寫你的實現來獲得更好的理解。

我相信這可能是作爲您的previous question的擴展。

來源

2012-11-21 14:10:39 Dukeling

使用插入排序算法 - 數組排序不準確。

回答

相關問題