N88-BASIC、C、アセンブラでQuick sort
N88-BASIC、C、アセンブラでQuick sort
Quick sort(並替え)
N88-BASIC、C
C(ポインター)、アセンブラ(8086系)
でプログラミング
クイックソートは再帰的に定義すると
1. 要素か1個以下なら以下を操作しない
2. 基準となる数値を決める
3. 基準となる数値より小さい集合と大きい集合に分ける
4. 小さいものに1.～5.を適用する
5. 大きいものに1.～5.を適用する
となります
QSORT(数の集合)を、ある数より小さいものと
大きいものに分ける操作とする
QSORT(数の集合)
数の要素が1個以下ならQSORT終了
基準となる数値を決める
基準となる数値より小さい集合と大きい集合に分ける
QSORT(小さい集合)
QSORT(大きい集合)
で並替る事ができます
{8 5 3 2}
を昇順に並替えをしてみます
QSORT({8 5 3 2})
要素数4個なので以下の操作をする
中央付近の5を基準に選ぶ
5より小と大の2グループに分ける
つまり、{3 2} {8 5}に分ける
({3 2} 5 {8} や {3 3 5} {8} に分けても良い)
QSORT({3 2})
QSORT({8 5})
{3 2} {8 5}
QSORT({3 2})
要素数2個なので以下の操作をする
中央付近の3を基準に選ぶ
3より小と大の2グループに分ける
{2} {3}
({} {3 2} や {3 2} {} とすると終わらない)
QSORT({2})は要素数1個なので何もしない
QSORT({3})は要素数1個なので何もしない
{2} {3} {8 5}
QSORT({8 5})は同様に
{2} {3} {5} {8}
となるり、小さい順(昇順)に並んでいます
8 5 3 2 を、基準5で小、大に分ける
3 2 | 8 5 それぞれ3や8で小、大に分ける
2 | 3 | 5 | 8
で並替えできます
分ける基準となる数値の決め方は色々ありますが
今回は中央付近の位置にある数にしています
クイックソートは基準の選び方と、データの並びの
相性によって、ソートにかかる時間が変わります
例、8個のデータ
最速の場合(A～H場所を表すとする)
A B C D E F G H
A B C D|E F G H
A B|C D|E F|G H ここまで、24個の要素を検索
A|B|C|D|E|F|G|H
最遅の場合(A～H場所を表すとする)
A B C D E F G H
A|B C D E F G H
A|B|C D E F G H
A|B|C|D E F G H
A|B|C|D|E F G H
A|B|C|D|E|F G H
A|B|C|D|E|F|G H ここまで、35個の要素を検索
A|B|C|D|E|F|G|H
小、大のグループは同じ要素数ずつに分かれると
速くなります
検索数のみ書きましたが要素を移動する回数も
実行時間にかかわってきます
プログラミングが目的なので、
アルゴリズムはざっくり説明しました
あまり詳しく知っている分けでは
ないので、
詳しくは、いろいろ調べて下さい
小、大に分ける方法
0 1 2 3 要素番号
{8 5 3 2} A(0)=8, A(1)=5, A(2)=3, A(3)=2とする
X=0, Y=3, B=5 左端、右端、基準となる数
(1) XをA(X) >= Bになるまで1ずつ増やす
(2) YをA(Y) <= Bになるまで1ずつ減らす
(3) X >= Y なら終了(～X-1,Y+1～に分ける)
(4) A(X)とA(Y)を交換し、X=X+1,Y=Y-1
上記(1)～(4)を繰り返す
{8 5 3 2}に適用して見ます
X=0, Y=3, B=5 に(1)～(2)を適用し
X=0, Y=3 なので(4)を適用し
{2 5 3 8} X=1, Y=2 に(1)～(2)を適用し
X=1, Y=2 なので(4)を適用し
{2 3 5 8} X=2, Y=1 に(1)～(2)を適用し
X=2, Y=1 なので(3)終了
～X-1,Y+1～つまり、0～1,2～3に分けて
{2 3}{5 8}となります
途中経過を色付きで表示しています
(n):nは分ける基準となる数値
青:検索範囲外
黄:小さい数
白:小にも大にも入らなかった数
緑:大きい数
青:検索範囲外
の順で表示され、小グループ、中、大グループ
(黄 白 緑)に分けられていく様を見る事ができます
N88-BASICのソートをCで書きました
ただし、Cではプログラムを簡単にするため、
すべて整数型で書き、途中経過の表示は
省略しています
すべての型に対応した関数はCライブラリの
qsortについて調べてみて下さい
Cでは、配列の初期化ができます
int a[] = { 3, 5, 7 };
は
int a[3]; a[0] = 3; a[1] = 5; a[2] = 7;
と同じです
また、sizeof(a)は配列aの総バイト数12、
sizeof(a[0])は配列1個a[0]のバイト数4なので
sizeof(a) / sizeof(a[0]) は、要素数3になります
(int型のバイト数はコンパイラーによって変わります)
ポインターについて、
int* p; pは整数型変数のアドレス(存在場所)
を入れる変数です
int i = 5;
p = &i; の&iは変数iのアドレス(存在場所)です
p[0]または*p はpの値が示すアドレス(存在場所)の
中身を表すので、どちらもiの中身なので、5です
int a[] = { 3, 5, 7 };
p = a; のaは配列変数の名ですが始めの要素の
アドレス(存在場所)でもあります
p[0]や*pは3、p[1]や*(p+1)は5、p[2]や*(p+2)は7
です
配列変数を関数に渡すときは、要素全部を渡すことは
できないので、先頭のアドレスを渡します
再帰はCだと楽ですね
Cはポインターを使うと計算量を減らせます
p = a + iなら、a[i] と *p は同じ値ですが
次の要素を読むとき、i++ と p++ の後、
a[i] は a+iを計算後その場所を読むのに対して、
*p は pが示す場所を読むだけで、
a+iの計算を省ける分、速くなります
Cはアセンブラに近い書き方も出来るので
高速化しやすいですね
C(ポインター)をアセンブラで書きました
ただし、quicksortの部分のみです
Cのポインターは、int *p; p++; でpはint型1個分の
4バイト分増加します
アセンブラではint型を参照するときはinc edx (1増加)
ではなくadd edx,4 (4増加)で4バイト分増加させる必要
があります
コンパイラーによってint型のビット数が異なりますので、
intをlong(32ビット = 4バイト)に変えてあります
#pragma optimize( "", off ) コンパイラーの最適化禁止
#pragma optimize( "", on ) コンパイラーの最適化許可
は、コンパイラーに最適化指定したとき、「アセンブラが
最適化ができない」というエラーが出るのを防ぐために
入れてありますデバッグモードで使うなどエラーが出ない
場合は無くてもかまいません
アセンブラはレジスタの選び方や命令の選び方などで
最適化の余地が多いのが良いですね
書き換えて最適化したりして遊んで見て下さい
Cコンパイラーなどは各自ご用意して下さい
NL-BASICとblg～.zip(qsort001.bas、qsort001.c、
qsort002.c、qsort002asm.c)は
このブログ(以下のリンク)からダウンロードできます
Quick sort(並替え)
N88-BASIC、C
C(ポインター)、アセンブラ(8086系)
でプログラミング
クイックソートは再帰的に定義すると
1. 要素か1個以下なら以下を操作しない
2. 基準となる数値を決める
3. 基準となる数値より小さい集合と大きい集合に分ける
4. 小さいものに1.～5.を適用する
5. 大きいものに1.～5.を適用する
となります
QSORT(数の集合)を、ある数より小さいものと
大きいものに分ける操作とする
QSORT(数の集合)
数の要素が1個以下ならQSORT終了
基準となる数値を決める
基準となる数値より小さい集合と大きい集合に分ける
QSORT(小さい集合)
QSORT(大きい集合)
で並替る事ができます
{8 5 3 2}
を昇順に並替えをしてみます
QSORT({8 5 3 2})
要素数4個なので以下の操作をする
中央付近の5を基準に選ぶ
5より小と大の2グループに分ける
つまり、{3 2} {8 5}に分ける
({3 2} 5 {8} や {3 3 5} {8} に分けても良い)
QSORT({3 2})
QSORT({8 5})
{3 2} {8 5}
QSORT({3 2})
要素数2個なので以下の操作をする
中央付近の3を基準に選ぶ
3より小と大の2グループに分ける
{2} {3}
({} {3 2} や {3 2} {} とすると終わらない)
QSORT({2})は要素数1個なので何もしない
QSORT({3})は要素数1個なので何もしない
{2} {3} {8 5}
QSORT({8 5})は同様に
{2} {3} {5} {8}
となるり、小さい順(昇順)に並んでいます
8 5 3 2 を、基準5で小、大に分ける
3 2 | 8 5 それぞれ3や8で小、大に分ける
2 | 3 | 5 | 8
で並替えできます
分ける基準となる数値の決め方は色々ありますが
今回は中央付近の位置にある数にしています
クイックソートは基準の選び方と、データの並びの
相性によって、ソートにかかる時間が変わります
例、8個のデータ
最速の場合(A～H場所を表すとする)
A B C D E F G H
A B C D|E F G H
A B|C D|E F|G H ここまで、24個の要素を検索
A|B|C|D|E|F|G|H
最遅の場合(A～H場所を表すとする)
A B C D E F G H
A|B C D E F G H
A|B|C D E F G H
A|B|C|D E F G H
A|B|C|D|E F G H
A|B|C|D|E|F G H
A|B|C|D|E|F|G H ここまで、35個の要素を検索
A|B|C|D|E|F|G|H
小、大のグループは同じ要素数ずつに分かれると
速くなります
検索数のみ書きましたが要素を移動する回数も
実行時間にかかわってきます
プログラミングが目的なので、
アルゴリズムはざっくり説明しました
あまり詳しく知っている分けでは
ないので、
詳しくは、いろいろ調べて下さい
小、大に分ける方法
0 1 2 3 要素番号
{8 5 3 2} A(0)=8, A(1)=5, A(2)=3, A(3)=2とする
X=0, Y=3, B=5 左端、右端、基準となる数
(1) XをA(X) >= Bになるまで1ずつ増やす
(2) YをA(Y) <= Bになるまで1ずつ減らす
(3) X >= Y なら終了(～X-1,Y+1～に分ける)
(4) A(X)とA(Y)を交換し、X=X+1,Y=Y-1
上記(1)～(4)を繰り返す
{8 5 3 2}に適用して見ます
X=0, Y=3, B=5 に(1)～(2)を適用し
X=0, Y=3 なので(4)を適用し
{2 5 3 8} X=1, Y=2 に(1)～(2)を適用し
X=1, Y=2 なので(4)を適用し
{2 3 5 8} X=2, Y=1 に(1)～(2)を適用し
X=2, Y=1 なので(3)終了
～X-1,Y+1～つまり、0～1,2～3に分けて
{2 3}{5 8}となります
途中経過を色付きで表示しています
(n):nは分ける基準となる数値
青:検索範囲外
黄:小さい数
白:小にも大にも入らなかった数
緑:大きい数
青:検索範囲外
の順で表示され、小グループ、中、大グループ
(黄 白 緑)に分けられていく様を見る事ができます
N88-BASICのソートをCで書きました
ただし、Cではプログラムを簡単にするため、
すべて整数型で書き、途中経過の表示は
省略しています
すべての型に対応した関数はCライブラリの
qsortについて調べてみて下さい
Cでは、配列の初期化ができます
int a[] = { 3, 5, 7 };
は
int a[3]; a[0] = 3; a[1] = 5; a[2] = 7;
と同じです
また、sizeof(a)は配列aの総バイト数12、
sizeof(a[0])は配列1個a[0]のバイト数4なので
sizeof(a) / sizeof(a[0]) は、要素数3になります
(int型のバイト数はコンパイラーによって変わります)
ポインターについて、
int* p; pは整数型変数のアドレス(存在場所)
を入れる変数です
int i = 5;
p = &i; の&iは変数iのアドレス(存在場所)です
p[0]または*p はpの値が示すアドレス(存在場所)の
中身を表すので、どちらもiの中身なので、5です
int a[] = { 3, 5, 7 };
p = a; のaは配列変数の名ですが始めの要素の
アドレス(存在場所)でもあります
p[0]や*pは3、p[1]や*(p+1)は5、p[2]や*(p+2)は7
です
配列変数を関数に渡すときは、要素全部を渡すことは
できないので、先頭のアドレスを渡します
再帰はCだと楽ですね
Cはポインターを使うと計算量を減らせます
p = a + iなら、a[i] と *p は同じ値ですが
次の要素を読むとき、i++ と p++ の後、
a[i] は a+iを計算後その場所を読むのに対して、
*p は pが示す場所を読むだけで、
a+iの計算を省ける分、速くなります
Cはアセンブラに近い書き方も出来るので
高速化しやすいですね
C(ポインター)をアセンブラで書きました
ただし、quicksortの部分のみです
Cのポインターは、int *p; p++; でpはint型1個分の
4バイト分増加します
アセンブラではint型を参照するときはinc edx (1増加)
ではなくadd edx,4 (4増加)で4バイト分増加させる必要
があります
コンパイラーによってint型のビット数が異なりますので、
intをlong(32ビット = 4バイト)に変えてあります
#pragma optimize( "", off ) コンパイラーの最適化禁止
#pragma optimize( "", on ) コンパイラーの最適化許可
は、コンパイラーに最適化指定したとき、「アセンブラが
最適化ができない」というエラーが出るのを防ぐために
入れてありますデバッグモードで使うなどエラーが出ない
場合は無くてもかまいません
アセンブラはレジスタの選び方や命令の選び方などで
最適化の余地が多いのが良いですね
書き換えて最適化したりして遊んで見て下さい
Cコンパイラーなどは各自ご用意して下さい
NL-BASICとblg～.zip(qsort001.bas、qsort001.c、
qsort002.c、qsort002asm.c)は
このブログ(以下のリンク)からダウンロードできます
