14,972,394 members
Articles / General Programming / Algorithms
Article
Posted 6 Jan 2011

33.2K views
8 bookmarked

# Optimizing QuickSort

Rate me:
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

C++
```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:

C#
`if(Left < Pivot)   &&    if(Right > Pivot)  `

with:

C#
`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

## Share

 United States
No Biography provided

 First Prev Next
 Other optimisations jsc4210-Jan-11 4:37 jsc42 10-Jan-11 4:37