This is a go fast bit for PB.
' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION string_sort(ByVal parray as DWORD,ByVal acnt as DWORD) COMMON as DWORD
#REGISTER NONE
PREFIX "!"
push 0
push acnt
push parray
call sbsort
END PREFIX
END FUNCTION
' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FASTPROC sbsort
PREFIX "!"
sub esp, &H14
push ebx
push ebp
push esi
mov esi, [esp+&H24]
push edi
mov edi, [esp+&H2C]
cmp edi, 10
jle sst1
sst18:
mov eax, edi
cdq
sub eax, edx
mov ebx, eax
xor ecx, ecx
sar ebx, 1
cmp edi, &H32
lea ebp, [edi-1]
jle sst2
mov ecx, [esp+&H30]
mov eax, edi
cdq
and edx, 7
add eax, edx
mov edi, eax
push ecx
sar edi, 3
lea eax, [edi+edi]
push eax
push edi
push 0
push esi
mov [esp+&H3C], eax
call med3func
mov edx, [esp+&H30]
push edx
mov [esp+&H20], eax
lea eax, [edi+ebx]
push eax
push ebx
sub ebx, edi
push ebx
push esi
call med3func
mov ecx, [esp+&H30]
push ecx
push ebp
mov edx, ebp
sub ebp, [esp+&H30]
sub edx, edi
push edx
push ebp
push esi
mov ebx, eax
call med3func
mov ecx, [esp+&H1C]
mov edi, [esp+&H2C]
mov ebp, eax
sst2:
mov eax, [esp+&H30]
push eax
push ebp
push ebx
push ecx
push esi
call med3func
mov edx, [esi+eax*4]
mov ecx, [esi]
mov [esi], edx
mov [esi+eax*4], ecx
mov ecx, [esi]
mov eax, [esp+&H30]
movsx ecx, BYTE PTR [ecx+eax]
mov ebx, 1
cmp edi, ebx
mov [esp+&H10], ecx
jle sst3
sst5:
mov edx, [esi+ebx*4]
movsx edx, BYTE PTR [edx+eax]
cmp edx, ecx
jne sst3
cmp ebx, edi
je sst4
add ebx, 1
cmp ebx, edi
jl sst5
sst3:
add edi, &H0FFFFFFFF
mov ebp, edi
mov eax, ebx
mov [esp+&H28], ebp
jmp sst6
lea ecx, [ecx]
sst6:
cmp eax, edi
jg sst7
' +++++++++++++++++++++++++++++++++++++++
sst10:
mov ecx, [esi+eax*4]
mov edx, [esp+&H30]
movsx edx, BYTE PTR [ecx+edx]
mov ebp, [esp+&H10]
cmp edx, ebp
jg sst8
jne sst9
mov edx, [esi+ebx*4]
mov [esi+ebx*4], ecx
mov [esi+eax*4], edx
add ebx, 1
sst9:
add eax, 1
cmp eax, edi
jle sst10
' +++++++++++++++++++++++++++++++++++++++
sst21:
mov ebp, [esp+&H28]
sst7:
mov edx, eax
sub edx, ebx
cmp ebx, edx
mov [esp+&H1C], edx
jg sst11
mov edx, ebx
sst11:
test edx, edx
jle sst12
mov ecx, eax
sub ecx, edx
lea ecx, [esi+ecx*4]
mov [esp+&H28], esi
mov [esp+&H14], ecx
mov [esp+&H18], edx
lea esp, [esp]
sst13:
mov edx, [esp+&H28]
mov edx, [edx]
mov ecx, [ecx]
mov [esp+&H20], edx
mov edx, [esp+&H28]
add DWORD PTR [esp+&H28], 4
mov [edx], ecx
mov ecx, [esp+&H14]
mov edx, [esp+&H20]
mov [ecx], edx
add ecx, 4
sub DWORD PTR [esp+&H18], 1
mov [esp+&H14], ecx
jne sst13
sst12:
mov edx, [esp+&H2C]
sub edx, ebp
mov ecx, ebp
sub ecx, edi
add edx, &H0FFFFFFFF
cmp ecx, edx
mov [esp+&H18], ecx
jg sst14
mov edx, ecx
sst14:
test edx, edx
jle sst15
mov ecx, [esp+&H2C]
sub ecx, edx
lea eax, [esi+eax*4]
lea ecx, [esi+ecx*4]
mov [esp+&H28], edx
lea ebx, [ebx]
' ------------------------------------
sst16:
mov edx, [eax]
mov [esp+&H20], edx
mov edx, [ecx]
mov [eax], edx
mov edx, [esp+&H20]
mov [ecx], edx
add eax, 4
add ecx, 4
sub DWORD PTR [esp+&H28], 1
jne sst16
' ------------------------------------
sst15:
mov eax, [esp+&H30]
mov ecx, [esp+&H1C]
push eax
push ecx
push esi
call sbsort
cmp DWORD PTR [esp+&H10], 0
je sst17
mov edx, [esp+&H30]
mov eax, [esp+&H2C]
add edx, 1
push edx
mov edx, [esp+&H20]
sub ebx, ebp
lea ecx, [ebx+eax-1]
push ecx
lea eax, [esi+edx*4]
push eax
call sbsort
sst17:
mov ecx, [esp+&H18]
sub edi, ebp
add edi, [esp+&H2C]
mov [esp+&H2C], ecx
lea esi, [esi+edi*4]
mov edi, ecx
sst20:
cmp edi, &H0A
jg sst18
sst1:
mov edx, [esp+&H30]
push edx
push edi
push esi
call insort
sst19:
pop edi
pop esi
pop ebp
pop ebx
add esp, &H14
ret &H0C
sst4:
test ecx, ecx
je sst19
add eax, 1
mov [esp+&H30], eax
jmp sst20
sst8:
cmp eax, edi
jg sst21
jmp sst22
lea ecx, [ecx]
sst22:
mov ecx, [esi+edi*4]
mov edx, [esp+&H30]
movsx edx, BYTE PTR [ecx+edx]
cmp edx, ebp
jl sst23
mov ebp, [esp+&H28]
jne sst24
mov edx, [esi+ebp*4]
mov [esi+edi*4], edx
mov [esi+ebp*4], ecx
sub ebp, 1
mov [esp+&H28], ebp
sst24:
sub edi, 1
cmp eax, edi
jg sst7
mov ebp, [esp+&H10]
jmp sst22
sst23:
cmp eax, edi
jg sst21
mov edx, [esi+edi*4]
mov ecx, [esi+eax*4]
mov ebp, [esp+&H28]
mov [esi+eax*4], edx
mov [esi+edi*4], ecx
add eax, 1
sub edi, 1
jmp sst6
' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
insort:
push ebx
push esi
push edi
push ebp
xor ebp, ebp
mov ebx, [esp+&H14]
sub DWORD PTR [esp+&H1C], 1
ist1:
add ebp, 1
test ebp, ebp
jle ist1
cmp ebp, [esp+&H18]
jge ist2
mov eax, ebp
ist5:
mov edx, [esp+&H1C]
mov esi, [ebx+eax*4]
mov edi, [ebx+eax*4-4]
ist4:
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
je ist1
add edx, 1
movzx ecx, BYTE PTR [edx+esi]
cmp cl, BYTE PTR [edx+edi]
jl ist3
jg ist1
test ecx, ecx
jne ist4
jmp ist1
mov edi, edi
ist3:
mov [ebx+eax*4], edi
mov [ebx+eax*4-4], esi
sub eax, 1
jg ist5
jmp ist1
ist2:
pop ebp
pop edi
pop esi
pop ebx
ret 12
' ¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤=÷=¤
med3func:
mov edx, [esp+4]
mov eax, [esp+8]
mov ecx, [edx+eax*4]
push ebp
mov ebp, [esp+&H10]
push esi
mov esi, [edx+ebp*4]
push edi
mov edi, [esp+&H20]
movsx ecx, BYTE PTR [ecx+edi]
movsx esi, BYTE PTR [esi+edi]
cmp ecx, esi
je med1
push ebx
mov ebx, [esp+&H20]
mov edx, [edx+ebx*4]
movsx edx, BYTE PTR [edx+edi]
cmp edx, ecx
je med2
cmp edx, esi
je med2
cmp ecx, esi
jge med3
cmp esi, edx
jl med4
cmp ecx, edx
jl med2
pop ebx
pop edi
pop esi
pop ebp
ret &H14
med3:
cmp esi, edx
jle med5
med4:
pop ebx
pop edi
pop esi
mov eax, ebp
pop ebp
ret &H14
med5:
cmp ecx, edx
jl med6
med2:
mov eax, ebx
med6:
pop ebx
med1:
pop edi
pop esi
pop ebp
ret &H14
END PREFIX
END FASTPROC
' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
i like the name :biggrin:
and they pick on me for "ling long kai fang" - lol
Hutch,
interesting code, indeed. Who is the inventor of the algorithm? Robert Sedgewick? I haven't found it in his book.
Gunther
I found it years ago searching the internet for C sort algos. Authors are Robert Sedgewick and Jon Bentley. I have not seen anything faster yet.
Quote from: hutch-- on January 01, 2015, 01:30:12 PM
Authors are Robert Sedgewick and Jon Bentley. I have not seen anything faster yet.
Unfortunately, I can't test it at the moment here. I've to purchase a new valid PBWin license in the next weeks. I hope the company is still running. Do you have some timings?
Gunther
Gunther,
You can get it off the PB site.
Quote from: hutch-- on January 01, 2015, 07:57:58 PM
Gunther,
You can get it off the PB site.
That's good news. My old AMD box with the right installation is out of order (could be the CMOS battery, but I'm not sure). I couldn't find the original key. But the PB compiler is worth the money.
Gunther
Gunther,
Depends on if you are used to working on computers but it would not be difficult to pull the hard disk and read it with a later computer.
I found the original article.
http://www.drdobbs.com/database/sorting-strings-with-three-way-radix-qui/184410724
Quote from: hutch-- on January 02, 2015, 02:20:35 AM
Gunther,
Depends on if you are used to working on computers but it would not be difficult to pull the hard disk and read it with a later computer.
That was my idea, too. The thing is, it's an old Toshiba laptop and changing the hard disk isn't an easy task. Thank you for the link to the Bentley and Sedgewick theory article.
Gunther