【アルゴリズム導論】分治法及び集計ソート

多くのアルゴリズムは、構造的に再帰的である.与えられた問題を解決するために、アルゴリズムは、関連するサブ問題を解決するために、1回または複数回の再帰呼び出しを必要とし、このようなアルゴリズムは通常、分治戦略を採用する.
分治法の基本思想:
(1).原問題==(区分)=>>いくつかのより小規模なサブ問題.
(2).要求サブ問題の解法は元の問題と同じである.
分治法の解法手順:
(1)分解(Divide):現在の問題をいくつかのサブ問題に分割する
(2)解決(Conquer):サブ問題を再帰的に解き,サブ問題が十分小さい場合は直接解く.
(3)連結(Combine):サブ問題の解を長原問題に連結する
分割法の例、集計ソート:

/*
《Introduction to Algorithms(second edition)》
 chapter2，MERGE_SORT()
date：2014-9-18
*/

#include 
#include 
#include 
#include 

#define MAX 50

typedef struct
{
	int arr[MAX+1];
	int length;
}SortArr;

SortArr *CreateSortArr()
{
	int i = 0;
	char buf[4*MAX] = "";
	char *ptr = NULL;
	SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr));
	memset(sortArr, 0, sizeof(SortArr));

	printf("        ，     ，     
"
		" ：23,12,65,36,35;
"
		"input:");
	scanf("%s", buf);

	ptr = buf;
	sortArr->arr[i] = 0;	//arr[0]         
	i = 1;
	while(*ptr != ';')
	{
		sortArr->arr[i] = atoi(ptr);
		i++;

		ptr = strstr(ptr, ",");
		if(!ptr)
		{
			break;
		}
		ptr++;
	}
	sortArr->length = (i - 1);

	return sortArr;
}

int merge(int arr[], int p, int q, int r)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int n1 = 0;
    int n2 = 0;
    int *leftArr = NULL;
    int *rightArr = NULL;

    n1 = q - p + 1;
    n2 = r - q;

    //   arr[]      ，leftArr[0] rightArr[0]  
    leftArr = (int *)malloc((n1 + 2) * sizeof(int));
    rightArr = (int *)malloc((n2 + 2) * sizeof(int));

    for(i = 1; i <= n1; i++)
    {
        leftArr[i] = arr[p+i-1];
    }
    for(j = 0; j <= n2; j++)
    {
        rightArr[j] = arr[q+j];
    }

    i = 1;
    j = 1;

    //           
    leftArr[n1+1] = INT_MAX;
    rightArr[n2+1] = INT_MAX;

    for(k = p; k <= r; k++)
    {
        if(leftArr[i] <= rightArr[j])
        {
            arr[k] = leftArr[i];
            i++;
        }
        else
        {
            arr[k] = rightArr[j];
            j++;
        }
    }

    free(leftArr);
    free(rightArr);
    return 0;
}

int mergeSort(int arr[], int p, int r)
{
    int q = 0;

    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, (q+1), r);
        merge(arr, p, q, r);
    }

    return 0;
}

int MergingSortRecursion(SortArr *sortArr)
{
    mergeSort(sortArr, 1, sortArr->length);
    return 0;
}

int PrintArray(SortArr sortArr)
{
	int i = 0;

	for(i = 1; i <= sortArr.length; i++)
	{
		printf("%d,", sortArr.arr[i]);
	}
	printf("\b;
");

	return 0;
}

int main()
{
	SortArr *sortArr = NULL;
	sortArr = CreateSortArr();

	printf("
Before Sort：\t");
	PrintArray(*sortArr);

	MergingSortRecursion(sortArr);

	printf("Sorted Array：\t");
	PrintArray(*sortArr);

	free(sortArr);

	return 0;
}

時間複雑度分析:
merge()関数では、70行~77行目のfor()サイクルに必要な時間O(n 1+n 2)=O(n)、86行目~98行目のforサイクルでnラウンド反復が共有されており、そのうち、各ラウンド反復に要する時間は定数であるため、merge()関数の時間複雑度はO(n)である.