Array Sorting Algorithms III

**whitey6993** · 02-07-2010, 06:14 AM

This tutorial is another installment of the "Array Sorting Algorithms" series. This installment will teach you one of the fastest methods of sorting arrays and arrays.

In the second installment of the series, Array Sorting Algorithms II, I showed the selection sort algorithm as a replacement for the simpler bubble sort. The selection sort is great, but lets say you really need speed. You need your array sorted as fast as possible. Then you need the Quick sort algorithm. Quicksort works by using a "divide-and-conquer" strategy. Lets take a look at the pseudo code for quick sort (taken from wikipedia).

Code:

 function quicksort(array)
     var list less, greater
     if length(array) = 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x = pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

The quick sort code is similar in difficulty to the selection sort. Open a new C++ file and enter the following code.

Code:

#include <iostream>

using namespace std;

void quicksort(int[]);

int main(void)
{
    return 0;
}

void quicksort(int[] unsorted)
{

}

Right now we have the basic information included for what we want to do. We include iostream and the std namespace as well as an empty main statement. We also declared a prototype for our sort function and started it off as an empty function. Now lets fill in our sort algorithm function based on the pseudo code.

Code:

    int i = left; j = right;
    int tmp;
    int pivot = unsorted[(left + right) / 2];
    
    //Partition function: divide array in half
    
    while(i <= j)
    {
        while(unsorted[i] < pivot)
            i++;
        while(unsorted[j] >pivot)
            j--;
        if (i <= j)
        {
            tmp = unsorted[i];
            unsorted[i] = unsorted[j];
            unsorted[j] = tmp;
            i++;
            j--;
        }
    }
    
    if (left < j)
        quicksort(unsorted, left, j);
    if (i < right)
        quicksort(unsorted, i, right);

The function starts by declaring a few variables. A start and end to the sort area, a temporary variable for when two numbers need to be switched, and a pivot point. Then we move onto the partition function which divides the array into two sections and sorts them if necessary. After that, based on whether the array needs to be re-partitioned and more sorting needs to occur, the function calls itself recursively. If no sorting needs to occur, the sorted array is returned.

To test it out, lets fill in the main function. Type in the following code inside the brackets of the main function.

Code:

    int unsorted[5];
    
    for(int i = 0; i < 5; i++)
    {
         cout << "Enter element number " << i + 1 << " of the array to be sorted: ";
         cin >> unsorted[i];
    }
    
    quicksort(unsorted, 0, 4);
    
    cout << endl << endl << "The sorted array is: ";
    for(int i = 0; i < 5; i++)
    {
         cout << unsorted[i];
         if (i != 4) cout << ", ";
    }
    
    cout << endl << endl;
    system("pause");     
    return 0;

Now compile the program, input 5 unsorted numbers, and the algorithm will output the sorted data. I wrote this program using arrays because I could not quite get the quicksort algorithm to work with vectors. I think it has something to do with the recursive nature of the algorithm and premature returning. If anyone can solve the problem, please post in the comments or in your own thread on this forum

. This code was written using Dev-C++, so it may need some tweaking in other compilers. The source code for this project is attached for convenience. If you would like to contribute to the information presented here, or would like to offer corrections, please post a reply.

Source Code: quicksort.zip (had a bit of trouble trying to attach to the post, so I decided to just host it at mediafire).