timing program for sort routine's

General FreeBASIC programming questions.
deltarho[1859]
Posts: 732
Joined: Jan 02, 2017 0:34
Location: UK

Re: timing program for sort routine's

Postby deltarho[1859] » Oct 25, 2017 10:17

We may in for a surprise with counting_pines's code. I read a thread at Stack Overflow where a guy reckoned that the best method for four numbers was to unroll the code into nothing but 'IF's. However, as the numbers to sort increased the method becomes increasingly unwieldy.
jj2007
Posts: 181
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: timing program for sort routine's

Postby jj2007 » Oct 26, 2017 0:14

I've played with frisian's code, trying to increase the array size:

Code: Select all

                         Array size = 100000

                  reversed     random       sorted       equal
     shellsort    0.017 sec    0.141 sec    0.005 sec    0.005 sec
   MDquicksort   14.610 sec    0.021 sec   13.643 sec    0.011 sec
        YQSort    0.007 sec    0.024 sec    0.006 sec    0.011 sec
    QuickSort2    0.006 sec    0.023 sec    0.005 sec    0.011 sec


It seems that MDquicksort has a problem: when increasing array size a bit more, it takes ages, and I have to kill it with Ctrl C. Is that normal? Is MDquicksort a built-in FB function? YQSort and QuickSort2 behave much better:

Code: Select all

                         Array size = 1000000

                  reversed     random       sorted       equal
     shellsort    0.216 sec    2.585 sec    0.062 sec    0.062 sec
        YQSort    0.073 sec    0.286 sec    0.070 sec    0.130 sec
    QuickSort2    0.064 sec    0.270 sec    0.061 sec    0.126 sec


P.S.: My own routine, a radix sort, is also stable for higher counts (more):

Code: Select all

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
Sort took 1930 ms for 10000000 elements (random)
Sort took 723 ms for 10000000 elements (sorted)
Sort took 734 ms for 10000000 elements (reversed)


Does anybody know what happened to the table sort, see this 2010 FreeBasic thread?
dafhi
Posts: 965
Joined: Jun 04, 2005 9:51

Re: timing program for sort routine's

Postby dafhi » Oct 26, 2017 5:19

inspired by selection sort

Code: Select all

SUB sort4(a() as single) '4 element array sort by dafhi - 2017 Oct 26
 
  var l=lbound(a), u=ubound(a), ilo=l, ihi=l
 
  for i as long = l+1 to u
    if a(i)<a(ilo) then: ilo=i
    elseif a(i)>a(ihi) then: ihi=i:  endif
  Next

  swap a(l), a(ilo):  if ihi=l then ihi=ilo
  swap a(ihi), a(u):  l+=1: u-=1
  if a(l)>a(u) then swap a(l), a(u)

END SUB

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests