From Clomosy Docs
Quick Sort, like Merge Sort, works on the divide and conquer principle. A pivot element is selected in the array, which serves as a reference point. Values smaller than the pivot are moved to its left, and values larger than the pivot are moved to its right. Then, the same process is applied recursively to the sub-arrays on the left and right of the pivot. As a result, the array becomes sorted.
Steps:
- Select a pivot element.
- Use the pivot to partition the dataset into two sub-arrays: elements smaller than the pivot and elements greater than the pivot.
- Recursively sort the sub-arrays using Quick Sort.
- Combine the sub-arrays and the pivot.
Example
var
arr: array[0..6] of Integer;
i: Integer;
str: string;
void swap(a, b: Integer);
var
temp: Integer;
{
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(low, high: Integer): Integer;
var
pivot, i, j: Integer;
{
pivot = arr[high];
i = low - 1;
for (j = low to high - 1)
{
if (arr[j] < pivot)
{
i = i + 1;
swap(i, j);
}
}
swap(i + 1, high);
Result = i + 1;
}
void quickSort(low, high: Integer);
var
pi: Integer;
{
if (low < high)
{
pi = partition(low, high);
quickSort(low, pi - 1);
quickSort(pi + 1, high);
}
}
{
arr[0] = 12;
arr[1] = 11;
arr[2] = 13;
arr[3] = 5;
arr[4] = 1;
arr[5] = 7;
arr[6] = 9;
str = 'Unordered array: ';
for (i = 0 to Length(arr)-1)
{
str = str + IntToStr(arr[i]) + ' ';
}
ShowMessage(str);
quickSort(0, Length(arr)-1);
str = 'Array sorted from smallest to largest: ';
for (i = 0 to Length(arr)-1)
{
str = str + IntToStr(arr[i]) + ' ';
}
ShowMessage(str);
str = 'Array sorted from largest to smallest: ';
for (i = Length(arr)-1 downto 0)
{
str = str + IntToStr(arr[i]) + ' ';
}
ShowMessage(str);
}