forummsgid131304edit
Original date:20170811 16:59:18 Edited by: petelomax Subject: Re: Natural sort comparison
I found a way to improve quick_sort for the all1s case, along with a minor speedup for the swap:
function quick_sort(sequence s) sequence qstack integer first, last, stackptr, I, J object tmp, pivot object pivot, ti, tj qstack = repeat(0,floor((length(s)/5)+10))  create a stack first = 1 last = length(s) stackptr = 0 while 1 do while first<last do maybe?:  if lastfirst<=100 then  s[first..last] = insertion_sort(s[first..last])  exit  end if pivot = s[floor((last+first)/2)] I = first J = last while 1 do  while s[I]<pivot do while 1 do ti = s[I] if ti>=pivot then exit end if I += 1 end while  while s[J]>pivot do while 1 do tj = s[J] if tj<=pivot then exit end if J = 1 end while if I>J then exit end if if I<J then  added 6/8/17: if ti=tj then {I,J} = {J+1,I1} exit end if  tmp = s[I]  s[I] = s[J]  s[J] = tmp s[I] = tj s[J] = ti end if I += 1 J = 1 if I>J then exit end if end while if I<last then qstack[stackptr+1] = I qstack[stackptr+2] = last stackptr += 2 end if last = J end while if stackptr=0 then exit end if stackptr = 2 first = qstack[stackptr+1] last = qstack[stackptr+2] end while return s end function
Which makes it the clear winner across the board in my "Compare_sorting_algorithms.exw".
Given the performance boost that qstack gives to quick_sort, I wonder whether a similar technique could be applied to merge_sort, likewise turning it from a recursive algorithm to an iterative one, and whether merges could be performed insitu. I jotted down some outline thoughts:
A stack of length log2 might be enough? Or even ceil(log2(n))6 if we farm out length<=64 to insertion_sort.
Consider the merge operation of merge_sort, being performed insitu.
(Note that <done> may in fact be a segment awaiting a future merge with merge(A,B))
xxxxxx,a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 <done> < A > < B >
Now, if we pick a1, then all that happens is that A shrinks. A' and B remain sorted.
If we pick b1, then a1 must move into that slot. At this stage the rest of B remains sorted, whereas A becomes (not for long) a stillsortedbutnowcircular list.
At some point, however, the circular list aspect of A breaks down (assuming we would rather not physically reorder it), eg:
xxxxx,b1,b2,b3,a4,a5,a1,a2,a3,b4,b5 < done > < A > <B>
(pick a1)
xxxxx,b1,b2,b3,a1,a5,a4,a2,a3,b4,b5 < done > < A > <B>
The obvious solution is to maintain A as a linked list, which can be done using a parallel sequence links, initially the same size as the sequence x being sorted.
There may be opportunities to preset that links sequence during some prior merge operation (but probably not if we palm off short sequences to insertion_sort).
Lastly, if the merge terminates because A became empty, then any remainder of B is already in place, whereas if B becomes empty, then A must be reordered, using the same linked list, obviously with nullops for any head(A)==A[1].
Pete
Not Categorized, Please Help
