The essay mainly inspired by the quicksort with C++ in www.geeksforgeeks.org

Now, I am studying the algorithm again and this is rather the technical essay in English for me to practice..

The code

# include<stdio.h>
# include<random>
# include<iostream>

int xnum = 0;
void printArray(int arr[], int size);

// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
    std::cout << "partition(pivot,log,high,i):" << pivot << "," << low << "," << high << "," << i << "\n";
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            std::cout << "swap:pivot,i,j:" << pivot << "," << i << "," << j << "\n";
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
            std::cout << "after swap:arr[i], arr[j]:" << arr[i] << "," << arr[j] << "\n";
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    printf("\n");
    if (low < high)
    {
        printf("low < high\n");
        printArray(arr, xnum);
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
        std::cout << "pi:" << pi << "\n";
        printArray(arr, xnum);
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        printf("====between====\n");
        quickSort(arr, pi + 1, high);
    }
    else printf("high >= low\n");
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
    printf("\n");
}

// Driver program to test above functions
int main()
{
    std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rand100(8, 16);
    std::uniform_int_distribution<> rand10(0, 9);
    int num = rand100(mt);
    xnum = num;
    int arr[num];
    for(int i=0;i<num;i++) {
         arr[i] = rand10(mt);
    }
    printf("# ");
    printArray(arr, num);
    //int n = sizeof(arr)/sizeof(arr[0]);
    printf("#################################################\n");
    quickSort(arr, 0, num-1);
    printf("\nSorted array: n\n");
    printf("# ");
    printArray(arr, num);
    return 0;
}

Impressions

• Especially concerning some programming contests, you may use C/C++ to understand better how CPU and memory work.
• Though the quicksort is well known as the fast algorithm of sort, in a specific implementation there are many ways to do it.
• Perhaps it's the key to use the global arary for swapping in that.

About the license

• GeeksforGeeks: www.geeksforgeeks.org seems to provides them under CC BY-SA 4.0. If you would be concerned about it, please check the below links.
  https://creativecommons.org/licenses/by-sa/4.0/