集計ソートとクイックソート

6064 ワード

ぶんかつほう
多くのアルゴリズムは構造的に再帰的である:与えられた問題を解決するために、アルゴリズムは、関連するサブ問題を解決するために、自身を1回または複数回再帰的に呼び出す必要がある.これらのアルゴリズムは通常、分治戦略(divide-and-conquier)を採用する:原問題をn個の規模が小さく、構造が原問題に似ているサブ問題に分割する.これらのサブ問題を再帰的に解決し,その後その結果を統合すると,元の問題の解が得られる.分治モードには、各階層の再帰に3つのステップがあります.
²分解(divide):元の問題を一連のサブ問題に分解する.
²解決(conquer):各サブ問題を再帰的に解く.サブ問題が十分に小さい場合は、直接解く.
²≪マージ|Merge|emdw≫:サブ問題の結果を元の問題の解にマージします.
下から上への集計ソート
集計ソートアルゴリズムは完全に分治モードに従い、直感的な操作は以下の通りである.
²分解:n個の要素をn/2個の要素を含む各サブシーケンスに分割する.
²解決:集計ソート法で2つのサブシーケンスを再帰的にソートします.
²≪マージ|Merge|emdw≫:ソートされた2つのサブシーケンスをマージして、ソート結果を取得します.
以下の例を観察すると,集計ソートは分解時に単純に原問題を2つの規模が半減したサブ問題に分解するだけであることが分かった.分解の過程で、元の問題に含まれる情報の利用は何もなく、問題を解く動作を試みることは何もない.この分解は、サブ問題の規模が十分に小さくなるまで(1)、サブ問題が直接解かれる.そして,サブ問題の解を底から上へ結合すると,そのときになって初めて,元の問題の特定情報を真に利用して解を求める動作を実行し,要素を比較する.
4 2 5 7 1 2 6 3
4 | 2 | 5 | 7   |   1 | 2 | 6 | 3
4 2 5 7   |   1 2 6 3
2 4 | 5 7   |   1 2 | 3 6
4 2 | 5 7   |   1 2 | 6 3
2 4 5 7   |   1 2 3 6
4 | 2 | 5 | 7   |   1 | 2 | 6 | 3
1 2 2 3 4 5 6 7
このような下から上への分治戦略のプログラミングモードは以下の通りである.
もし問題の規模が十分に小さいならば、直接解いて、さもなくば単純に元の問題を分解して規模のもっと小さいサブ問題で、そしてこのような分解を続けます;解を求める動作を行い,サブ問題の解を元の問題の解に統合する.
下から上への集計過程において,各層はi群n/i回の比較を行う必要があり,単純な対称分解を行うため,総層数は常にlg nであるため,集計ソートの様々な場合の時間的代価はΘ(n lg n).考えてみると、グループ化に力を入れることができます.つまり、元の問題を毎回2より大きいサブ問題に分解して、運行時間を下げることができますか?
次のプログラムの巧みな点は、彼は2つの半分の配列をすべて2つの新しい配列の中にコピーして、各配列は元のより1つの位置が多くて、この多くの位置は何に使いますか?
歩哨を置くためのもので、歩哨というのは配列の中より明らかに大きな要素なので、二つの配列を一つの大きな配列にコピーするときは、二つの配列の下付きを制御する必要はありません.一つが境界を越えているかどうかを判断する必要はありません.どの配列が残っているかを判断して、すべてコピーすると、このプログラムの論理が非常に簡単になります.

#include<stdio.h>
#include<stdlib.h>
#define INFINITE 1000

//         ,   mid  
// a[start...mid] a[mid+1...end]    
void merge(int *a,int start,int mid,int end)
{
    int i,j,k;
    //      
    int *array1=(int *)malloc(sizeof(int)*(mid-start+2));
    int *array2=(int *)malloc(sizeof(int)*(end-mid+1));

    // a mid         
    for(i=0; i<mid-start+1; i++)
        *(array1+i)=a[start+i];
    *(array1+i)=INFINITE;//    
    for(i=0; i<end-mid; i++)
        *(array2+i)=a[i+mid+1];
    *(array2+i)=INFINITE;
    //        a 
    i=j=0;
    for(k=start; k<=end; k++)
    {
        if(*(array1+i) > *(array2+j))
        {
            a[k]=*(array2+j);
            j++;
        }
        else
        {
            a[k]=*(array1+i);
            i++;
        }
    }
    free(array1);
    free(array2);
}

//    
void mergeSort(int *a,int start,int end)
{
    int mid=(start+end)/2;
    if(start<end)
    {
        //  
        mergeSort(a,start,mid);
        mergeSort(a,mid+1,end);
        //  
        merge(a,start,mid,end);
    }
}

int main()
{
    int i;
    int a[7]= {0,3,5,8,9,1,2}; //   a[0]
    mergeSort(a,1,6);
    for(i=1; i<=6; i++)
        printf("%-4d",a[i]);
    printf("
");
    return 1;
}

次のプログラムは私が自分で書いたものです.中には当時多くの間違いがあり、注釈で表明されていました.

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include<time.h>
#define random(x) (rand()%x)
using namespace std;

void MergeSort( int* a, int start, int end);
void  merge(int *a,int start,int mid,int end);

void printArray(int a[],int n)
{
    for(int i =0; i<n; i++)
    {
        cout<< a[i]<<" ";
    }
}
int main()
{
    while(true){
     system("cls");

    time_t t;
    int a[10]= {0};
    srand((unsigned) time(&t));
    for(int i =0; i<=9; i++)
    {
        a[i]= random(100);
    }

    //int a[10]={6,2,3,8,4,1,7,9,0,5};
    cout<<"    ："<<endl;
    printArray(a,10);
    MergeSort(a,0,9);
    cout<<endl<<"      ："<<endl;
    printArray(a,10);

    //int a[]  = {28,28,18};
    //merge(a,0,1,2);
    //printArray(a,3);
    cin.get();
    }
    return 0;
}
void MergeSort( int* a, int start, int end)
{

    if(start < end)
    {
        //      
        int mid = (start + end )/2;

        MergeSort(a,start,mid);
        MergeSort(a,mid+1,end);
        merge(a,start,mid,end);
    }



}

void merge(int *a,int start,int mid,int end)
{
    int low,high;
    low = start;
    high = mid + 1;

    int *temp= new int[end - start + 1];
    int * ptr = temp;
    memset(temp,0,sizeof(temp));

    while( (low<mid+1) && (high < end +1) )
    {
        if (a[low]< a[high])
        {
            *ptr = a[low];
            low ++;
            ptr++;
        }
        else
        {
            // *temp++ = a[high++];
            *ptr = a[high];
            high++;
            ptr++;

        }
    }
    if (low > mid)
    {
        while(high < end +1)
        {
            *ptr++ = a[high++];
        }


    }
    else if (high > end)
    {
        //        
        while(low<mid +1)
        //   
        *ptr++ = a[low++];
    }

    for(int j =start; j<=end; j++)
        //    temp      
        a[j] = temp[j-start];

    delete []temp;
}

上から下への高速ソート
迅速なソートも、次の3つのステップに基づいています.
²分解:配列A[p..r]は、A[p..q-1]とA[q+1..r]の2つの(空の可能性がある)サブ配列A[p..q-1]とA[q+1..r]に分割され、A[p..q-1]の各要素がA(q)以下であり、A[q+1..r]の要素以下であり、下付きqもこの分解過程で計算される.
²解決:再帰呼び出しによる高速ソートにより、サブ配列A[p..q-1]とA[q+1..r]をソートする.
²マージ:2つのサブ配列がその場でソートされているため、それらのマージを操作する必要はありません.A[p..r]全体がソートされています.
高速ソートは集計ソートとは異なり、元の問題に対して単純な対称分解を行うことが明らかになった.その解動作は分解サブ問題の開始前に行われ、問題の分解は元の問題自体に含まれる情報に基づいている.次に,各サブ問題を上から下へ再帰的に解く.次の例では、高速ソートの実行手順を観察できます.高速ソート中に比較に基づいていない位置交換が存在するため,高速ソートは不安定である.
4 2 5 7 1 2 6 | 3
2 1 2   |   3   |   7 4 5 6
1 | 2 | 2   |   3   |   4 5 | 6 | 7
1 | 2 | 2   |   3   |   4 | 5 | 6 | 7
このようなトップダウン分治戦略のプログラミングモードは以下の通りである.
問題の規模が十分に小さい場合、直接解く.そうしないと、解く動作を実行し、元の問題をより規模の小さいサブ問題に分解する.各サブ問題を再帰的に解く.解を求める動作は分解の前に行われるため,各サブ問題を解いた後,プロセスを統合する必要はない.
高速ソートの実行時間は、分解が対称かどうかに関係し、後者は、どの要素を選択して分割するかに関係します.分割が対称である場合、実行時間は集計ソートと同じで、Θ(n lg n).分解のたびにn-1と0の2つのサブ問題が発生すると、高速ソートの実行時間はΘ(n2).高速ソートの平均実行時間は、最適な場合と同じです.Θ(n lg n).

古典的な循環構造の例題の新しいアルゴリズム

コマンドラインCDコマンドの実装