Optimizing QuickSort

• Download Optimizing QuickSort - 940 B

Introduction

In productivity, there are two variables which are always a concern: time and space. In terms of computing, these are speed and memory. QuickSort, as the overall fastest sorting algorithm, has had people combing over it for nearly 50 years, so there isn't really much left to do as far as directly increasing its speed. However, there remain several ways that we can optimize it so that it can make much better use of its memory.

Background

Just have a good interest in sorting algorithms, and an understanding of QuickSort.

Changes

static void OptimizedQuickSort(ref int[] Arr, int Left, int Right)
{
    int Pivot;
    Pivot = Q_Sort(ref Arr, Left, Right);
    if(Left < Pivot - 1)
    {
        OptimizedQuickSort(ref Arr, Left, Pivot - 1);
    }
    if(Right > Pivot + 1)
    {
        OptimizedQuickSort(ref Arr, Pivot + 1, Right);
    }
}  

static int Q_Sort(ref int[] Arr, int Left, int Right)
{
    int Pivot;
    Pivot = Arr[Left];
    while(Left < Right)
    {
        while((Arr[Right] >= Pivot) && (Left < Right))
        {
            Right--;
        }
        if(Left != Right)
        {
            Arr[Left] = Arr[Right];
            Left++;
        }
        while((Arr[Left] <= Pivot) && (Left < Right))
        {
            Left++;
        }
        if(Left != Right)
        {
            Arr[Right] = Arr[Left];
            Right--;
        }
    }   
    Arr[Left] = Pivot;
    return Left;
}  

The biggest change I made was to separate QuickSort into two functions, so that, at first glance, it looks sort of like MergeSort. The idea for doing this is that instead of each new recursion copying the same code and using up more memory, it reuses the same code.
NOTE: This code only works properly when running a single thread. If you want to use QuickSort on multiple threads, use the standard version.

As a result of the algorithm being split up, we don't need a Temporary Left and Right variable in Q_Sort, because they are kept back in the original function that calls them, so the only variable we need in Q_Sort is the Pivot.

Next, if you look in the OptimizeQuickSort, you will see that I replaced the:

if(Left < Pivot)   &&    if(Right > Pivot)  

with:

if(Left < Pivot - 1)   &&    if(Right > Pivot + 1)   

My reasoning behind this is that, if there is one variable between Left and Pivot, then that variable must be Greater Than Left. What's more, it must be the only variable that is Less than Pivot that is greater than Left, so there is no reason to sort it. The same thing works for Pivot and Right.

End

Well, that's really all I've got. Just a few things that I think improve upon QuickSort, at least as far as managing memory. I would like to add that I have seen many other ways to make QuickSort more efficient, but nearly all of those advantages only worked on those languages, taking advantage of its features, whereas I wanted to work on the overall design.

If anyone can see any way to further improve upon what I've done here, or if you think this is a waste of time, let me know.

John

History

• 6^th January, 2011: Initial post