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

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.

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: 1037