Sedgewick Bentley 3 way radix quicksort.

[hutch--]

This is a go fast bit for PB.

Code Select Expand


' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

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

' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤


[dedndave]

i like the name   

and they pick on me for "ling long kai fang" - lol

[Gunther]

Hutch,

interesting code, indeed. Who is the inventor of the algorithm? Robert Sedgewick? I haven't found it in his book.

Gunther

[hutch--]

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.

[Gunther]

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

[hutch--]

Gunther,

You can get it off the PB site.

[Gunther]

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

[hutch--]

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

[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.

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