Saturday, July 16, 2011

Tail Recursion: Stack Optimization of Quick Sort

Following procedure implements QuickSort in recursive way –

QuickSort(Array, Left, Right)
{
If (Left >= Right)
{
Return
}
Else
{
Pivot <-- Partition(Array, Left, Right);

QuickSort(Array, Left, Pivot - 1);

QuickSort(Array, Pivot + 1, Right);
}
}

*Partition procedure mentioned above, rearranges the sub array Array[left..right]

Above procedure contains two recursive calls to itself. Once left sub array is recursively sorted and then right sub array is recursively sorted. This method demands for a stack space of ʘ(n).

To reduce the stack depth of the above method, second recursive call can be eliminated. This way we could get an optimization on stack depth without reducing the readability of the code.

QuickSort(Array, Left, Right)
{
If (Left >= Right)
{
Return;
}
Else
{
While(Left < Right)
{
Pivot <-- Partition(Array, Left, Right);

QuickSort(Array, Left, Pivot - 1);

Left <-- Pivot +1;
}
}
}

Stack depth of the modified version of QuickSort is ʘ(lgn).

Above optimization is called Tail recursion. Many compilers do this automatically for you. Unfortunately I could not see this optimization with C# compiler.

1 comment: