Click here to Skip to main content
12,701,051 members (30,340 online)
Click here to Skip to main content
Add your own
alternative version

Stats

18.8K views
170 downloads
7 bookmarked
Posted

Optimizing QuickSort

, 6 Jan 2011 CPOL
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

You may also be interested in...

Comments and Discussions

 
GeneralOther optimisations Pin
jsc4210-Jan-11 5:37
memberjsc4210-Jan-11 5:37 
GeneralMy vote of 4 Pin
JustDownload29-Jan-11 10:27
memberJustDownload29-Jan-11 10:27 
General3 percent improvement in benchmark testing Pin
bob169729-Jan-11 4:53
memberbob169729-Jan-11 4:53 
GeneralMy vote of 3 Pin
Emilio Garavaglia7-Jan-11 7:10
memberEmilio Garavaglia7-Jan-11 7:10 
GeneralQuicksort Pin
Ted21026-Jan-11 23:15
memberTed21026-Jan-11 23:15 
GeneralComments Pin
peterchen6-Jan-11 23:08
memberpeterchen6-Jan-11 23:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    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 | Terms of Use | Mobile
Web01 | 2.8.170118.1 | Last Updated 6 Jan 2011
Article Copyright 2011 by John Paul Walker
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid