QuickSort port

[Dragokas]

Hi all !

Where can I find an experiments of arithmetic sorting functions of your forum ?
I made a port of Charles Hoar's QuickSort.
So, it's interesting to see something else to compare.

Code: Select all

@echo off
SetLocal EnableExtensions EnableDelayedExpansion

:: Set a count of numbers
set Count=30
:: Minimal and maximal numbers
set min=-100
set max=+100

:: Generation of numbers
for /L %%C in (1 1 %Count%) do set /a ar[%%C]=!random!%%(%max%-%min%+1)+%min%

echo Before:
call :PrintArray ar 1 %Count%
echo.
set t0=%time%
:: Sorting
call :qSort ar 1 %Count%
set t1=%time%
echo.
echo After:
call :PrintArray ar 1 %Count%
echo.
call :difftime
echo.
pause
exit /B


:qSort [arrayName] [lowBound] [upBound]
  :: port of Charles Hoar QuickSort
  :: maded by Alex Dragokas
  set i=%2
  set L=%3
  set /a M=(%i%+%L%)/2
  set M=!%1[%M%]!
  :_qSort_m0
  if %i% GTR %L% goto _qSort_m1
  :_qSort_m2
  if !%1[%i%]! GEQ %M% (goto _qSort_m3) else (set /a i+=1& goto _qSort_m2)
  :_qSort_m3
  if !%1[%L%]! LEQ %M% (goto _qSort_m4) else (set /a L-=1& goto _qSort_m3)
  :_qSort_m4
  if %i% GTR %L% goto _qSort_m5
  set wsp=!%1[%i%]!
  set %1[%i%]=!%1[%L%]!
  set %1[%L%]=%wsp%
  set /a i+=1, L-=1
  :_qSort_m5
  goto _qSort_m0  
  :_qSort_m1
  if %2 LSS %L% call :qSort %1 %2 %L%
  if %i% LSS %3 call :qSort %1 %i% %3
exit /B

:PrintArray [arrayName] [lowBound] [upBound]
  For /L %%C in (%2 1 %3) do echo %1[%%C]=!%1[%%C]!
exit /B

:difftime
  for /F "tokens=1-8 delims=:.," %%a in ("!t0: =0!:!t1: =0!") do set /a "a=(((1%%e-1%%a)*60)+1%%f-1%%b)*6000+1%%g%%h-1%%c%%d, a+=(a>>31) & 8640000, a*=10"
  echo Elapsed: %a% msec.
goto :eof

Results on my system shows that the speed mostly depends on the number of elements of array.

Count: 100
Speed: 960 msec..

Count: 200
Speed: 2200 msec.

Count: 1000
Speed: 14520 msec.

[Squashman]

You could always search.

[Squashman]

http://www.codeproject.com/Articles/203 ... ubble-Sort
I have always liked this bubble sort.

[einstein1969]

Hi,

This is a faster version. (the iterative version i think is faster than this)

Code: Select all

:: Quicksort by einstein1969
:qsort2
  set "sw1=%1[^!pi^!] ^^^^ %1[^!k^!]"
  set "sw2=%1[%%i] ^^^^ %1[^!a^!]"
  set "sw3=%1[^!a^!] ^^^^ %1[^!k^!]"
  set "s=0"
:qsort2_ric
     set /a "s+=1, i=%2, k=%3, pi=(i+k)/2"
     set /a pv=%1[!pi!]
     if !pi! neq !k! set /a "%1[!pi!]=%sw1%, %1[!k!]=%sw1%, %1[!pi!]=%sw1%"
     set /a a=i, ub=k-1
     for /L %%i in (!i!,1,!ub!) do (
      if !%1[%%i]! leq !pv! (
        if %%i neq !a! set /a "%1[%%i]=%sw2%, %1[!a!]=%sw2%, %1[%%i]=%sw2%"
        set /a a+=1
     ))
     if !a! neq !k! set /a "%1[!a!]=%sw3%,  %1[!k!]=%sw3%,   %1[!a!]=%sw3%"
     set /a p[!s!]=a, pm=p[!s!]-1
     if %2 lss !pm! call :qsort2_ric %1 %2 !pm!
     set /a pm=p[!s!]+1
     if !pm! lss %3 call :qsort2_ric %1 !pm! %3
     set /a s-=1
exit /b

einstein1969

[Ed Dyreen]

what is wrong with the internal sort command

Code: Select all

>(echo.3&echo.2&echo.1)|sort
1
2
3

>

?

[einstein1969]

what is wrong with the internal sort command

Code: Select all

>(echo.3&echo.2&echo.1)|sort
1
2
3

>

?

Is fast but less flexible:

Code: Select all

> (echo.3&echo.2&echo.1&echo.9&echo.10)|sort
1
10
2
3
9

EDIT: Think about sorting a color palette. With a generic sort can be done...

einstein1969

[einstein1969]

I have done a test. The algorithm is pretty linear (n*log(n)). The ratio is about 2.3 faster.


A=Quicksort
B=Quicksort Optmized

The code for the black&white Graph

Code: Select all

@echo off
SetLocal EnableExtensions EnableDelayedExpansion

rem Use raster 8x8 font

:: Set a Max count of numbers
set MaxCount=1500
:: Minimal and maximal numbers
set min=-100
set max=+100

:: Generation of numbers
for /L %%C in (1 1 %MaxCount%) do (
  set /a "ar[%%C]=!random!%%(%max%-%min%+1)+%min%"
  set /a save[%%C]=!ar[%%C]!
)

call :graph
pause

set Count=100

for /L %%C in (1 1 %Count%) do set /a ar[%%C]=!save[%%C]!

echo Before:
call :PrintArray ar 1 %Count%
echo.
set t0=%time%
:: Sorting
call :qSortA ar 1 %Count%
set t1=%time%
echo.
echo After:
call :PrintArray ar 1 %Count%
echo.
call :difftime
set a0=!a!
echo.

for /L %%C in (1 1 %Count%) do set /a ar[%%C]=!save[%%C]!

echo Before:
call :PrintArray ar 1 %Count%
echo.
set t0=%time%
:: Sorting
call :qSortB ar 1 %Count%
set t1=%time%
echo.
echo After:
call :PrintArray ar 1 %Count%
echo.
call :difftime
echo.
echo Previuos-Elapsed: %a0% msec.
echo.

echo checking 1 ...

for /L %%C in (1 1 %Count%) do (
  set ar[%%C]=
  set /a ar1[%%C]=!save[%%C]!
  set /a ar2[%%C]=!save[%%C]!
)
call :qSortA ar1 1 %Count%
call :qSortB ar2 1 %Count%

echo checking 2 ...

for /L %%C in (1 1 %Count%) do if !ar1[%%C]! neq !ar2[%%C]! echo Error. ar1[%%C] neq ar2[%%C] = !ar1[%%C]! neq !ar2[%%C]!

exit /B

:graph

mode 123,70

set /a p=0, max=-9999, maxy=64, maxX=120, Top=MaxCount

for /L %%x in (0,1,!maxX!) do ( set /a "v=%%x %% 12" 
   if !v! equ 0 (set "L_=!L_!|" & set "Ls=!Ls!|") else (set "L_=!L_!-" & set "Ls=!Ls! ") )

For /L %%c in (50,150,%Top%) do (

  set /a p+=1

  for /L %%C in (1 1 %%c) do set ar[%%C]=!save[%%C]!

  For %%T in (A;B) do (
    set t0=!time!
    call :qSort%%T ar 1 %%c
    set t1=!time!
    call :difftime
    if !a! gtr !max! set /a max=a

    set  time[%%T][!p!]=!a!
    set count[%%T][!p!]=%%c
  )

  :: empty buffer
  For /L %%y in (0,1,!maxy!) do for /L %%x in (0,1,!maxX!) do if defined b[%%y][%%x] set b[%%y][%%x]=

  :: fill
  For %%T in (A;B) do for /L %%p in (1,1,!p!) do (
    set /a "x=count[%%T][%%p]*maxX/top, y=!maxy!-time[%%T][%%p]*!maxy!/max"
    set b[!y!][!x!]=%%T
  )

  ::draw
  cls
  echo max_time:!max!cs count=%%c #test=!p! top_count:!Top!
  For /L %%y in (0,1,!maxy!) do (
    set L=
    set V=1
    for /L %%x in (0,1,!maxX!) do if defined b[%%y][%%x] set V=0
    if !V! equ 1 (
       set /a "o=%%y %% 8"
       if !o! equ 0 (set L=!L_!) else set L=!Ls!
    ) else (
      for /L %%x in (0,1,!maxX!) do if defined b[%%y][%%x] (
          set "L=!L!!b[%%y][%%x]!"
        ) else (
          set /a "v=%%x %% 12" & if !v! equ 0 (set "L=!L!|"
            ) else (
              set /a "o=%%y %% 8"
              if !o! equ 0 (set "L=!L!-") else set "L=!L! "
            )
        )
    )
    echo( !L!
  )
)
exit /b

:qSortA [arrayName] [lowBound] [upBound]
  :: port of Charles Hoar QuickSort
  :: maded by Alex Dragokas
  set i=%2
  set L=%3
  set /a M=(%i%+%L%)/2
  set M=!%1[%M%]!
  :_qSort_m0
  if %i% GTR %L% goto _qSort_m1
  :_qSort_m2
  if !%1[%i%]! GEQ %M% (goto _qSort_m3) else (set /a i+=1& goto _qSort_m2)
  :_qSort_m3
  if !%1[%L%]! LEQ %M% (goto _qSort_m4) else (set /a L-=1& goto _qSort_m3)
  :_qSort_m4
  if %i% GTR %L% goto _qSort_m5
  set wsp=!%1[%i%]!
  set %1[%i%]=!%1[%L%]!
  set %1[%L%]=%wsp%
  set /a i+=1, L-=1
  :_qSort_m5
  goto _qSort_m0 
  :_qSort_m1
  if %2 LSS %L% call :qSortA %1 %2 %L%
  if %i% LSS %3 call :qSortA %1 %i% %3
exit /B

:: Quicksort by einstein1969
:qsortB
  set "sw1=%1[^!pi^!] ^^^^ %1[^!k^!]"
  set "sw2=%1[%%i] ^^^^ %1[^!a^!]"
  set "sw3=%1[^!a^!] ^^^^ %1[^!k^!]"
  set "s=0"
:qsort2_ric
     set /a "s+=1, i=%2, k=%3, pi=(i+k)/2"
     set /a pv=%1[!pi!]
     if !pi! neq !k! set /a "%1[!pi!]=%sw1%, %1[!k!]=%sw1%, %1[!pi!]=%sw1%"
     set /a a=i, ub=k-1
     for /L %%i in (!i!,1,!ub!) do (
      if !%1[%%i]! leq !pv! (
        if %%i neq !a! set /a "%1[%%i]=%sw2%, %1[!a!]=%sw2%, %1[%%i]=%sw2%"
        set /a a+=1
     ))
     if !a! neq !k! set /a "%1[!a!]=%sw3%,  %1[!k!]=%sw3%,   %1[!a!]=%sw3%"
     set /a p[!s!]=a, pm=p[!s!]-1
     if %2 lss !pm! call :qsort2_ric %1 %2 !pm!
     set /a pm=p[!s!]+1
     if !pm! lss %3 call :qsort2_ric %1 !pm! %3
     set /a s-=1
exit /b

:PrintArray [arrayName] [lowBound] [upBound]
  For /L %%C in (%2 1 %3) do echo %1[%%C]=!%1[%%C]!
exit /B

:difftime
  for /F "tokens=1-8 delims=:.," %%a in ("!t0: =0!:!t1: =0!") do set /a "a=(((1%%e-1%%a)*60)+1%%f-1%%b)*6000+1%%g%%h-1%%c%%d, a+=(a>>31) & 8640000, a*=10"
  echo Elapsed: %a% msec.
goto :eof

EDIT: Fixed code for test.

einstein1969

[penpen]

I have done a test. The algorithm is pretty linear (n*log(n)).

The complexity of (any) quicksort algorithm is OMEGA(n log(n)), and O(n^2).
In some versions of quicksort (for example randomized pivot element, or randomized input)
it is assumed that the probability of the worst case is too low to happen, so that the complexity therefore should be THETA(n log(n)).
But the probability is not zero, so the worst case may occur (=> in my eyes it stays an O(n^2) algorithm).

Worst case example of quicksort: Exact inverse sorted order (OP case example: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

penpen

[einstein1969]

I have done a test. The algorithm is pretty linear (n*log(n)).

The complexity of (any) quicksort algorithm is OMEGA(n log(n)), and O(n^2).
In some versions of quicksort (for example randomized pivot element, or randomized input)
it is assumed that the probability of the worst case is too low to happen, so that the complexity therefore should be THETA(n log(n)).
But the probability is not zero, so the worst case may occur (=> in my eyes it stays an O(n^2) algorithm).

Worst case example of quicksort: Exact inverse sorted order (OP case example: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

penpen

Hi penpen,

I known the complexity. This algorimths have a "patch" for the worst case of inverse sorted order or already sorted case.

You can try with my graph code and see that the complexity is "n log n" and not "n^2" ...

change:

Code: Select all

  set /a "ar[%%C]=!random!%%(%max%-%min%+1)+%min%"

with:

Code: Select all

set /a "ar[%%C]=MaxCount-%%C
rem or   set /a "ar[%%C]=%%C

einstein1969