Printable Version of Topic

Click here to view this topic in its original format

Dream.In.Code _ C++ Tutorials _ Recursive Quicksort Algorithm

Posted by: LifeHacker 17 Nov, 2008 - 12:56 PM

This is a quicksort algorithm and is used to sort numbers in ascending order held within an array. I will start by initialising the basic parts of the program, including libraries etc...

CODE

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

void quicksort(int *lp, int *rp);
int passes = 0;

int main()
{
    int arraylength = 5000;
    int sortarray[arraylength];
    srand(time(NULL));
    for (int i = 0; i < arraylength; i++){
        sortarray[i] = rand() %100;
        //cout<<sortarray[i]<<endl;
    }

Up to this point all the program is doing is creating an array to work with, and filling it with random numbers. The bit of code below then passes the first and last elements of the array, by reference, to a function called quicksort.

CODE

    quicksort(&sortarray[0], &sortarray[arraylength-1]);
    /*for (int i = 0; i < arraylength; i++){
        cout<<sortarray[i]<<", ";
    }*/
    //cout<<endl;
    cout<<"passes: "<<passes<<endl;
    return 0;
}

Below is the quick sort function. All it basically does is finds the pivot point of the array, generally the middle point and then works from the very most left point of the array and checks whether it is bigger then the pivot. If it is not then it moves to the next until it finds a number that is greater than the pivot. The algorithm then works from the right checking whether the number is less than the pivot. When it has then found two numbers it swaps them. It continues to do this until all the numbers on the left are less than the pivot and all the numbers on the right are greater than the pivot.

CODE

void quicksort(int *lp, int *rp){
    passes++;
    int arraysize = (rp-lp)+1;
    if(arraysize > 1){
        int *pivot = (lp+(arraysize/2));
        int swap = 0;
        int *origl = lp;
        int *origr = rp;
        while (lp != rp){
            while (*lp < *pivot){
                lp++;
            }
            while (*rp > *pivot){
                rp--;
            }
            if (lp == pivot){
                pivot = rp;
            }
            else if (rp == pivot){
                pivot = lp;
            }
            swap = *lp;
            *lp = *rp;
            *rp = swap;
            if((*lp == *pivot) || (*rp == *pivot)){
                break;
            }
        }
        quicksort(origl, pivot-1);
        quicksort(pivot+1, origr);
    }
}

Lastly the algorithm recursively calls itself passing the only the first half of the array to the function and then does the same thing as above. It then passes itself the second half of the array and does the same thing as mentioned above. It repeats this until all of the numbers are in ascending order. The algorithm knows when they are all in ascending order when no swaps have to be made.

A copy of this code can be found here:

main.cpp.rtf ( 1.37k ) Number of downloads: 160

Posted by: fuzzylunkinz 8 Jan, 2009 - 09:22 PM

Thanks for this tutorial!

I had been trying to do it in C# previously, and couldn't figure it out - so I left it alone.

Then I saw this and I realized I was forgetting one thing. I converted some things to C# and it doesn't work right 100% of the time. Where is my error?

csharp


public static int cells = 0;
public static uint passes = 0;
public static int[] array;
public static void Main(string[] args)
{
	Console.BufferHeight = Int16.MaxValue - 1;
	Random rn = new Random();
	Console.Write("How many cells in the array? ");
	cells = Convert.ToInt32(Console.ReadLine());
	array = new int[cells];
	for(int c = 0; c < cells; c++)
		array[c] = rn.Next(0, 100);
	Console.WriteLine("Original array:");
	writeArray();
	
	quickSort(0, cells-1);
	
	Console.WriteLine("Number of passes: {0}\nSorted array:", passes);
	writeArray();
	Console.WriteLine("\n");
	Console.Write("\nPress any key to continue . . . ");
	Console.ReadKey(true);
}
public static void writeArray()
{
	for(int c = 0; c < cells; c++)
		Console.Write("{0} ", array[c]);
	Console.WriteLine();
}
public static void quickSort(int leftPoint, int rightPoint)
{
	passes++;
	int arrayLength = rightPoint - leftPoint + 1;
	if(arrayLength > 1)
	{
		int a = leftPoint, z = rightPoint, p = a+(arrayLength/2), temp = 0;
		while(a != z)
		{
			while(array[a] < array[p])
				a++;
			while(array[z] > array[p])
				z--;
			if(a == p)
				p = z;
			else if (z == p)
				p = a;
			temp = array[a];
			array[a] = array[z];
			array[z] = temp;
			if(array[a] == array[p] || array[z] == array[p])
				break;
		}
		quickSort(leftPoint, p-1);
		quickSort(p+1, rightPoint);
	}
}

Posted by: LifeHacker 23 Jan, 2009 - 04:02 PM

I'll get back to you this afternoon after i have fully read your code and run through it

Posted by: LifeHacker 24 Jan, 2009 - 12:58 PM

Firstly i am no expert with C# as I have never learnt it, so this post may be incorrect depending upon my understanding of the language. But i think, from what i am seeing, your problem lies with the number of cells you have. From what i am seeing, you have no control over how many cells you have, so lets say that the computer makes 100 cells in you program and then randomly generates the numbers to put into the array.

Now lets say that the array contains, somewhere in the middle, the number 99. This is the same number that was passed to the quicksort function.

CODE

quickSort(0,cells-1);

Therefore when you execute this line:

CODE

while(a != z){
...
}

eventually the program will fail, because this condition is now terminated. Therefore with your program, how it is, you could probably not have the same number occur in your array twice, nor could you have the array contain a number that is one less than you cell count. You should be able to solve this problem by having your program check whether the memory address of 'a' is not equal to the memory address of 'z'.

I hope this helps

Posted by: cmaster 13 Apr, 2009 - 01:27 AM

http://simpleprogrammingtutorials.com/tutorials/sorts/quicksort.php