Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Array Sorting Algorithms III

array

  • Please log in to reply
8 replies to this topic

#1 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 07 February 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).

 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.

#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.

    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.

    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).
  • 3

#2 ZekeDragon

ZekeDragon

    CC Leader

  • Retired Mod
  • PipPipPipPipPipPipPip
  • 1263 posts

Posted 07 February 2010 - 09:35 AM

You sort those arrays!

++whitey6993.rep;
  • 0
If you enjoy reading this discussion and are thinking about commenting, why not click here to register and start participating in under a minute?

#3 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 07 February 2010 - 12:34 PM

Thank you :)
  • 0

#4 James.H

James.H

    CC Devotee

  • Just Joined
  • PipPipPipPipPipPip
  • 569 posts

Posted 07 February 2010 - 12:56 PM

Great tut! +rep
  • 0

#5 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 07 February 2010 - 12:58 PM

Thanks!
  • 0

#6 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 07 February 2010 - 03:20 PM

Very nice. +rep
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#7 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 07 February 2010 - 04:41 PM

Thanks :)
  • 0

#8 genux

genux

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 76 posts

Posted 08 February 2010 - 04:07 AM

very nice tut+
  • 0
int coffeePerDay = 10; // need to cut down!!!
Codingfriends

#9 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 08 February 2010 - 07:41 AM

Thank you
  • 0





Also tagged with one or more of these keywords: array

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download