シェルソートプログラムについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
asdjack
記事: 22
登録日時: 8年前

シェルソートプログラムについて

#1

投稿記事 by asdjack » 8年前

C++でソートアルゴリズムの速度を調べるプログラムを作成しようと思い、ソートごとにクラスを分けてプログラムを作ってテストしてみたのですが、シェルソートが正しく並べ変わらないです。ソート対象のデータ生成や交換の部分はほかのクラスで使っていて問題なかったのでおかしいのはこのクラスの中だけだと思います。
どこがおかしいのか解答お願いします。

コード:

#pragma once
#include "timer.h"
#include "Swap.h"
#include "Etc.h"
#include <math.h>
#include <malloc.h>

class ShellSort
{
public:
	ShellSort();
	virtual~ShellSort();
	void Sh_Sort(int data[]);
};

ShellSort::ShellSort(){}

ShellSort::~ShellSort(void){}

void ShellSort::Sh_Sort(int data[])
{
	Swap Sh_swap;
	Etc Sh_etc;
	timer Sh_timer;
	Sh_etc.create_data(data);
	Sh_etc.disp(data);
	Sh_timer.timer_start();
	int t = (int)log((double)DATA_NUM) / log(2.0);
	int *Seq=(int*)malloc(sizeof(int)*t);
	if(Seq==NULL) 
	{
		std::cout<<"Memory Error"<<std::endl;
	}
	memset(Seq,0,t*sizeof(int));
	Seq[t]=1;
	for(int i=t;i>0;i--)//間隔定義	
	{
		Seq[i-1]=(2*Seq[i]+1);
	}

	for(int i=0;i<=t;i++)//ソート
	{
		for(int j=Seq[i];j<DATA_NUM;j++)
		{
			int h=j;
			if(h>=Seq[i]&&data[h-Seq[i]]>data[h])
			{
				Sh_swap.Pre_Swap(data[h-1],data[h]);
				h-=Seq[i];
			}
		}
	}
	Sh_timer.timer_stop();
	Sh_etc.disp(data);
	Sh_timer.disp_timer();
	free(Seq);
}
開発環境 Visual C++2010

beatle
記事: 1280
登録日時: 8年前
住所: 埼玉
連絡を取る:

Re: シェルソートプログラムについて

#2

投稿記事 by beatle » 8年前

38行目でSeq[t]にアクセスしていますが、Seqは要素がt個のint配列なので、[t]にアクセスしちゃだめです。

初級者
記事: 200
登録日時: 9年前

Re: シェルソートプログラムについて

#3

投稿記事 by 初級者 » 8年前

mallocに失敗したとき、なにごともなかったかのように実行し続けるのはどうなのかな、と思います。

asdjack
記事: 22
登録日時: 8年前

Re: シェルソートプログラムについて

#4

投稿記事 by asdjack » 8年前

指摘されたところと、自分で気づいた部分は修正してみました。
・46行目のif を doにした。
・seq[t]だったところをswq[t-1]にした。

コード:

#pragma once
#include "timer.h"
#include "Swap.h"
#include "Etc.h"
#include <math.h>
#include <malloc.h>

class ShellSort
{
public:
	ShellSort();
	virtual~ShellSort();
	void Sh_Sort(int data[]);
};

ShellSort::ShellSort(){}

ShellSort::~ShellSort(void){}

void ShellSort::Sh_Sort(int data[])
{
	Swap Sh_swap;
	Etc Sh_etc;
	timer Sh_timer;
	Sh_etc.create_data(data);
	Sh_etc.disp(data);
	Sh_timer.timer_start();
	int t = (int)log((double)DATA_NUM) / log(2.0);
	int *Seq=(int*)malloc(sizeof(int)*t);
	if(Seq==NULL) 
	{
		std::cout<<"Error"<<std::endl;
	}
	memset(Seq,0,t*sizeof(int));
	Seq[t-1]=1;
	for(int i=t-2;i>0;i--)//間隔定義	
	{
		Seq[i-1]=(2*Seq[i]+1);
	}

	for(int i=0;i<t;i++)//ソート
	{
		for(int j=Seq[i];j<DATA_NUM;j++)
		{
			int h=j;
			do
			{
				Sh_swap.Pre_Swap(data[h-Seq[i]],data[h]);
				h-=Seq[i];
			} while(h>=Seq[i] && data[h-Seq[i]]>data[h]);
			
		}
	}
	Sh_timer.timer_stop();
	Sh_etc.disp(data);
	Sh_timer.disp_timer();
	free(Seq);
}
これでほとんど正確にソートされたのですが、一番最後の配列だけ、間違ったソートになってしまいます。
例;0 2 3 5 5 6 6 8 8 4 ※DATA_NUM=10の時、
初級者 さんが書きました:mallocに失敗したとき、なにごともなかったかのように実行し続けるのはどうなのかな、と思います。
これは30行目のseq==NULLの時、エラーを出す処理以外に必要だということですか?

asdjack
記事: 22
登録日時: 8年前

Re: シェルソートプログラムについて

#5

投稿記事 by asdjack » 8年前

すいません、自己解決しました。46行目をdo文から while文にしたら正しくソートされました。
解答してくれた方、有難うございました。

閉鎖

“C言語何でも質問掲示板” へ戻る