Quick Sort in C: Introduction and Basic Implementation

1. What is Quick Sort?

Quick sort is a popular and efficient sorting algorithm that sorts an array of elements by dividing it into smaller subarrays and recursively sorting them. It is based on the idea of choosing a pivot element and partitioning the array around it, such that all the elements smaller than the pivot are on its left and all the elements larger than the pivot are on its right.

Quick sort is one of the most widely used sorting algorithms in practice, as it can handle large datasets with high performance and low memory usage. It is also a comparison-based algorithm, which means that it only compares the elements to each other, without relying on any external information or ordering.

In this blog, you will learn how quick sort works, how to implement it in C, and what are its advantages and disadvantages. You will also see some examples of quick sort in action and how it compares to other sorting algorithms.

2. How Quick Sort Works

Quick sort works by applying the divide and conquer strategy, which means that it breaks down a large problem into smaller and simpler subproblems, and then combines the solutions to get the final result. In quick sort, the subproblems are the subarrays that need to be sorted.

The main steps of quick sort are:

• Choosing a pivot: This is the element that will be used to partition the array. There are different ways to choose a pivot, such as picking the first, last, middle, or random element of the array. The choice of the pivot can affect the performance of quick sort, as we will see later.
• Partitioning the array: This is the process of rearranging the elements of the array such that all the elements smaller than the pivot are on its left, and all the elements larger than the pivot are on its right. The pivot itself is placed in its final position in the sorted array. This step can be done in different ways, such as using two pointers or a swap function.
• Recursively sorting the subarrays: This is the process of applying quick sort to the left and right subarrays that are created after partitioning the array. This step is repeated until the subarrays have one or zero elements, which means that they are already sorted.

Let’s see an example of how quick sort works on an array of numbers. Suppose we have the following array:

int arr[] = {10, 7, 8, 9, 1, 5};

We will use the last element as the pivot, which is 5 in this case. We will also use two pointers, i and j, to keep track of the smaller and larger elements. Initially, i is -1 and j is 0.

We will compare each element of the array with the pivot, and if it is smaller, we will increment i and swap arr[i] and arr[j]. If it is larger, we will just increment j. At the end of the loop, we will swap the pivot with arr[i+1], which is the first element larger than the pivot. This will place the pivot in its correct position in the sorted array.

Here is how the array looks like after each iteration of the loop:

After the loop, we swap the pivot (5) with arr[i+1] (8), which gives us the following array:

int arr[] = {1, 5, 8, 9, 10, 7};

Now, the pivot (5) is in its final position, and all the elements smaller than it are on its left, and all the elements larger than it are on its right. We have successfully partitioned the array.

Next, we recursively sort the left and right subarrays, which are {1} and {8, 9, 10,

2.1. Choosing a Pivot

The first step of quick sort is to choose a pivot element, which is the element that will be used to partition the array. The pivot can be any element of the array, but the choice of the pivot can affect the performance of quick sort.

Why is the choice of the pivot important? Because the pivot determines how evenly the array is split into subarrays. Ideally, we want the pivot to be the median of the array, which means that half of the elements are smaller than the pivot and half of the elements are larger than the pivot. This way, the subarrays have roughly the same size and quick sort can achieve its best case time complexity of O(n log n).

However, finding the median of an array is not easy, and it would take extra time and space. Therefore, quick sort uses some heuristics to choose a pivot, such as:

• First element: This is the simplest way to choose a pivot, but it can lead to poor performance if the array is already sorted or nearly sorted. In that case, the pivot would be the smallest or the largest element of the array, and the subarrays would have very different sizes. This would result in the worst case time complexity of O(n²).
• Last element: This is similar to choosing the first element, but it can avoid some problems if the array is sorted in reverse order. However, it still suffers from the same issue if the array is sorted or nearly sorted in ascending order.
• Middle element: This is a better way to choose a pivot, as it can avoid the worst case scenario for sorted or nearly sorted arrays. However, it still does not guarantee that the pivot is close to the median of the array, and it can lead to unbalanced subarrays if the array has many repeated elements.
• Random element: This is a way to choose a pivot randomly from the array, which can reduce the chances of getting a bad pivot. However, it still does not guarantee that the pivot is close to the median of the array, and it can introduce some randomness in the performance of quick sort.
• Median of three: This is a way to choose a pivot by taking the median of the first, middle, and last elements of the array. This can improve the performance of quick sort, as it can avoid the worst case scenario for sorted or nearly sorted arrays, and it can also reduce the chances of getting a bad pivot. However, it still does not guarantee that the pivot is the median of the array, and it can take some extra time to compute the median of three.

As you can see, there is no perfect way to choose a pivot for quick sort, and each method has its pros and cons. In this blog, we will use the last element as the pivot, but you can experiment with different methods and see how they affect the performance of quick sort.

2.2. Partitioning the Array

The second step of quick sort is to partition the array around the pivot element, such that all the elements smaller than the pivot are on its left, and all the elements larger than the pivot are on its right. This step is also called the quicksort partition or the Lomuto partition, after the name of the algorithm that implements it.

The Lomuto partition algorithm works as follows:

1. Choose the last element of the array as the pivot.
2. Initialize a variable i to -1, which will keep track of the last element smaller than the pivot.
3. Iterate over the array from 0 to n-2, where n is the size of the array.
4. For each element, compare it with the pivot. If it is smaller, increment i and swap the element with arr[i].
5. After the loop, swap the pivot with arr[i+1], which is the first element larger than the pivot.
6. Return the index of the pivot, which is i+1.

The Lomuto partition algorithm ensures that the pivot is placed in its correct position in the sorted array, and that all the elements smaller than the pivot are on its left, and all the elements larger than the pivot are on its right. The algorithm also returns the index of the pivot, which will be used to recursively sort the subarrays.

Here is the C code for the Lomuto partition algorithm:

// A function to partition an array using the Lomuto partition scheme
int partition(int arr[], int low, int high) {
    // Choose the last element as the pivot
    int pivot = arr[high];
    // Initialize i to -1
    int i = -1;
    // Iterate over the array from low to high-1
    for (int j = low; j < high; j++) {
        // Compare the element with the pivot
        if (arr[j] < pivot) {
            // Increment i and swap arr[i] and arr[j]
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Swap the pivot with arr[i+1]
    i++;
    int temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
    // Return the index of the pivot
    return i;
}

2.3. Recursively Sorting the Subarrays

The third and final step of quick sort is to recursively sort the subarrays that are created after partitioning the array. This step is based on the principle of recursion, which means that a function calls itself with smaller inputs until a base case is reached.

In quick sort, the base case is when the subarray has one or zero elements, which means that it is already sorted. In that case, the function returns without doing anything. Otherwise, the function performs the following steps:

1. Call the partition function on the subarray and get the index of the pivot.
2. Call the quick sort function on the left subarray, which is from the first element to the pivot-1.
3. Call the quick sort function on the right subarray, which is from the pivot+1 to the last element.

By doing this, the function sorts the subarrays around the pivot, and then sorts the subarrays of the subarrays, and so on, until the whole array is sorted.

Here is the C code for the quick sort function that uses recursion:

// A function to sort an array using quick sort
void quickSort(int arr[], int low, int high) {
    // Check if the subarray has more than one element
    if (low < high) {
        // Partition the subarray and get the index of the pivot
        int pivot = partition(arr, low, high);
        // Recursively sort the left subarray
        quickSort(arr, low, pivot - 1);
        // Recursively sort the right subarray
        quickSort(arr, pivot + 1, high);
    }
}

To sort the whole array, we need to call the quick sort function with the first and last indices of the array, which are 0 and n-1, where n is the size of the array.

For example, if we want to sort the following array:

int arr[] = {10, 7, 8, 9, 1, 5};

We need to call the quick sort function as follows:

quickSort(arr, 0, 5);

This will sort the array in ascending order, and the result will be:

int arr[] = {1, 5, 7, 8, 9, 10};

3. Quick Sort Algorithm in C

In this section, you will learn how to implement the quick sort algorithm in C. You will use the Lomuto partition scheme that you learned in the previous section, and you will write a recursive function that sorts an array of integers using quick sort.

The quick sort function takes three parameters: the array to be sorted, the low index, and the high index of the subarray. The function performs the following steps:

1. Check if the subarray has more than one element. If not, return without doing anything.
2. Call the partition function on the subarray and get the index of the pivot.
3. Recursively call the quick sort function on the left subarray, which is from the low index to the pivot-1.
4. Recursively call the quick sort function on the right subarray, which is from the pivot+1 to the high index.

Here is the code for the quick sort function in C:

// A function to sort an array using quick sort
void quickSort(int arr[], int low, int high) {
    // Check if the subarray has more than one element
    if (low < high) {
        // Partition the subarray and get the index of the pivot
        int pivot = partition(arr, low, high);
        // Recursively sort the left subarray
        quickSort(arr, low, pivot - 1);
        // Recursively sort the right subarray
        quickSort(arr, pivot + 1, high);
    }
}

To sort the whole array, you need to call the quick sort function with the low index as 0 and the high index as n-1, where n is the size of the array. For example, if you have the following array:

int arr[] = {10, 7, 8, 9, 1, 5};

You can sort it using quick sort as follows:

quickSort(arr, 0, 5);

This will sort the array in ascending order, and the result will be:

int arr[] = {1, 5, 7, 8, 9, 10};

Congratulations, you have successfully implemented the quick sort algorithm in C! You can test your code with different inputs and see how it works. You can also modify your code to sort other types of data, such as strings or structures.

4. Advantages and Disadvantages of Quick Sort

Quick sort is one of the most widely used sorting algorithms in practice, as it has many advantages over other sorting algorithms. However, it also has some disadvantages that you should be aware of. In this section, you will learn about the pros and cons of quick sort, and how it compares to other sorting algorithms.

Some of the advantages of quick sort are:

• Fast and efficient: Quick sort can sort large datasets with high performance and low memory usage. It has an average time complexity of O(n log n), which means that it can sort n elements in roughly n log n comparisons. This is faster than other comparison-based algorithms, such as bubble sort, selection sort, or insertion sort, which have a time complexity of O(n²). Quick sort also uses in-place sorting, which means that it does not require extra space to store the sorted elements, unlike merge sort, which uses O(n) extra space.
• Simple and elegant: Quick sort is based on a simple and elegant idea of dividing and conquering the array. It uses recursion to sort the subarrays, which makes the code easy to understand and implement. It also does not depend on any external information or ordering, as it only compares the elements to each other.
• Adaptable and versatile: Quick sort can sort any type of data, such as numbers, strings, or structures, as long as there is a way to compare them. It can also sort the data in any order, such as ascending, descending, or custom. It can also be modified to handle some special cases, such as duplicate elements, or to achieve some specific goals, such as finding the kth smallest element.

Some of the disadvantages of quick sort are:

• Unstable and unpredictable: Quick sort is an unstable sorting algorithm, which means that it does not preserve the relative order of equal elements. For example, if you have an array of students with their names and grades, and you sort them by their grades using quick sort, the students with the same grade may not appear in the same order as they were in the original array. This can be a problem if you need to maintain the original order of the elements. Quick sort is also unpredictable, as its performance depends on the choice of the pivot. If the pivot is chosen poorly, such as the smallest or the largest element, quick sort can degenerate to the worst case scenario, where it takes O(n²) time to sort the array. This can happen if the array is already sorted or nearly sorted, or if it has many repeated elements.
• Complex and fragile: Quick sort is based on recursion, which can make the code complex and fragile. Recursion can cause some issues, such as stack overflow, infinite loops, or memory leaks, if it is not handled properly. Recursion can also be difficult to debug and test, as it involves multiple function calls and variables. Moreover, quick sort requires some extra steps, such as choosing a pivot, partitioning the array, and swapping the elements, which can introduce some errors or bugs in the code.

As you can see, quick sort has both advantages and disadvantages, and it is not a perfect sorting algorithm. However, it is still a very powerful and useful algorithm, and it can be improved by using some techniques, such as choosing a better pivot, using a hybrid approach, or using a randomized version. In the next section, you will learn about some of these techniques and how they can enhance the performance of quick sort.

5. Conclusion

In this blog, you have learned about the quick sort algorithm and its implementation in C. You have seen how quick sort works by choosing a pivot element and partitioning the array around it, and then recursively sorting the subarrays. You have also learned about the advantages and disadvantages of quick sort, and how it compares to other sorting algorithms.

Quick sort is a fast and efficient sorting algorithm that can handle large datasets with low memory usage. It is based on a simple and elegant idea of divide and conquer, and it can sort any type of data in any order. However, quick sort is also unstable and unpredictable, as its performance depends on the choice of the pivot. It can also be complex and fragile, as it uses recursion and requires some extra steps.

Quick sort can be improved by using some techniques, such as choosing a better pivot, using a hybrid approach, or using a randomized version. These techniques can enhance the performance of quick sort and reduce the chances of getting a bad pivot. You can also modify quick sort to suit your specific needs, such as finding the kth smallest element or sorting an array of strings.

Quick sort is one of the most widely used sorting algorithms in practice, and it is a useful skill to have as a programmer. You can use quick sort to sort your data efficiently and effectively, and to solve various problems that involve sorting. You can also learn more about quick sort and other sorting algorithms by reading books, articles, or online tutorials.

We hope you enjoyed this blog and learned something new. If you have any questions or feedback, please leave a comment below. Thank you for reading!