Quick Sort

Quicksort

Quicksort is an important algorithm, often listed alongside the Fourier transform among the twentieth century's major algorithms.

Its speed comes from divide and conquer. Choose a pivot each round, move smaller items to one side and larger ones to the other, and split the sequence into two subproblems.

The simplest pivot is the first item. But sorting a reversed sequence this way produces extremely uneven partitions: the pivot is always an extreme value, settling only itself each round. In this case quicksort requires a linear number of levels and degrades to $O(n^2)$ .

A randomly selected pivot reduces this risk, including for reversed inputs. It still has some probability of selecting an extreme value: for m distinct items, the probability is $2/m$ .

How do we move the smaller and larger values to the appropriate sides?

Consider an eight-item sequence. Select pivot and set left and right pointers at its two ends.

Start at right. If its value is greater than or equal to pivot, move right leftward. If smaller, fill the left hole with that value and advance left.

Now inspect left. If its value is smaller than or equal to pivot, move left rightward. If larger, fill the right hole with that value and move right leftward.

Repeat the same steps:

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Once the pointers meet, place the saved pivot in that position. Values on its left are no greater than pivot, and values on its right are no smaller.

Algorithm analysis

Under divide and conquer, each range splits into two subranges, which split again until no further division is needed. Average behavior has $\log n$ levels, yielding average time $O(n\log n)$ .

Time	Recursion space	Stability	Design idea
Average $O(n\log n)$ , worst $O(n^2)$	Average $O(\log n)$ , worst $O(n)$	Unstable	Divide and conquer

Quicksort

The text's diagrams use hole filling. The supplied code uses two-pointer exchanges: both partition correctly, but their movement steps differ.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        T pivot = arr[start];

        int pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Random pivot selection

One partition places values no greater than the pivot on one side and values no smaller on the other; recursive calls then sort the two sides.

Always using the first value performs poorly on an ordered array. Choosing a pivot randomly within the active range helps mitigate this situation.

Random pivot selection

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = rand() % (end - start + 1) + start;
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Median of three

Random pivots reduce the chance of bad partitions but leave the $O(n^2)$ worst case. Another approach uses the median of the values at start, mid, and end.

Median of three

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = median_of_three(arr, start, end);
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Median of three with insertion sort

For very small or partly ordered arrays, insertion sort can outperform quicksort. Once partitioning reaches a small range, sort it directly by insertion.

Median of three with insertion sort

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start >= end) {
        return;
    }
    if (end - start <= INSERTION_SORT_THRESHOLD) {
        T temp[end - start + 1];
        memcpy(temp, arr + start, sizeof(T) * (end - start + 1));
        insertion_sort(temp, end - start + 1);
        memcpy(arr + start, temp, sizeof(T) * (end - start + 1));
        return;
    }

    int pivot_index = median_of_three(arr, start, end);
    swap(arr[start], arr[pivot_index]);
    T pivot = arr[start];

    pivot_index = partition(arr, start, end, pivot);
    __quick_sort(arr, start, pivot_index - 1);
    __quick_sort(arr, pivot_index + 1, end);
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

These are the supplied programs. The commented-out C base partition helper is restored, and the small-range optimization now checks empty ranges. C++ variable-length arrays are replaced with standard vector; the sorting procedure is otherwise retained.

QUESTION

After one quicksort partition, which positions are fixed in their final locations?

QUESTION

Why must hole partitioning handle equality with the pivot?

Partition [5,8,2,7,1,6] once using the text’s hole method, pivot 5. Record pointer moves, hole-filling arrays using ∅, the pivot’s final position, and the next two ranges. Do not recursively sort them.

Quick Sort

Quicksort

Quicksort is an important algorithm, often listed alongside the Fourier transform among the twentieth century's major algorithms.

Its speed comes from divide and conquer. Choose a pivot each round, move smaller items to one side and larger ones to the other, and split the sequence into two subproblems.

A randomly selected pivot reduces this risk, including for reversed inputs. It still has some probability of selecting an extreme value: for m distinct items, the probability is $2/m$ .

How do we move the smaller and larger values to the appropriate sides?

Consider an eight-item sequence. Select pivot and set left and right pointers at its two ends.

Start at right. If its value is greater than or equal to pivot, move right leftward. If smaller, fill the left hole with that value and advance left.

Now inspect left. If its value is smaller than or equal to pivot, move left rightward. If larger, fill the right hole with that value and move right leftward.

Repeat the same steps:

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Once the pointers meet, place the saved pivot in that position. Values on its left are no greater than pivot, and values on its right are no smaller.

Algorithm analysis

Under divide and conquer, each range splits into two subranges, which split again until no further division is needed. Average behavior has $\log n$ levels, yielding average time $O(n\log n)$ .

Time	Recursion space	Stability	Design idea
Average $O(n\log n)$ , worst $O(n^2)$	Average $O(\log n)$ , worst $O(n)$	Unstable	Divide and conquer

Quicksort

The text's diagrams use hole filling. The supplied code uses two-pointer exchanges: both partition correctly, but their movement steps differ.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        T pivot = arr[start];

        int pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Random pivot selection

One partition places values no greater than the pivot on one side and values no smaller on the other; recursive calls then sort the two sides.

Always using the first value performs poorly on an ordered array. Choosing a pivot randomly within the active range helps mitigate this situation.

Random pivot selection

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = rand() % (end - start + 1) + start;
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Median of three

Random pivots reduce the chance of bad partitions but leave the $O(n^2)$ worst case. Another approach uses the median of the values at start, mid, and end.

Median of three

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = median_of_three(arr, start, end);
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Median of three with insertion sort

For very small or partly ordered arrays, insertion sort can outperform quicksort. Once partitioning reaches a small range, sort it directly by insertion.

Median of three with insertion sort

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start >= end) {
        return;
    }
    if (end - start <= INSERTION_SORT_THRESHOLD) {
        T temp[end - start + 1];
        memcpy(temp, arr + start, sizeof(T) * (end - start + 1));
        insertion_sort(temp, end - start + 1);
        memcpy(arr + start, temp, sizeof(T) * (end - start + 1));
        return;
    }

    int pivot_index = median_of_three(arr, start, end);
    swap(arr[start], arr[pivot_index]);
    T pivot = arr[start];

    pivot_index = partition(arr, start, end, pivot);
    __quick_sort(arr, start, pivot_index - 1);
    __quick_sort(arr, pivot_index + 1, end);
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

These are the supplied programs. The commented-out C base partition helper is restored, and the small-range optimization now checks empty ranges. C++ variable-length arrays are replaced with standard vector; the sorting procedure is otherwise retained.

QUESTION

After one quicksort partition, which positions are fixed in their final locations?

QUESTION

Why must hole partitioning handle equality with the pivot?

Quick Sort

Quick Sort

Quicksort

Quick sort: the complete hole method

Algorithm analysis

Basic quick sort: two-pointer comparisons and swaps

Random pivot selection

Random-pivot quick sort: choose, then partition

Median of three

Median-of-three quick sort: compare three candidates

Median of three with insertion sort

Median of three with insertion sorting for small ranges

KNOWLEDGE QUIZ

KNOWLEDGE QUIZ

Trace one hole partition

Quick Sort

Quick Sort

Quicksort

Quick sort: the complete hole method

Algorithm analysis

Basic quick sort: two-pointer comparisons and swaps

Random pivot selection

Random-pivot quick sort: choose, then partition

Median of three

Median-of-three quick sort: compare three candidates

Median of three with insertion sort

Median of three with insertion sorting for small ranges

KNOWLEDGE QUIZ

KNOWLEDGE QUIZ

Trace one hole partition