-1

配列サイズに挿入ソートを使用するクイックソートアルゴリズムの修正バージョンを実装するいくつかの実用的なコードを次に示しますn > 8。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);
                }
            }
        }
    }
}
4

2 に答える 2

1

3つの配列要素を昇順でソートすることになっている関数は、次のことを行いません。

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);
            }

おけどけ。

        }
        else
        {

b < a <= c

            exchange(list,p,median);

わかった。

        }

    }


    return list[r];
}

この関数が何かを返すのはなぜですか？とにかく戻り値を使用しません。

于 2012-11-21T16:29:05.390 に答える
0

「再帰的挿入ソートアルゴリズムの一般的な形式は」です。ヘッド再帰的アルゴリズムが必要な場合はそうです。そうでない場合は、次のようになります。

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

これははるかに理解しやすいです。また、Insertの本体をInsertionsortに入れた方がよいでしょう。

非常に複雑なバージョンのクイックソートを理解しようとはしません。適切なクイックソートは約20行以下です（このように-www.algolist.net/Algorithms/Sorting/Quicksort）（挿入ソート用にさらに10行以下を追加します）。別の実装を見て、自分の実装を書き直すことで、理解を深めることをお勧めします。

これはあなたの前の質問の延長として尋ねられたかもしれないと私は信じます。

于 2012-11-21T14:10:39.500 に答える