Quicksort

Quicksort

PROBLEM

Given an array A. of N elements the result of sorting the array in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.N

ALGORITHM

Quicksort by C. A. R. Hoare is a sorting algorithm in place. It has a worst-case running time that is O(N**2); its expected running time is O(N*lgN).

PRACTICE

It is often the best practical choice for sorting because it is remarkably efficient on the average. The following table compares four sorting algorithms. The A. array includes the integers in the range 1 to Max=10,100,1000,40000.

Running time in seconds for N=10000
Algorithm Max = 100 Max = 1000 Max = 40000 Max = 99999

QUICKSORT 4.66 4.53 4.89 4.59

HEAPSORT 10.26 10.67 11.58 11.18

SHELLSORT 7.45 8.89 10.58 10.13

COUNTING_SORT 1.88 1.95 7.93 31.85

IMPLEMENTATION

Unit: nonrecursive internal subroutine

Global variables: array A. of arbitrary elements

Parameter: a positive integer N - number of elements in A.

Result: Reordering of input array such that
A.1<=A.2<=...<=A.N

QUICKSORT: procedure expose A.
parse arg N
S = 1; StackL.1 = 1; StackR.1 = N
do until S = 0
  L = StackL.S; R = StackR.S; S = S - 1
  do until L >= R
    I = L; J = R; P = (L + R) % 2
    if A.L > A.P
      then do; W = A.L; A.L = A.P; A.P = W; end
    if A.L > A.R
      then do; W = A.L; A.L = A.R; A.R = W; end
    if A.P > A.R
      then do; W = A.P; A.P = A.R; A.R = W; end
    X = A.P
    do until I > J
      do I = I while A.I < X; end
      do J = J by -1 while X < A.J; end
      if I <= J
        then do
          W = A.I; A.I = A.J; A.J = W
          I = I + 1; J = J - 1
        end
    end
    if J - L < R - I
      then do
        if I < R
          then do
            S = S + 1; StackL.S = I; StackR.S = R
          end
        R = J
      end
      else do
        if L < J
          then do
            S = S + 1; StackL.S = L; StackR.S = J
          end
        L = I
      end
  end /* until L >= R */
end /* until S = 0 */
return

For sorting in descending order, you need only change the red coloured statements

      do I = I while A.I > X; end
      do J = J by -1 while X > A.J; end

CONNECTIONS

Sorting Problem
     Counting sort
     Heapsort
     Shellsort
Merging

Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms

The MIT Press, Cambridge, 1990

Sedgewick R. Algorithms

Addison-Wesley, Reading, Massachusetts, 1984

Wirth N. Algorithms and data structure

New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986

Acknowledgement
I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.

Note
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.