２進クイックソート、MSD・LSD基数整列法について

[孫六]

学校の課題で、for文とif文、特殊な変数を使わずに、以下のプログラム作れと言われました。

まず２進クイックソート(便宜上の名称です)という２進数に変換してからクイックソートをするプログラムを作れと言われました。
２進数に変換するまでの過程は一応出来ました(１０進数を２で割る→余り(０か１)を配列を使って一桁ずつ代入→出力)。
しかし、複数の数値を比較して、入れ替えるという過程がどうしても出来ません。


またMSD・LSD基数整列法は手も足も出ません。
なにかとクイックソートと関連性があるようなのですが、理解できません・・・
こちらは１０進数で良いようです

MSD基数整列法は例えば４５６、９８７３、３２という数値があった場合、
１０００で割って余りを比較する→値を降順に入れ替える→余りが同じなら、同じ数値のやつだけ１００で割って余りを比較するという流れでいいのですか？
また良いならプログラムを提示して頂けると非常に助かります。

LSD基数整列法に関しては全く分かりません・・・
一番下の桁から基数交換法で値を交換していけばいいのでしょうか・・・
自分でも何を言っているのか分かりませんが・・・

使っているOSはLinaxです

[Hermit]

http://www.geocities.jp/m_hiroi/light/pyalgo07.html
は参考になるでしょうか？
google で簡単に出てきますけど。

[zaku]

#include <stdio.h>
#define NM 3/*配列データ長*/
#define ZERO 0/*制御用初期値*/
int main(void){/*プログラム本文*/
int ap[NM]={456,9873,32};/*基本データ*/
int ia,ib,wk;/*配列制御用変数とスタックポインタ*/
for(ia=ZERO;ia<NM;ia++){/*1000で割る処理*/
printf("%d ",ap[ia]);/*ソート前の配列表現*/
ap[ia]%=1000;/*実際の割り算処理*/
putchar('\n');/*改行処理*/
}
for(ia=ZERO;ia<NM-1;ia++){/*並べ替え第一ループ*/
for(ib=ia+1;ib<NM;ib++){/*並べ替え第二ループ(実際の比較処理用のループ)*/
if(ap[ib]<ap[ia]){/*単純比較*/
wk=ap[ia];/*退避*/
ap[ia]=ap[ib];/*挿入*/
ap[ib]=wk;/*退避挿入*/
}
if(ap[ib]==ap[ia]){/*数値が､同じなら*/
ap[ib]%=100;/*更に100で割る*/
ap[ia]%=100;/*更に100で割る*/
if(ap[ib]<ap[ia]){/*更に単純比較*/
wk=ap[ia];/*退避*/
ap[ia]=ap[ib];/*挿入*/
ap[ib]=wk;/*退避挿入*/
}
}
}
}
for(ia=ZERO;ia<NM;ia++) printf("%d ",ap[ia]);/*処理後の数値表現*/
putchar('\n');/*改行処理*/
retunr(ZERO);/*プログラム終了*/
}

[孫六]

遅れて申し訳ありませんでした

＞Hermitさん
レスありがとうございます
そちらのサイトは前から読んでいたのですが、それをプログラムに書き出すとなると、ちょっと。。。。
理論的にはすごく参考になっています

＞zakuさん
レスどころかプログラムまで…ほんとにありがとうございます
ただごめんなさい。先生からは理論的に違うと指摘されました。
と言うのは９８７３を１０００で割ってint型の変数に入れると「９」で比較出来るのですが、
９８７３を１００で割ると「９８」で比較してしまうので、MSD基数整列法ではないと言われました＾＾；

MSD基数整列法をプログラムで実現するには、どうやら二次元配列を用いて、

a[j][0]　a[j][1]　a[j][2]　a[j][3]
a[0][n]　　９　　　８　　　　７　　　３
a[1][n]　　０　　　４　　　　５　　　６
a[2][n]　　０　　　０　　　　３　　　２

この状態でa[j][0]の列を比較して交換、a[j][1]の列を比較して交換、a[j][2]の列を比較して交換。。。
とした方が具合がいいようです

またMSD基数整列法なので、全てのソートが終わった時点で終了させなければならないみたいです…
これをforとifだけでと言われると、ちょっと追い付けないです…

LSDは逆にa[j][3]の列から比較していって、a[j][0]まで問答無用で比較していけばいいみたいです。

せっかく作って頂いたのに僕の知識と説明が至らず、本当に申し訳ありませんでした。