【分治法】集計分類

集計アルゴリズムの基本的な実装:

集計ソートは集計操作に確立された有効なソートアルゴリズムであり,このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.時間の複雑さはΘ(nlgn).集計ソートの手順は、次のとおりです.
1.Divide:長さnの入力シーケンスを2つの長さn/2のサブシーケンスに分ける.
2.Conquer:この2つのサブシーケンスは、それぞれ集計ソートを使用します.
3.Combine:2つの並べ替えられたサブシーケンスを1つの最終的な並べ替えシーケンスに結合します.
集計ソートの手順を説明するときに集計ソート自体が呼び出されます.これは再帰的なプロセスであることがわかります.
したがって、集計ソートの基本的な実装コード:

#include <stdio.h>

//merge the two sequential array lists to the temp array ascend

//param:array     the original array

//param:first,mid,last    the index of the original data

//param:temp     the temporary array for the sorting

void MergeArray(int array[], int first, int mid, int last, int temp[])

{

    int i = first;

    int m = mid;

    int j = mid + 1;

    int n = last;

    

    int k = 0;

    

    while(i <= m && j <= n)

    {

        if(a[i] < a[j])

        {

            temp[k++] = a[i++];

        }

        else

        {

            temp[k++] = a[j++];

        }

    }//while

    

    //copy the remainder data to the temp array

    while(i <= m)

    {

        temp[k++] = a[i++];

    }

    while(j <= n)

    {

        temp[k++] = a[j++];

    }

    

    //copy the data from the temp array to the original array.

    for(int i = 0; i < k; i++)

    {

        a[first + i] = temp[i];

    }

    

}//MergeArray()



void MergeSort_Inner(int array[], int first, int last, int temp[])

{

    if(first < last)

    {

        int mid = (first + last) / 2;

        MergeSort(array, first, mid, temp);

        MergeSort(array, mid + 1, last, temp);

        MergeArray(array, first, mid, last, temp);

    }

}//MergeSort_Inner()



bool MergeSort(int array[], int n)

{

    int *p = new int[n];

    if(p == NULL)

    {

        return false;

    }

    MergeSort_Inner(array, 0, n - 1, p);

    delete[] p;

    

    return true;

}//MergeSort()

 

集計ソートアルゴリズムの改良:

上記のアルゴリズムから、集合が2つの要素のみを含むサブ集合に分割されるたびに、サブ集合を単一の要素の集合に分割するために2回の再帰呼び出しを使用する必要がある.これはアルゴリズムが実際の分類ではなく処理再帰に多くの時間を費やすことを示している.再帰呼び出しの深さを少なくするために,SMALL(p,q)が入力規模q−p+1が適切に小さい場合に,小規模集合上で効率的に並べ替えられる分類アルゴリズムを採用すれば,下位再帰呼び出しによる消費過大の問題を克服できる.ここでは挿入ソートを選択し,このアルゴリズムの時間的複雑度はO(n 2)であるが,nが小さい(例えば16)場合には極めて迅速に動作できる.
もう1つの問題は、補助配列temp[]が使用されていることです.問題は、追加のストレージスペースを占有していることではなく、temp[]に格納されているデータを元の配列にコピーするのに時間がかかることです.解決策は,整数で表されるリンク情報配列LINK[]を用いて元の配列のソートを記録することである.