クイックソート

[とーる]

#include <stdio.h>

#define ARRAY_SIZE (10)

/* プロトタイプ宣言 */
void quick_sort(int array[/url], int begin, int end);
void print_array(int array[/url], int size);

int main(void)
{
	int data[ARRAY_SIZE] = { 30, 20, 60, 50, 90, 0, 40, 10, 70, 80 };
	
	print_array( data, ARRAY_SIZE );      /* ソート前の配列を出力 */
	quick_sort( data, 0, ARRAY_SIZE-1 );  /* クイックソート実行 */
	print_array( data, ARRAY_SIZE );      /* ソート前の配列を出力 */
	
	return 0;
}

/*
	昇順になるようにクイックソートを行う。
	引数　array：ソート対象の配列。
	　　　begin：ソート範囲の先頭の添字。
		  end：ソート範囲の末尾の添字。
*/
void quick_sort(int array[/url], int begin, int end)
{
	int i, j;
	int pivot;   /* 枢軸 */
	int work;
		
	pivot = array[ ( begin + end ) / 2 ];  /* 範囲の中央にある要素を枢軸とする */
	i = begin;
	j = end;
	
	while( 1 )
	{
		while( array < pivot ){ ++i; }  /* 枢軸以上の値が見つかるまで右方向へ進めていく */
		while( array[j] > pivot ){ --j; }  /* 枢軸以下の値が見つかるまで左方向へ進めていく */
		if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
		/* 要素を交換する */
		work = array;
		array = array[j];
		array[j] = work;
	}
	/* 枢軸の左側に要素が２つ以上あれば、その部分についてクイックソートを再帰させる */
	if( begin < i - 1 ){ 
		quick_sort( array, begin, i - 1 );
	}
	/* 枢軸の右側に要素が２つ以上あれば、その部分についてクイックソートを再帰させる */
	if( j + 1 < end ){
		quick_sort( array, j + 1, end );
	}
}

/*
	配列の要素を出力。
	引数　array：出力する配列。
	　　　size：配列の要素数。
*/
void print_array(int array[/url], int size)
{
	int i;
	int *p = &array[0];
	
	for( i = 0; i < size; ++i )
	{
		printf( "%d ", *p );
		++p;
	}
	printf( "\n\n" );
}

クイックソートに関しての質問なのですけど自分でいろいろ考えてたのですが
上の if( i >= j ){ break; } なんですが if( i == j ){ break; } でも、いいんですよね。
くだらない質問なんですが答えてもらえると助かります。お願いします。
開発環境はVisual C++です。

[管理人]

いや、i==jではだめです。
何故かというと、１回ずつ比較しているとは限らないからです。

今一番左が0で一番右が10だとしましょう。(以下番号は左から数えた要素番号です

0から探索していって、4でとまったとします。
10から探索していって、6でとまったとします。

これは正常に交換が出来ます、しかし、次、

左からの探索で5でとまり、右からの探索で4で止まったとすると、
i==jではぶつかったことが判定出来ませんよね。

この件は文字では中々わかりにくいです。
そのために、アニメーションで解説したソフトを作りましたので、
よければそちらを参考にして下さい。

http://dixq.net/sort.html

[array]

クイックソートとかまったく知らない素人ですが。管理人さんがめっちゃ得意そうｗ（クイックソート解説アプリというのを自作しているので）

data[ ]の配列の中心の値を基準、たぶんdata[5]（かdata[4]）を基準に判定してるみたいなので、

>while( array < pivot ){ ++i; }　　//ここでiを決定

ここでdata[0] < data[5]なら　iを+1し
もし  data[1] > data[5]　なら処理を終了し次の処理へ
この場合i = 1

>while( array[j] > pivot ){ --j; }   //ここでj決定

ここでdata[9] > data[5]なら　jを-1し
もし  data[8] < data[5]　なら処理を終了し次の処理へ
この場合j = 8

>work = array;　　　//ここで要素の置き換え
>array = array[j];
>array[j] = work;

data[i = 1]はdata[5]より大きい値
data[j = 8]はdata[5]より小さい値

が入っておりdata[1]⇔data[8]を入れ替えているので
data[1] < data[8] な値になるので・・・。

まぁこれだけ言えばどこを書き換えれば良いか分る筈です

[管理人]

私も苦手でした＾＾；
苦手で苦労したからこそ、こういうアプリを作って
みんなに楽してもらおうと思ったわけですが。

こういう動的なアルゴリズムは写真や本じゃわかりにくいんですよね・・。

[とーる]

すいません、返事が遅くなりました。
まず、始めに管理人様、array様ありがとうございます。
一番上のコードだと,クイックソート自体が間違っていましたね。
また質問などが、ありましたらよろしくお願いします。