Click here to Skip to main content
Click here to Skip to main content
Go to top

Optimizing QuickSort

, 6 Jan 2011
Rate this:
Please Sign up or sign in to vote.
Some things we can do to make QuickSort more efficient

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

  • 6th January, 2011: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

John Paul Walker

United States United States
No Biography provided

Comments and Discussions

 
GeneralOther optimisations Pinmemberjsc4210-Jan-11 4:37 
GeneralMy vote of 4 PinmemberJustDownload29-Jan-11 9:27 
General3 percent improvement in benchmark testing Pinmemberbob169729-Jan-11 3:53 
GeneralMy vote of 3 PinmemberEmilio Garavaglia7-Jan-11 6:10 
GeneralQuicksort PinmemberTed21026-Jan-11 22:15 
GeneralComments Pinmemberpeterchen6-Jan-11 22:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140922.1 | Last Updated 6 Jan 2011
Article Copyright 2011 by John Paul Walker
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid