quick sort analysis and behaviour

Question

I am reading about quick sort algoritm in book titled Algorithms 4th edition Robert Sedgewick.

Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications. The quicksort algorithm’s desirable features are that it is in-place (uses only a small auxiliary stack) and that it requires time proportional to N log N on the average to sort an array of length N. None of the algorithms that we have so far considered combine these two properties.

Furthermore, quicksort has a shorter inner loop than most other sorting algorithms, which means that it is fast in practice as well as in theory. Its primary drawback is that it is fragile in the sense that some care is involved in the implementation to be sure to avoid bad performance.

My questions on above text is

1. What does author mean by "uses only a small auxiliary stack" ?

2. What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

Request to explain with simple example.

Thanks

Answer 1

1 What does author mean by "uses only a small auxiliary stack" ?

In the ideal case, quicksort uses O(log2(n)) space on the stack, in the worst case, it uses O(n) space on the stack, taking up more space than the array being sorted.

2. What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

This probably doesn't matter much on a modern system, since any reasonably sized inner loop will fit within the code cache on most processors. Conditional branches will affect the pipeline performance, depending on branch prediction.

quicksort ... is substantially faster than any other sorting method in typical applications.

This isn't true, quick sort is only marginally faster (less than 10%) than merge sort in the best of cases, and much slower in the of worst cases, O(n^2) versus O(n log(n)). The main issue with merge sort is that it needs a temp array the same size or 1/2 the size of the original array.

Answer 2

1. What does author mean by "uses only a small auxiliary stack" ?

You need to also consider that quick-sort is in-place sorting algorithm.

in-place means:

• this in-place feature substantially reduces the storage requirement.
• it uses constant amount of storage (read: fixed number of extra variable) to facilitate the sorting process.

Therefore, because of small and fixed amount of storage, its said that quick-sort "uses only a small auxiliary stack".

2. What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms"?

By this it might mean that the logic inside the inner loop is simple and hence requires less code. This "shorter inner loop" should not confused with the number of times the loop iterates. Because on any level of recursion tree the total number of iteration would be "n" only.

Answer 3

1 What does author mean by "uses only a small auxiliary stack" ?

The author means very little extra memory is needed in addition to the data to sort. So there is no big overhead by a data structure generated during sorting.

2. What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

The author means the number of instruction to be performed in the innermost loop are quite view, this is a benefit for e.g. the cpu cache.

In the code below in the inner loops only an index is incremented/decremented. And of cause the loop-condition is checked.

As an example I take the implementation mentioned in wikipedia

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot
    do
        j := j – 1
    while A[j] > pivot
    if i >= j then
        return j
    swap A[i] with A[j]

Answer 4

function QuickSort(Array, Left, Right)
var
  L2, R2, PivotValue
begin
 Stack.Push(Left, Right);       // pushes Left, and then Right, on to a stack
 while not Stack.Empty do
 begin
     Stack.Pop(Left, Right);    // pops 2 values, storing them in Right and then Left
     repeat
         PivotValue := Array[(Left + Right) div 2];
         L2 := Left;
         R2 := Right;
         repeat
             while Array[L2] < PivotValue do // scan left partition
                 L2 := L2 + 1;
             while Array[R2] > PivotValue do // scan right partition
                 R2 := R2 - 1;
             if L2 <= R2 then
             begin
                 if L2 != R2 then
                     Swap(Array[L2], Array[R2]);  // swaps the data at L2 and R2
                 L2 := L2 + 1;
                 R2 := R2 - 1;
             end;
         until L2 >= R2;
         if R2 - Left > Right - L2 then // is left side piece larger?
         begin
             if Left < R2 then
                 Stack.Push(Left, R2);
             Left := L2;
         end;
         else
         begin
             if L2 < Right then // if left side isn't, right side is larger
                 Stack.Push(L2, Right);
             Right := R2;
         end;
     until Left >= Right;
 end;
 end;

1. What does author mean by "uses only a small auxiliary stack" ?

that you do not need a second array to store (like mergesort) it is calculated inside the same memory

What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

the very fast part of quicksort are the inner loops (// scan left partition and // scan right partition) because it is only increasing and a check... not more.