#99 Article 1049 Posted at 1995/12/19 03:59:43 by MSP-Iris (MAP4370) [SAHOU.3]
Subject: Re: Re: Re: プログラミング作法・お題３ /1046 /1032 /1029
今までアップしたものはただの順位付けルーチンで、ソートとは厳密には
違う．．．というわけで、ちゃんとソートしました。ソートアルゴリズムは
最初のうちはバブルソート、途中で二分木に変わります（それぞれのルーチ
ンの１ループあたりの処理速度とループ回数期待値から、途中で変えるのが
得策と判断）。バブルソートの方も、いちいちスワップするんじゃなくて、
挿入位置を決定してから一気に処理してます。
昨日のルーチンをプリプロセッサとして使用しますので、仕様は同じです。
----------------------------
Art.1046 の ASM ルーチンをリンクして下さい(_SORTIT)。
----------------------------
magicn equ 16 ;バブルソートと二分木ソートの境目
.model small,c
.186
locals __
OKIKAE macro
mov cx,si
sub cx,di
push si
push di
add si,bx
mov di,si
dec si
rep movsb
pop di
pop si
mov ax,si
mov [bx+di+1],al
endm
HIKAKU macro X
mov bl,[bx+&X]
xor bh,bh
add bx,dx
mov al,[bx]
mov bx,dx
cmp [bx+si],al
mov bx,Aque
endm
.code
public SORTIU
SORTIU proc near uses SI DI ES,Arnk:word,Aque:word,Anum:word
mov ax,ds
mov es,ax
std
mov bx,Aque
mov dx,Arnk
xor ax,ax
mov si,ax
mov di,ax
mov ax,Anum
push ax
cmp ax,magicn
jbe iloop
mov Anum,magicn
iloop: inc si
mov di,si
__bubbleloop:
dec di
HIKAKU di ;バブルソートで挿入位置決定
jb __bubbleloop ;いちいちスワップしない
OKIKAE ;位置決定後一気に挿入
nexti: cmp si,Anum
jne iloop
pop ax
cmp ax,magicn
jbe fin
mov Anum,ax
iloop2: inc si
mov ax,si
mov [bx+si],al
mov di,si
mov cx,si
__treeloop:
shr cx,1 ;移動距離をどんどん半分（切り捨て）
and cx,cx
jnz __notzero
inc cx ;移動距離０だと永久ループなので
__notzero:
sub di,cx
HIKAKU di
jb __treeloop ;まだ上へ行ける
HIKAKU di+1 ;１つ下を見て
jbe __exittree ;ここで決定
add di,cx ;上へ行き過ぎなので戻す
jmp short __treeloop
__exittree:
OKIKAE
nexti2: cmp si,Anum
jne iloop2
fin: cld
ret
endp
end
----------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
extern void SORTIT (char *,char *,int,int);
extern void SORTIU (char *,char *,int);
void errend (s) char *s; {
printf("%s\n",s);
abort();
}
main (int argc,char *argv[]) {
static char mjstr[64][32]; static unsigned char rank[64],queue[64];
int i;
if(argc<2|argc>64)
errend("ソート対象は１～６３個です");
for(i=1;i<=argc-1;i++)
strncpy(mjstr[i],argv[i],31);
SORTIT(&mjstr[0][0],&rank[0],argc-1,32);
SORTIU(&rank[0],&queue[0],argc-1);
printf("順位 文字列\n");
for(i=1;i<=argc-1;i++)
printf("%2i %s\n",rank[queue[i]],argv[queue[i]]);
}
----------------------------
MAP4370 MSP-Iris