The quicksort is a beast. It was invented by C Hoare (I'm not making these names up) and works by splitting the list into ever smaller sublists which are easier to sort. The algorithm is fairly long and requires a bunch of procedures and functions.
If you have patiently messed around with each of the sorting algorithms on the site, you may have worked out that the Array class already has a sort method. That sort method uses a version of the quicksort algorithm which has deservedly gained a reputation for being one of the quickest ways to sort data.
static void QSort()
{
RecQSort(0, randomArray.GetLength(0) - 1);
}
static void RecQSort(int first, int last)
{
if ((last - first) <= 0)
{
return;
}
else
{
int part = Partition(first, last);
RecQSort(first, part - 1);
RecQSort(part + 1, last);
}
}
static int Partition(int first, int last)
{
double pivotVal = randomArray[first];
int thefirst = first;
bool okSide = true;
first += 1;
do
{
okSide = true;
while (okSide)
{
if (randomArray[first] > pivotVal)
{
okSide = false;
}
else
{
first += 1;
okSide = (first <= last);
}
}
okSide = (first <= last);
while (okSide)
{
if (randomArray[last] <= pivotVal)
{
okSide = false;
}
else
{
last -= 1;
okSide = (first <= last);
}
}
if (first < last)
{
Swap(first, last);
first += 1;
last -= 1;
}
}
while (first <= last);
Swap(thefirst, last);
return last;
}
static void Swap(int item1, int item2)
{
double temp = randomArray[item1];
randomArray[item1] = randomArray[item2];
randomArray[item2] = temp;
}