Compare QSort method to another

[B+]

This is a comparison of Qsort method to another being spread around BASIC forums:

'TITLE "Compare RussianSorting presented by Danilin to a Basic standard QuickSort by B+ 2018-10-28"

' Here is the only relevant parts of Danilin
n = 100000
DIM d(n)
DIM a(n)
DIM QS(n)

' Make a sample set of test data
FOR i = 1 TO n
   r = RND(0) * n
   d(i) = r
   QS(i) = r
NEXT

' Since Danilin does not provide us with "c:/N.txt" file data, can't be important to his demo
age = 1 + LOG(n) / LOG(2)
start = TIME$("ms")
IF age > 0 THEN
   CALL RussianSortingHalvesDAV 1, n, 1, age
END IF
finish = TIME$("ms")
PRINT (finish - start) / 1000; "second "
IF n > 100 THEN stopper = 100 ELSE stopper = n
FOR i = 1 TO stopper
   PRINT d(i); ", ";
NEXT
DanilinTime = (finish - start) / 1000
PRINT: PRINT: INPUT "Now for the Quick Sort Test, press enter..."; enter$
CLS

'now try good ole Quick Sort
start = TIME$("ms")
call qSort 1, n
finish = TIME$("ms")
PRINT (finish - start) / 1000; "sec."
IF n > 100 THEN stopper = 100 ELSE stopper = n
FOR i = 1 TO stopper
   PRINT d(i); ", ";
NEXT
QSortTime = (finish - start) / 1000
PRINT: PRINT: PRINT "Ha, ha, ha QSort took "; INT(QSortTime / DanilinTime * 1000) / 1000; " times longer than Danilin's Sort!"


SUB RussianSortingHalvesDAV ab, yz, part, age

   IF yz - ab < 1 THEN EXIT SUB

   FOR i = ab TO yz '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> really a time waster and String Array Buster here!!!!!
       summa = summa + d(i)
   NEXT
   middle = summa / (yz - ab + 1)

   abc = ab - 1
   xyz = yz + 1

   FOR i = ab TO yz
       IF d(i) < middle THEN abc = abc + 1: a(abc) = d(i): ELSE xyz = xyz - 1: a(xyz) = d(i)
   NEXT

   FOR i = ab TO yz: d(i) = a(i): NEXT

   IF part < age THEN
       IF abc >= ab THEN CALL RussianSortingHalvesDAV ab, abc, part + 1, age
       IF xyz <= yz THEN CALL RussianSortingHalvesDAV xyz, yz, part + 1, age
   END IF

END SUB

'QS is DIM SHARED to compare to Danilin's method that needs two DIM SHARED Arrays for his SUB
SUB qSort start, finish
   'DIM Hi AS LONG, Lo AS LONG, Middle AS SINGLE
   Hi = finish: Lo = start
   Middle = QS((Lo + Hi) / 2) 'find middle of array
   DO
       DO WHILE QS(Lo) < Middle: Lo = Lo + 1: LOOP
       DO WHILE QS(Hi) > Middle: Hi = Hi - 1: LOOP
       IF Lo <= Hi THEN
           t = QS(Hi)
           QS(Hi) = QS(Lo)
           QS(Lo) = t
           Lo = Lo + 1: Hi = Hi - 1
       END IF
   LOOP UNTIL Lo > Hi
   IF Hi > start THEN call qSort start, Hi
   IF Lo < finish THEN call qSort Lo, finish
END SUB


JB dies at n = 1000000 and at 100000 runs pretty slow. Rod said code runs fast in loop structures so I was disappointed how long this took. Maybe it needs to be non recursive or Rod was meaning code in LB runs faster.

[tsh73]

By auxiliary array of same size and constant copying between them,
looks like some variant of merge sort for me.

---

EDIT I run it and QSORT worked 2x faster then first sort.
(on my machine)

[B+]

Yes! It, RussianSortingHalves method, looks a bit like QSORT as well with allot of extra voodoo! ;-))

It adds up all the values in the array section and takes a sort of average, what is advantage of that? Oh, I see, it gives you time to get a cup of coffee. ;-))