1.6 Quick Sort

Category Algorithm

Quick Sort is a sorting algorithm developed by Tony Hoare. On average, it sorts n items with Ο(nlogn) comparisons. In the worst-case scenario, it requires Ο(n²) comparisons, but this is rare. In fact, Quick Sort is often significantly faster than other Ο(nlogn) algorithms because its inner loop can be efficiently implemented on most architectures.

Quick Sort uses the divide-and-conquer strategy to divide a list into two sub-lists.

Quick Sort is also a typical application of the divide-and-conquer approach in sorting algorithms. Essentially, it can be seen as a recursive divide-and-conquer method based on Bubble Sort.

The name Quick Sort is straightforward and reflects its purpose: it is fast and efficient! It is one of the fastest sorting algorithms for handling large datasets. Although its worst-case time complexity reaches O(n²), it is still excellent, outperforming most sorting algorithms with an average time complexity of O(n logn) in many cases. However, the reason for this is unknown to me. Fortunately, my obsession led me to find a satisfactory answer in "Algorithm Art and Informatics Competition":

The worst-case runtime of Quick Sort is O(n²), for example, with a sorted sequence. However, its amortized expected time is O(nlogn), and the constant factor implied in the O(nlogn) notation is very small, much smaller than that in Merge Sort, which has a stable complexity of O(nlogn). Therefore, for most randomly ordered sequences with weak sequentiality, Quick Sort is generally superior to Merge Sort.

1. Algorithm Steps

Select an element from the list, called the "pivot";

Reorder the list so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation;

Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values;

2. Dynamic Demonstration

index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}

PHP

Example

function quickSort($arr)
{
if (count($arr) <= 1)
return $arr;
$middle = $arr[0];
$leftArray = array();
$rightArray = array();

for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] > $middle)
$rightArray[] = $arr[$i];
else
$leftArray[] = $arr[$i];
}
$leftArray = quickSort($leftArray);
$leftArray[] = $middle;

$rightArray = quickSort($rightArray);
return array_merge($leftArray, $rightArray);
}

C

Example

typedef struct _Range {
int start, end;
} Range;

Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}

void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}

void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // Avoid segment fault when len is negative
// r[] simulates list, p is quantity, r[p++] is push, r[--p] is pop and get element
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // Select midpoint as pivot
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // Check if elements on the left side of pivot meet the requirement
while (arr[right] > mid) --right; // Check if elements on the right side of pivot meet the requirement
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // Move pointers to continue
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}

Recursive Method

Example

void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}

void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}

C++

Function Method

sort(a, a + n); // Sort all numbers from a[0] to a[n-1].

Iterative Method

Example

// Reference: http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/
struct Range {
int start, end;
Range(int s = 0, int e = 0) {
start = s, end = e;
}
};
template &lt;typename T> // Can be used for integers or floating-point numbers, must define "<", ">", and ">=" operators for class objects
void quick_sort(T arr[], const int len) {
if (len <= 0)
return; // Avoid segment fault when len is negative
// r[] simulates stack, p is quantity, r[p++] is push, r[--p] is pop and get element
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
T mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right) left++;
while (arr[right] >= mid && left < right) right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
std::swap(arr[left], arr[range.end]);
else
left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}

Recursive Method

Example

template &lt;typename T>
void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
while (left < right) { // Search for elements smaller or larger than the pivot within the entire range and swap them on the left and right sides
while (arr[left] < mid && left < right) // Attempt to find an element larger than the pivot on the left side
left++;
while (arr[right] >= mid && left < right) // Attempt to find an element smaller than the pivot on the right side
right--;
std::swap(arr[left], arr[right]); // Swap elements
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
template &lt;typename T> // Can be used for integers or floating-point numbers, must define "<", ">", and ">=" operators for class objects
void quick_sort(T arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}

Reference addresses:

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md

https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

#

** Azierjiang

* bju**[email protected]

The above implementation does not include C#; I will add it as follows:

// QuickSort (target array, array start position, array end position)
static void QuickSort(int[] array, int left = 0, int right = -1)
{
if (right.Equals(-1)) right = array.Length - 1;
try
{
int keyValuePosition; // Record the index of the key value

// When the target array passed contains more than two elements, perform recursive calls. (i.e., when the target array contains only one element, this pass of sorting ends)
if (left < right)
{
    keyValuePosition = Partion(array, left, right);  // Get the index of the key value (core of quick sort)
    QuickSort(array, left, keyValuePosition - 1);    // Recursive call, quick sort the left interval
    QuickSort(array, keyValuePosition + 1, right);   // Recursive call, quick sort the right interval
}
}
catch (Exception ex)
{
    Console.WriteLine("Exception: {0}", ex);
}
}

/// Core part of quick sort: Determine the position of the key value in the array, thus dividing the array into two intervals, with the key value outside. (Returns the index where the key value should be in the array)
static int Partion(int[] array, int left, int right)
{
    int leftIndex = left;        // Record the starting position of the target array (subsequent dynamic left index)
    int rightIndex = right;      // Record the ending position of the target array (subsequent dynamic right index)
    int keyValue = array[left];  // The first element of the array as the key value
    int temp;
    // Break out of the loop when (left dynamic index == right dynamic index)
    while (leftIndex < rightIndex)
    {
        while (leftIndex < rightIndex && array[leftIndex] <= keyValue)  // Left dynamic index increases until it finds an index greater than keyValue
        {
            leftIndex++;
        }
        while (leftIndex < rightIndex && array[rightIndex] > keyValue)  // Right dynamic index decreases until it finds an index less than or equal to keyValue
        {
            rightIndex--;
        }
        if (leftIndex < rightIndex)  // If leftIndex < rightIndex, swap the values pointed to by the left and right dynamic indices; when leftIndex == rightIndex, break out of the entire loop
        {
            temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
        }
    }

    // When the left and right dynamic indices are equal (i.e., both indices point to the same position), the accurate position of keyValue can be determined
    temp = keyValue;
    if (temp < array[rightIndex])   // If keyValue < the value pointed to by both indices, swap keyValue with the value pointed to by rightIndex - 1, and return rightIndex - 1
    {
        array[left] = array[rightIndex - 1];
        array[rightIndex - 1] = temp;
        return rightIndex - 1;
    }
    else // If keyValue >= the value pointed to by both indices, swap keyValue with the value pointed to by rightIndex, and return rightIndex
    {
        array[left] = array[rightIndex];
        array[rightIndex] = temp;
        return rightIndex;
    }
}

1.4 Shell Sort

Follow on WeChat

❮ Ascii Counting Sort ❯