クイックソートについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: クイックソートについて

Re: クイックソートについて

#3

by ちびれおん » 6年前

Bull 様
ありがとうございます！！！
無事に実行でき正しく測定することができました！
ピボットの選び方でこんなに違いが出てくるんですね…。
勉強不足ですみません。
このプログラムに3日間くらい悩まされましたが解決できました(;_:)

本当に感謝しかないです…ありがとうございます！！！

Re: クイックソートについて

#2

by Bull » 6年前

データ量が多いということもありますが、クリックソートの再帰呼び出しでスタックオーバーフローが起こっているようです。

対症療法的にはスタックを増やせばいいと思います。お使いのコンパイラーによって違いますが、VC++ ならばプロジェクトのプロパティーでリンカーのオプションで設定できます。

根本的に見直すならば、クイックソート関数で、ピボットの選び方を変えればいいと思います。
ご提示のソースでは配列の左端をピボットにしていますが、データが降順であると最悪ケースになってしまっているようです。そのため再帰呼び出しが深くなりスタックを食い潰しているようです。クイックソートではピボットの選び方は重要ですが、“クイックソート ピボット”で検索すると興味深いページが幾つか見付かります。

安直には配列の中央の値でもだいぶましになります。
例えばクイックソート関数を以下のようにすると、スタックはそれほど消費しません。

コード: 

void q_sort(int numbers[], int left, int right)
{
	int pivot, l_hold, r_hold;

	l_hold = left;
	r_hold = right;
	pivot = numbers[(left+right)/2];

	for (;;)
	{
		while (numbers[right] > pivot)
			right--;
		while (numbers[left] < pivot)
			left++;

		if (left >= right) break;

		int t = numbers[right];
		numbers[right] = numbers[left];
		numbers[left] = t;

		left++;
		right--;
	}

	if (l_hold < left - 1)					//軸の左側をソートする
		q_sort(numbers, l_hold, left - 1);
	if (right + 1 < r_hold)					//軸の右側をソートする
		q_sort(numbers, right + 1, r_hold);
}

クイックソートについて

#1

by ちびれおん » 6年前

降順に並ぶ10万個のデータを、クイックソートのアルゴリズムを用いて昇順にソートし、そのソート時間を計測するプログラムを作成しています。データ数が1000個程度だと昇順にソートはできますが、ソート時間は0.000000秒になってしまいます。また、データが10000個以上になると動作が停止され上手く実行できません…。

同様にランダムに並ぶ10万個のデータをソートした時には正しく測定することができました。
降順に並ぶデータではなぜできないのかわかりません。よろしくお願いします。(;_:)

コード: 

#define _CRT_SECURE_NO_WARNINGS
#define SIZE 100000
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//プロトタイプ宣言
void koujun(int *num, int size);//データを降順にし、ファイルに書き込む
double quick_sort(int *num, int size);//クイックソート
double q_sort(int numbers[], int left, int right);

//データを降順にし、ファイルに書き込む
void koujun(int *num, int size){
	//変数宣言
	FILE *fp;
	int i;

	//10万個のデータを降順に作成
	for (i = 0; i < size;i++){
		num[i] = size - (i + 1);
	}

	//ファイルに書き込む
	if ((fp = fopen("koujun", "w")) == NULL){//リードモードでファイルを開く
		printf("ファイルがない.\n");
		exit(1);
	}
	for (i = 0; i<size; i++){
		fprintf(fp, "%d\n", num[i]);//ファイルに書き込む
	}
	printf("ファイルに書き込みました\n");
	fclose(fp);

	return;
}

//クイックソート
double quick_sort(int *num, int size)
{
	//変数宣言
	FILE *fp;
	clock_t start, end;
	int i;

	//計測開始
	start = clock();
	printf("選択ソートの処理時間を計測します\n");
	printf("開始時間：%lf秒\n", (double)start / CLOCKS_PER_SEC);

	//クイックソート処理開始
	q_sort(num, 0, size - 1);

	end = clock();//計測終了
	printf("終了時間：%lf秒\n", (double)end / CLOCKS_PER_SEC);
	printf("ソート時間は%lf秒です\n", (double)(end - start) / CLOCKS_PER_SEC);

	//ファイルに書き込む
	if ((fp = fopen("quick_sort", "w")) == NULL){//リードモードでファイルを開く
		printf("ファイルがない.\n");
		exit(1);
	}
	for (i = 0; i<size; i++){
		fprintf(fp, "%d\n", num[i]);//ファイルに書き込む
	}
	printf("結果を書き込みました\n");
	fclose(fp);
	
	return;
}
double q_sort(int numbers[], int left, int right)
{
	int pivot, l_hold, r_hold;

	l_hold = left;
	r_hold = right;
	pivot = numbers[left];
	while (left < right)
	{
		while ((numbers[right] >= pivot) && (left < right))
			right--;
		if (left != right)
		{
			numbers[left] = numbers[right];
			left++;
		}
		while ((numbers[left] <= pivot) && (left < right))
			left++;
		if (left != right)
		{
			numbers[right] = numbers[left];
			right--;
		}
	}
	numbers[left] = pivot;
	pivot = left;
	left = l_hold;
	right = r_hold;
	if (left < pivot)//軸の左側をソートする
		q_sort(numbers, left, pivot - 1);
	if (right > pivot)//軸の右側をソートする
		q_sort(numbers, pivot + 1, right);
}

void main(){
	//変数宣言
	int i;
	int NUM[SIZE];
	int n = 0;

	//10万個のデータの作成
	for (i = 0; i < SIZE; i++){
		NUM[i] = i;
	}

	//降順
	koujun(NUM, SIZE);
	
	//クイックソート
	quick_sort(NUM, SIZE);
}

ページトップ