Quick Sort using C

Quick sort is a popular and efficient sorting algorithm that works by partitioning an array into smaller sub-arrays, and then recursively sorting those sub-arrays. The basic idea behind the algorithm is to choose a "pivot" element from the array and partition the other elements into two sub-arrays, one containing elements less than the pivot and one containing elements greater than the pivot. The pivot element is then placed in its final position in the sorted array.

Here is an example of a C implementation of the quick sort algorithm

void quick_sort(int arr[], int left, int right) {

    int i = left, j = right;

    int tmp;

    int pivot = arr[(left + right) / 2];

 

    /* partition */

    while (i <= j) {

        while (arr[i] < pivot)

              i++;

        while (arr[j] > pivot)

              j--;

        if (i <= j) {

            tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

            i++;

            j--;

        }

    }

    /* recursion */

    if (left < j)

        quick_sort(arr, left, j);

    if (i < right)

        quick_sort(arr, i, right);

}

The function takes in three parameters: an array to be sorted, a left index, and a right index. The pivot element is chosen as the middle element of the array. The partitioning step is done by using two pointers, i and j, that start at the left and right ends of the array, respectively. The pointers move towards each other, swapping elements that are on the wrong side of the pivot. Once the pointers meet, the partitioning is complete.

The recursion step is done by calling the quick_sort function again on the sub-arrays created by the partitioning step. The base case for the recursion is when the left index is greater than or equal to the right index, which means that the sub-array has only one element and is already sorted.

It's important to note that the pivot element can be chosen in many different ways, such as randomly, the first or last element of the array, or the median element. The choice of pivot will impact the performance of the algorithm.

In conclusion, quick sort is a powerful and efficient sorting algorithm that is easy to implement in C. Its average case time complexity is O(n log n), making it a good choice for sorting large arrays.