K&R のクイックは優れたコーディングの例ですが、クイックソートの仕組みの良い例ではありません。プレスワップの目的は直感的ではなく、ID スワップは非効率的で混乱を招きます。これを明確にするためのプログラムを作成しました。コード コメントで問題を説明します。
私は Linux でのみコンパイルおよびテストしましたが、Visual Studio はこのプレーンなバニラ コンソール アプリで問題はないはずです。
/***************************** QUICK.CPP ***************** ************************
著者: デビッド・マクラッケン
更新日: 2009-08-14
目的: これは、K&R "The C
プログラミング言語」（第 2 版 p. 120）。多くのプログラマーが不満を抱いています。
このバージョンから一般的なクイックソートを理解しようとすると、
明らかにクイックソートのチュートリアルではなく、ポインタの使用に関するものでした
関数に。私のプログラムは、オリジナルを int でのみ動作するように変更して、
選別作業に集中。グローバルリストと再帰を印刷できます
変更ごとにサブリストを作成して、並べ替えの決定プロセスを追跡します。私のプログラムも
どちらも説明のつかないスワッピングを含む、2 つの紛らわしい側面を明確にします。
その操作を、さらに 2 つの変更されたバージョンの操作と比較することにより、オリジナルを確認します。
オリジナルが行う紛らわしいことの 1 つは、アイテムをそれ自体と交換することです。
コード (int のみに変更) は次のとおりです。
最後 = 左;
for( i = 左 +1 ; i <= 右 ; i++ )
if( v[i] < v[ 左 ] )
swap( v[ ++last ], v[ i ]);
left と v[ left ] はループ不変であることに注意してください。v[ left ] はピボットです。
余分なスワップは、ピボットよりも小さいすべての値に対して実行されます。
以前の値がピボットよりも大きい。たとえば、指定されたサブリスト (後
preswap) 9,8,5,7,4,6、最初は i = left + 1、8 を選択。
9 よりも大きい場合、last は i と同じ要素を指すようにインクリメントされ (8 を選択)、
余分なスワップが実行されます。次の反復で、last は 8 を選択しますが、i
5 を選択し、5 がそれ自体と交換されます。これが最後まで続く
サブリスト。ソート関数 krQuick2 は krQuick と同じですが、++last をテストします
余分なスワッピングを避けるために i に対して。これは確かにより良い結果をもたらします
実質的に無料でパフォーマンスを向上させますが、さらに重要なことは、明確にするのに役立ちます
コードが行おうとしているのは、次の値を見つけて交換することです。
ピボットよりも大きく、後で発生し、ピボットよりも小さいものがあります。
混乱の第 2 の原因は、中間点であるプレスワップの目的です。
値は一番左のものと交換されます。これは関係なく行われるため、
エントロピーを減らすことはできません。実際、それは正反対のことをします
すでにソートされているサブリストの非常に重要なケースで、通常は
クイックソートのパフォーマンスが悪い。このアクションは、ソートされたリストを意図的にソート解除し、
基本的に、ソートされていないものには何もしません。このシンプルで安価なアクション
によって示されるように、平均および最悪の場合のパフォーマンスが大幅に向上します。
3 番目のバリエーションは、krQuick2 から preswap を削除するだけの quick3 です。
quick3 は、プレスワップが不要であることを示しています。実際には、任意の値
リストからピボットとして機能するものを選択できます。最も分類されていないもののみ
virture による場合、quick3 は krQuick2 よりもわずかに優れたパフォーマンスを示します。
プレスワップをスキップする。初期順序の増加に伴い、
krQuick2 は、quick3 よりも着実に改善されています。
v[i] を v[left] に対してテストすると、混乱が生じる場合もあります。左と
v[ left ] はループ不変です。最適化コンパイラはこれを認識し、
ループから値を引き上げますが、このループ不変性はすぐには適用されません
クイックソートの例としてこれを研究している人には明らかです。スワップ中
ループ、v[left] はピボット値を保持するためだけに機能します。オートマチックも同じように
値を簡単に保持でき、その目的がより明確になります。ただし、コードは
間接的な例。リスト項目が何であるかはわかりませんが、そうすることができます
それらのいずれかが v[ left ] に適合し、swap 関数ができることを確認してください。
そこにそれを置きます。したがって、1 回のプレスワップ操作で 3 つのことが行われます。それはランダム化します
ソートされたサブリスト; ピボットをコピーしない場所に便利にコピーします
スワッピングの対象となります。を抽出して残ったループの穴を埋めます。
ピボット。要素が何であるかを知らなくても、これらすべてを実行します
私たちがすでに持っている機能。この驚くべきプログラミングの偉業は十分に価値があります
勉強はしますが、クイックソートを理解するためではありません。
このプログラムの使用方法
3 つの一般変数、関数、並べ替えられるデータ、および何
表示する。
単純化された K&R オリジナル関数 krQuick は関数 0 です。関数 1、
krQuick2 は、ID スワップが削除された krQuick です。関数 2、quick3 は、
プリスワップなしの krQuick2。
ソートされるデータは、5 つの組み込みリストのいずれか、またはそれらすべて、または
コマンドラインで入力された 10 進整数のスペースで区切られたリスト。
表示された情報は、機能の動作のトレースを提供します。全部で
場合、リストは並べ替えの前後に表示され、統計が実行されます
報告されています。SHOW_NOTHING の場合、他に何も報告されません。SHOW_GLOBAL の場合、
再帰ソートが呼び出されるたびに、変化する完全なリストが表示されます
関数。SHOW_LOCAL1 の場合、関数に渡されたサブリストが表示される前に
変更されています。SHOW_LOCAL の場合、各スワップ後にサブリストが表示されます。もしも
SHOW_INDEX、スワッピングに含まれるインデックスとそれらのインデックスの値
スワップが発生する前に表示されます。これらの選択は、SHOW_ 列挙型に対応します。
および は累積フラグです。
デフォルトでは、3 つの関数すべてが 5 つの組み込み関数すべてに連続して適用されます。
SHOW_NOTHING を使用したデータ リスト。の性能を比較するのに便利です。
関数。たとえば、順序付けられていないリスト 11 0 10 1 9 2 8 を示しています。
3 7 4 6 5 quick3 は 37 回の比較と 30 回のスワップを使用し、krQuick2 は 38 回の比較を使用します。
そして44回のスワップ。ただし、順序付きリストでは 0 1 2 3 4 5 6 7 8 9 10 11 quick3
は 66 回の比較と 22 回のスワップを使用しますが、krQuick2 は 25 回の比較と 28 回のスワップを使用します。
コマンド ライン引数は内容を変更しますが、操作の順序は変更しません。全部で
場合、選択された各関数は、選択されたすべてのデータ リストに適用されます。
コマンド引数は大文字と小文字を区別しません: F 関数セレクター、D データ セレクター、
と S はどのマップかを示します。それぞれの後にスペースなしで 1 文字が続きます。
F0、F1、F2、FA 機能 0、1、2 のみ、またはすべての機能を選択します。
D0、D1、D2、D3、D4、DA 組み込みデータ リスト 0、1、2、3、または 4 のみ、またはすべてを選択します。
S0 (デフォルト) は、追加情報を表示しません。
S1 (GLOBAL) は、呼び出しごとに完全なリスト (「GLOBAL」凡例を除く) を表示します。
S2 (LOCAL1) は、処理前のサブリストを示しています。
S3 (グローバル+ローカル1)
S4 (LOCAL) は、各スワップ後のサブリストを示します。前にサブリストも表示します
処理。
S8 (INDEX) はインデックスを表示しますが、これらは少なくとも LOCAL がなければ表示されません。
1 桁の引数で 8 と組み合わせることはできません。
SA(全て)
ローカルの凡例には、
レポートしているコードをポイントします。
最も有用な S 形式は、S1、S5、および SA (S0 がデフォルト) です。
F および S 引数の後に、スペースで区切られた数字のリストが取得されます
データリストとして。D 引数は無視されます。例えば：
クイック 20 21 15 12 40 0
3 つの関数すべてをデータに適用し、並べ替えられていないものと並べ替えられたもののみを報告します。
完全なリストと運用統計。
クイック f0 sa 20 21 15 12 40 0
関数 0 krQuick のみをデータに適用し、すべてを報告します。
****************************************************** ****************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// ======================== データと宣言 ==================== ==========
#define DIM(A) ( sizeof A / sizeof A[0])
typedef unsigned int UINT;
enum { SHOW_NOTHING、SHOW_GLOBAL = 1、SHOW_LOCAL1 = 2、SHOW_LOCAL = 4、
SHOW_INDEX = 8、SHOW_ALL = 0xFF };
int showWhat = SHOW_NOTHING;
int list0[] = { 4,0,2,5,1,3 };
int list1[] = { 0,1,2,3,4,5,6,7,8,9,10,11};
int list2[] = { 11,10,9,8,7,6,5,4,3,2,1,0};
int list3[] = { 11,9,7,5,3,1,0,2,4,6,8,10};
int list4[] = { 11,0,10,1,9,2,8,3,7,4,6,5};
static struct { int *list; int cnt; } リスト[] =
{
{ list0, DIM( list0 )},
{ list1, DIM( list1 )},
{ list2, DIM( list2 )},
{ list3, DIM( list3 )},
{ list4, DIM( list4 )},
};
int 合計 [ 1000 ];
int totalCnt;
int *userData = 0;
int userDataLen = 0;
int 再帰; // 現在の再帰レベル。
int 呼び出し。// sort 関数が呼び出された回数。
整数の深さ; // 最大再帰レベル。
int スワップ; // スワップの数。
int 比較; // リスト アイテムの数を比較します。
int totCalls;
int totDepth;
int totCompares;
int totSwaps;
void (*sortFunc)( int *list, int left, int right );
char dArg = 'A'; // コマンド ライン引数は、0、1、2、3、4、または A を選択します
int dataList; // dArg が数値の場合、これはその int 値です。
//============================== 機能 ================= ====================
// - - - - - - - - - - - - - - - インデント - - - - - - - - - ----------------------
// 再帰の各レベルに 2 つのスペースを出力して、後続の出力をインデントします
// 出力。
// ................................................................ ...................................
void インデント( void )
{
for( int インデント = 1 ; インデント < 再帰 ; インデント++ )
printf( " " );
}
// - - - - - - - - - - - - - - - - 見せる - - - - - - - - ------------------------
// グローバル コントロール設定 showWhat に従って、指定された int リストを出力します
// および指定されたローカル ID。これは何も出力しないか、グローバル
// リストまたはローカル サブリスト。凡例 GLOBAL または
// LOCALx x はローカル ID で、ソート コードのどの時点であるかを示します
// サブリストを表示しています。
// 戻り値: なし
// 引数:
//- int *ia は int リストを指します。
//- int cnt はリスト内の要素の数です。
//- int local は、0 より大きい場合、ソート ルーチンのローカル ポイントを示します。 0
// これがグローバルであることを示します。どちらの場合も、フォーマットはによって制御されます
// showWhat. local が -1 の場合、リストは無条件に印刷されます。
// 任意の凡例。
// グローバル：
//- showWhat ビットマップ コントロール ワード
//-- 0 (SHOW_NOTHING) これは完全な値であり、ビット フラグではありません。
//-- 1 (SHOW_GLOBAL) ローカルが 0 の場合、リストを出力する。他のビットも
// 設定すると、GLOBAL 凡例がリストの前に出力されます。
//-- 2 (SHOW_LOCAL1) ローカルが 1 の場合にのみリストを出力する。
//-- 3 (SHOW_LOCAL) ローカルが 1 以上の場合、リストを出力します。
///
// ...................... ノート ......................... ...................................
// SHOW_NOTHING
// これは、呼び出し元が呼び出す前に showWhat をテストしないために存在します。もし私達
// 最初のソートされていないリストと最終的なソートされたバージョンのみを表示したい場合
// SHOW_NOTHING は、並べ替え関数からのすべての印刷出力をブロックします。制御
// 関数呼び出しは local = -1 で表示され、リストを出力します。
// ................................................................ ...................................
void show( int *ia, int cnt, int local )
{
if( ローカル >= 0 )
{
スイッチ ( showWhat )
{
ケースSHOW_NOTHING:
戻る;
case SHOW_GLOBAL: // SHOW_GLOBAL のみ
if( ローカル > 0 )
戻る; // これはローカルです
壊す; // 凡例なしでリストを出力します。
デフォルト: // SHOW_GLOBAL、SHOW_LOCAL1、SHOW_LOCAL の組み合わせ
if( ローカル == 0 ) // グローバル
{
if( ( showWhat & SHOW_GLOBAL ) == 0 )
戻る;
printf( "グローバル" );
}
else if( showWhat & SHOW_LOCAL || ( showWhat & SHOW_LOCAL1 && local == 1 ))
{
インデント（）;
printf( "Local%d: ", ローカル );
}
そうしないと
戻る;
}
}
for( int *end = ia + cnt ; ia < end ; ia++ )
printf( "%d ", *ia );
putchar( '\n' );
}
// -------------------------------- スワップ --------------- ------------------------
void swap( int *p1, int *p2 )
{
int temp = *p2;
*p2 = *p1;
*p1 = 温度;
++スワップ;
}
// ------------------------------ krQuick ----------------- ----------------------
// K&R のクイック関数は、整数のみを処理し、インラインを使用するように変更されました
// 間接比較関数の代わりに数値比較。
// ................................................................ ...................................
void krQuick( int *list, int left, int right )
{
int i、最後。
++コール;
if( 再帰 > 深さ )
深さ = 再帰; // 最初に recursion = 0 を呼び出し、深さは 0 です。つまり、まだ再帰はありません。
++再帰;
表示 (合計、totalCnt、0); // グローバル
show( リスト + 左、右 - 左 + 1、1 ); // ローカル
if( 左 < 右 )
{
swap( リスト + 左、リスト + (左 + 右) / 2 );
++スワップ;
show( リスト + 左、右 - 左 + 1、2 );
最後 = 左;
for( i = 左 + 1 ; i <= 右 ; i++ )
{
++比較;
if( リスト[ i ] < リスト[ 左 ])
{
if( showWhat & SHOW_INDEX )
{
インデント（）;
printf( "i=%d @i=%d 左=%d @左=%d 最後=%d\n",
i、リスト[i]、左、リスト[左]、最後);
}
swap( list + ++last, list + i );
show( リスト + 左、右 - 左 + 1、3 );
++スワップ;
}
}
swap( リスト + 左、リスト + 最後 );
show( リスト + 左、右 - 左 + 1、4 );
++スワップ;
krQuick( リスト、左、最後 - 1 );
krQuick( リスト、最後 + 1、右 );
}
- 再帰;
}
// ------------------------------- krQuick2 ---------------- --------------------
// krQuick のように変更された K&R のクイック関数に ID の削除を加えたもの
// スワップします。
// ................................................................ ...................................
void krQuick2( int *list, int left, int right )
{
int i、最後。
++コール;
if( 再帰 > 深さ )
深さ = 再帰; // 最初に recursion = 0 を呼び出し、深さは 0 です。つまり、まだ再帰はありません。
++再帰;
表示 (合計、totalCnt、0); // グローバル
show( リスト + 左、右 - 左 + 1、1 ); // ローカル
if( 左 < 右 )
{
swap( リスト + 左、リスト + (左 + 右) / 2 );
++スワップ;
show( リスト + 左、右 - 左 + 1、2 );
最後 = 左;
for( i = 左 + 1 ; i <= 右 ; i++ )
{
++比較;
if( list[ i ] < list[ left ] && ++last != i )
{
if( showWhat & SHOW_INDEX )
{
インデント（）;
printf( "i=%d @i=%d 左=%d @左=%d 最後=%d\n",
i、リスト[i]、左、リスト[左]、最後);
}
swap( リスト + 最後、リスト + i );
show( リスト + 左、右 - 左 + 1、3 );
++スワップ;
}
}
swap( リスト + 左、リスト + 最後 );
show( リスト + 左、右 - 左 + 1、4 );
++スワップ;
krQuick2( リスト、左、最後 - 1 );
krQuick2( リスト、最後 + 1、右 );
}
- 再帰;
}
// ------------------------------------ クイック3 ----------------------- ----------------------
// プレスワップを行わないように変更された krQuick2。K&Rオリジナルでは、目的は
// preswap は、事前に並べ替えられたサブリストにランダム性を導入することです。ソート
// これをなくしても結果は変わりませんが、
// 平均と最悪の間のすべてのケースでより多くの比較と交換。近くだけ
// 最良のケースでは、preswap をなくすことでパフォーマンスが向上します。
// ................................................................ ...................................
void quick3( int *list, int left, int right )
{
int i、最後。
++コール;
if( 再帰 > 深さ )
深さ = 再帰; // 最初に recursion = 0 を呼び出し、深さは 0 です。つまり、まだ再帰はありません。
++再帰;
表示 (合計、totalCnt、0); // グローバル
show( リスト + 左、右 - 左 + 1、1 ); // ローカル
if( 左 < 右 )
{
最後 = 左;
for( i = 左 + 1 ; i <= 右 ; i++ )
{
++比較;
if( list[ i ] < list[ left ] && ++last != i )
{
if( showWhat & SHOW_INDEX )
{
インデント（）;
printf( "i=%d @i=%d 左=%d @左=%d 最後=%d\n",
i、リスト[i]、左、リスト[左]、最後);
}
swap( リスト + 最後、リスト + i );
show( リスト + 左、右 - 左 + 1、3 );
++スワップ;
}
}
swap( リスト + 左、リスト + 最後 );
show( リスト + 左、右 - 左 + 1、4 );
++スワップ;
quick3( リスト、左、最後 - 1 );
quick3( リスト、最後 + 1、右 );
}
- 再帰;
}
static struct { void (*func)( int *list, int left, int right ) ; char *name ; } sortFuncs[] =
{
{ krQuick, (char*)"krQuick" },
{ krQuick2, (char*)"krQuick2 (ID スワップなし)" },
{ quick3, (char*)"quick3 (プレスワップなし)" }
};
// ------------------------------------ 並べ替え ----------------------- ----------------------
// パフォーマンス カウンターを設定し、現在選択されている並べ替えを現在の
// データ リスト、およびパフォーマンスを出力します (選択された関数のこの 1 つのケースについて)
// 選択したデータ リストに適用されます)。
// ................................................................ ...................................
void sortOne( void )
{
再帰 = 0;
コール = 0;
深さ = 0;
スワップ = 0;
比較 = 0;
表示 (合計、totalCnt、-1);
sortFunc(合計、0、合計Cnt - 1);
表示 (合計、totalCnt、-1);
printf( "呼び出し = %d、深さ = %d、比較 = %d、スワップ = %d\n",
呼び出し、深度、比較、スワップ );
printf( "--------------------------------\n" );
}
// -------------------------------- sortOneSet ------------------- ------------------
// 目的: 現在選択されている並べ替え関数を 1 つのデータ リストに適用します。
void sortOneSet( int idx )
{
if( idx < 0 )
{
totalCnt = userDataLen;
memcpy( total, userData, totalCnt * sizeof( int ));
}
そうしないと
{
totalCnt = リスト[ idx ].cnt;
memcpy( 合計, リスト [ idx ].list, totalCnt * sizeof( int ));
}
sortOne();
totCalls += コール;
totDepth += 深さ;
totCompares += 比較します。
totSwaps += スワップ;
}
// ------------------------- testOneFunc ---------------------- -----------------
// 目的: 選択した関数を 1 つまたはすべてのデータ リストに適用します。
// 戻り値: なし
// 引数: int sel は 0、1、または 2 で、krQuick、krQuick2、または quick3 を選択します。
// Globals: char dArg は、データ リスト セレクターのコマンド ライン引数です。それは「0」です。
// '1'、'2'、または 'A'。'A' はすべてのデータ リストを選択します。それ以外の場合、int dataList は
// コマンドによってすでに変換されている dArg の int 値
// ライン プロセッサ。
// ................................................................ ...................................
void testOneFunc( int sel )
{
totCalls = 0;
総深さ = 0;
totCompares = 0;
totSwaps = 0;
sortFunc = sortFuncs[ sel ].func;
printf( "====== %s ======\n", sortFuncs[ sel ].name );
if( userDataLen != 0 )
sortOneSet( -1 );
それ以外の場合 ( dArg == 'A' )
{
for( UINT idx = 0 ; idx < DIM( リスト ) ; idx++ )
sortOneSet( idx );
printf( "合計: 呼び出し = %d、深さ = %d、比較 = %d、スワップ = %d\n",
totCalls、totDepth、totCompares、totSwaps );
}
そうしないと
sortOneSet( データリスト );
}
// - - - - - - - - - - - - - - - - - 主要 - - - - - - - ------------------------
// 目的: コマンド ライン引数の処理、show (印刷出力) およびデータの設定
// セレクターを一覧表示し、選択した関数に対して testOneFunc を 1 回呼び出します
// または 3 つの関数のそれぞれ。
// ................................................................ ...................................
int main( int argc, char **argv )
{
char *cp;
char fArg = 'A'; // 関数セレクター 0,1,2,A
UINT idx;
showWhat = SHOW_NOTHING;
dArg = 'A';
for( int cnt = 1 ; cnt < argc ; cnt++ )
{
cp = argv[ cnt ];
switch( toupper( *cp ))
{
ケース「F」:
fArg = toupper( cp[1] );
壊す;
ケース「D」:
dArg = toupper( cp[1] );
if( dArg != 'A' )
{
dataList = dArg - '0';
if( dataList < 0 || dataList >= (int)DIM( リスト ))
{
printf( "エラー: 不正なデータ リスト セレクタ %c\n", dArg );
1 を返します。
}
}
壊す;
case 'S': // 表示セレクターは、ビットマップ化された showWhat または N または A に一致します
++cp;
if( *cp != 0 || toupper( *cp ) != 'N' )
{
if( toupper( *cp ) == 'A' )
showWhat = SHOW_ALL;
そうしないと
showWhat = atoi( cp );
}
壊す;
デフォルト：
if( !isdigit( *cp ))
{
printf( "エラー: オプション %c がありません\n", *cp );
1 を返します。
}
for( idx = 0 ; idx < DIM( 合計 ) && cnt < argc ; idx++, cnt++ )
total[ idx ] = atoi( argv[ cnt ] );
userData = (int*)malloc( sizeof( int ) * idx );
if( ユーザーデータ == 0 )
{
printf( "エラー: データ リストにメモリを割り当てることができません\n" );
2 を返します。
}
memcpy( userData, total, sizeof( int ) * idx );
userDataLen = idx;
}
}
スイッチ( fArg )
{
ケース「A」:
for( UINT sfi = 0 ; sfi < DIM( sortFuncs ) ; sfi++ )
testOneFunc( sfi );
壊す;
ケース '0':
ケース '1':
ケース '2':
testOneFunc( fArg - '0' );
壊す;
デフォルト：
printf( "エラー: 不正な関数セレクター %c\n", fArg );
1 を返します。
}
0 を返します。
}
クイックの結果
これはすべてのデフォルトを使用します。これは、パフォーマンスを比較するのに最も役立ちます。
3つの異なる機能の。
====== krQuick ======
4 0 2 5 1 3
0 1 2 3 4 5
呼び出し = 7、深さ = 2、比較 = 8、スワップ = 20
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 3、比較 = 25、スワップ = 48
----------------------------------
11 10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 17、深さ = 5、比較 = 30、スワップ = 62
----------------------------------
11 9 7 5 3 1 0 2 4 6 8 10
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 13、深さ = 5、比較 = 33、スワップ = 56
----------------------------------
11 0 10 1 9 2 8 3 7 4 6 5
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深度 = 6、比較 = 38、スワップ = 60
----------------------------------
合計: 呼び出し = 67、深さ = 21、比較 = 134、スワップ = 246
====== krQuick2 (ID スワップなし) ======
4 0 2 5 1 3
0 1 2 3 4 5
呼び出し = 7、深さ = 2、比較 = 8、スワップ = 16
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 3、比較 = 25、スワップ = 28
----------------------------------
11 10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 17、深さ = 5、比較 = 30、スワップ = 52
----------------------------------
11 9 7 5 3 1 0 2 4 6 8 10
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 13、深さ = 5、比較 = 33、スワップ = 46
----------------------------------
11 0 10 1 9 2 8 3 7 4 6 5
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 6、比較 = 38、スワップ = 44
----------------------------------
合計: 呼び出し = 67、深さ = 21、比較 = 134、スワップ = 186
====== quick3 (プレスワップなし) ======
4 0 2 5 1 3
0 1 2 3 4 5
呼び出し = 7、深さ = 3、比較 = 10、スワップ = 10
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 23、深さ = 11、比較 = 66、スワップ = 22
----------------------------------
11 10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 23、深さ = 11、比較 = 66、スワップ = 22
----------------------------------
11 9 7 5 3 1 0 2 4 6 8 10
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 7、比較 = 46、スワップ = 54
----------------------------------
11 0 10 1 9 2 8 3 7 4 6 5
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 19、深さ = 6、比較 = 37、スワップ = 30
----------------------------------
合計: 呼び出し = 87、深さ = 38、比較 = 225、スワップ = 138
****************************************************** ****************************
クイック f0 s5 d1 の結果
S5 形式は、並べ替え中にサブリストがどのように変化するかを表示するのに最適です。以来
LOCAL は、スワップ、余分な ID スワップ (この多くは
例) すぐにわかります。
====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 2: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 4: 0 1 2 3 4 5 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1 2 3 4
ローカル 2: 2 1 0 3 4
ローカル 3: 2 1 0 3 4
ローカル 3: 2 1 0 3 4
ローカル 4: 0 1 2 3 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1
ローカル 2: 0 1
ローカル 4: 0 1
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 1
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 3 4
ローカル 2: 3 4
ローカル4: 3 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 6 7 8 9 10 11
ローカル 2: 8 7 6 9 10 11
ローカル 3: 8 7 6 9 10 11
ローカル 3: 8 7 6 9 10 11
ローカル 4: 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 6 7
ローカル 2: 6 7
ローカル4: 6 7
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 7
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 9 10 11
ローカル 2: 10 9 11
ローカル 3: 10 9 11
ローカル 4: 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 9
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 11
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 3、比較 = 25、スワップ = 48
****************************************************** ******************************
クイック f0 sa d1 の結果
これは前の例と同じですが、インデックスの追加の詳細を示しています
スワッピングの決定につながる値。ただし、混乱は不明瞭になる傾向があります
サブリストに実際に何が起こっているか。
====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 2: 5 1 2 3 4 0 6 7 8 9 10 11
i=1 @i=1 左=0 @左=5 最後=0
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
i=2 @i=2 左=0 @左=5 最後=1
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
i=3 @i=3 左=0 @左=5 最後=2
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
i=4 @i=4 左=0 @左=5 最後=3
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
i=5 @i=0 左=0 @左=5 最後=4
ローカル 3: 5 1 2 3 4 0 6 7 8 9 10 11
ローカル 4: 0 1 2 3 4 5 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1 2 3 4
ローカル 2: 2 1 0 3 4
i=1 @i=1 左=0 @左=2 最後=0
ローカル 3: 2 1 0 3 4
i=2 @i=0 左=0 @左=2 最後=1
ローカル 3: 2 1 0 3 4
ローカル 4: 0 1 2 3 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 0 1
ローカル 2: 0 1
ローカル 4: 0 1
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 1
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 3 4
ローカル 2: 3 4
ローカル4: 3 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 4
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 6 7 8 9 10 11
ローカル 2: 8 7 6 9 10 11
i=7 @i=7 左=6 @左=8 最後=6
ローカル 3: 8 7 6 9 10 11
i=8 @i=6 左=6 @左=8 最後=7
ローカル 3: 8 7 6 9 10 11
ローカル 4: 6 7 8 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 6 7
ローカル 2: 6 7
ローカル4: 6 7
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1:
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 7
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 9 10 11
ローカル 2: 10 9 11
i=10 @i=9 左=9 @左=10 最後=9
ローカル 3: 10 9 11
ローカル 4: 9 10 11
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 9
グローバル 0 1 2 3 4 5 6 7 8 9 10 11
ローカル 1: 11
0 1 2 3 4 5 6 7 8 9 10 11
呼び出し = 15、深さ = 3、比較 = 25、スワップ = 48