jsgray@watrose.UUCP (03/02/87)
In article <8515@watrose.UUCP> jsgray@watrose.UUCP (Jan Gray) writes: >There is a new result from Europe which shows it is possible to >quicksort with no extra space! > >I'll post more detailed information and the reference soon. And here it is. The paper is "Quicksort Without a Stack" Branislav Durian VUVT Zilina, k.u.o, Nerudova 33, 01001 Zilina, Czechoslovakia from Math. Foundations of Computation Theory, 1986. pp. 283-289. The following explanation is strongly borrowed from the paper. Assume you are going to quicksort each subfile left to right (we don't have to sort the smaller subfile first to keep the stack O(lg n), since we don't use a stack at all!). Standard quicksort would stack the right bound, sort the left subfile, and restore the right bound. Let's say your problem looks like p p' | | 4 1 3 2 5 9 6 8 7 10 12 14 18 S1 S2 S' i.e. you partitioned about 10, and about 5. You want to quicksort the left subfile S1 and remember how to return to S2. Ordinarily you would stack p', sort S1, and then S2 is the elements between p and p' (which you pop). Instead, swap p' and the first element of S2: p p' | | 4 1 3 2 5 10 6 8 7 9 12 14 18 S1 S2 S' Now you can identify S2 this way: S2 is the elements after p' which are smaller than p'. Once S2 is identified p' can be returned to its original place. Repeat until the entire array is sorted. For those of you who like to see pseudocode, here is a standard quicksort: 1 procedure SQS(var n : integer; var a : array[1..n+2] of integer); 2 { elements a[1..n]; sentinels a[n+1] = maxint-1, a[n+2] = maxint } 3 var p, i, j, l, r, m, s : integer; 4 begin 5 l := 1; r := n+1; m := 9; s := 0; 6 repeat begin 7 while r-l > m do begin 8 i := l; j := r; 9 p := a[l]; { or choose pivot as median of 3 elements } 10 repeat 11 repeat i := i+1 until a[i] >= p; 12 repeat j := j-1 until a[j] <= p; 13 if i < j then swap(a[i], a[j]); 14 until i >= j; 15 a[l] := a[j]; a[j] := p; 16 STACK[s] := r; s := s+1; { stack the position } 17 r := j 18 end 19 l := r+1; 20 if l <= n then begin 21 s := s-1; r := STACK[s] { unstack the position } 22 end 23 end until l > n; 24 insertsort(n) 25 end; We can eliminate the stack by replacing line 16 and line 21 with 16 swap(a[i], a[r]); { instead of stacking the position } 21a p := a[l]; r := l; 21b repeat r := r+1 until a[r] > p; 21c r := r-1; a[l] := a[r]; a[r] := p Note that line 21b does a linear search for the right bound. The paper states that this degrades performance by 30%. It then describes other modifications which cause this sort to be only 4-8% slower than standard quicksort. Who said you can't teach an old sort new tricks? Jan Gray jsgray@watrose University of Waterloo (519) 885-1211 x3870