Quick Sort In C

✅ Sorting arrays in programming languages such as C, Java, and Python.
✅ Sorting database records in database management systems.
✅ Sorting large datasets in scientific computing, such as in numerical simulations and data analysis.
✅ Sorting search results in web applications and e-commerce platforms.

In general, quick sort is a flexible and commonly utilized algorithm that finds application in numerous fields that demand sorting. Its efficient average-case time complexity and straightforward implementation render it an attractive option for sorting extensive datasets effectively.

Here is a C code of quick sort:

C Programming Language:

Example


#include <stdio.h>



// Function to swap two elements

void swap(int* a, int* b) {

	int t = *a;

	*a = *b;

	*b = t;

}

int partition(int arr[], int low, int high) {

	int pivot = arr[high];

	int i = (low - 1);



	for (int j = low; j <= high - 1; j++) {

		if (arr[j] < pivot) {

			i++;

			swap(&arr[i], &arr[j]);

		}

	}

	swap(&arr[i + 1], &arr[high]);

	return (i + 1);

}

void quickSort(int arr[], int low, int high) {

	if (low < high) {

		int pi = partition(arr, low, high);

		quickSort(arr, low, pi - 1);

		quickSort(arr, pi + 1, high);

	}

}



// Function to print the array

void printArray(int arr[], int size) {

	int i;

	for (i = 0; i < size; i++)

		printf("%d ", arr[i]);

	printf("\n");

}



int main() {

	int arr[] = { 12, 17, 6, 25, 1, 5 };

	int n = sizeof(arr) / sizeof(arr[0]);

	quickSort(arr, 0, n - 1);

	printf("Sorted array: \n");

	printArray(arr, n);

	return 0;

}

Output


Sorted array: 

1 5 6 12 17 25

✅ The quicksort function takes an array arr, and the indices of the first and last elements of the subarray to be sorted, low and high. If low is less than high, the function selects a pivot element using the partition function, and recursively applies the quicksort function to the two subarrays to the left and right of the pivot.
✅ The partition function takes the same arguments as quick_sort, and returns the index of the pivot element after partitioning the subarray. It begins by selecting the pivot as the last element of the subarray, and initializes an index i to the left of the subarray. It then iterates through the subarray, swapping any element less than the pivot with the element at arr[i] and incrementing i. The centre is then switched for the element at arr[i+1] before returning i+1.
✅ The swap method changes the values of two pointers to integers.
✅ To use this implementation of quick sort, you can simply call quick_sort(arr, 0, n-1), where arr is the array to be sorted and n is its length.
✅ Take note that the pivot in this implementation is the final member of the subarray. This is a simple and commonly used method, but it can lead to poor performance in certain cases, such as when the array is already sorted or nearly sorted. In these situations, efficiency can be enhanced by utilising more sophisticated pivot selection techniques. Additionally, this implementation uses recursion, which can be a source of performance overhead in certain cases. Iterative implementations of quick sort are also possible.

Characteristics:

✅ Quick sort divides an array into two sections according to a pivot element, usually the last element in the array.
✅ All elements smaller than the pivot are put in one partition, and all elements larger than the pivot are placed in the other, dividing the array into two partitions.
✅ The algorithm repeats this procedure for each division until the array as a whole is sorted.
✅ If the data is already ordered or the pivot element is not carefully chosen, quick sort has a worst-case time complexity of O(n2).

Advantages:

✅ Quick sort has a fast average-case time complexity of O(nlogn), making it efficient for large datasets.
✅ It is a simple and easy-to-implement algorithm that can be implemented in a few lines of code.
✅ Quick sort can be easily parallelized, making it suitable for use on multicore and distributed systems.
✅ It is an in-place sorting algorithm, which means that it does not require additional memory to store temporary variables or data structures.

Disadvantages:

✅ Quick sort has a worst-case time complexity of O(n^2) if the pivot element is chosen poorly or the data is already sorted.
✅ It is not a stable sorting algorithm, which means that it does not guarantee the relative order of equal elements in the sorted array.
✅ Quick sort is not suitable for sorting large datasets that do not fit in memory, as it requires multiple passes over the data.

Conclusion:

Quick sort stands out as a widely adopted and effective sorting technique that divides an array into two sections and executes the process on each segment repeatedly until the entire array is arranged in order. Its time complexity is O(nlogn) for average and best cases, and O(n^2) for the worst-case scenario. Despite the drawback of a higher time complexity in the worst case, quick sort is often preferred for its straightforwardness, efficiency, and straightforward implementation when compared to alternative sorting algorithms.

Q1. How can we use Quick Sort to handle duplicate elements effectively?

We have the option to implement a three-part partitioning approach within Quick Sort to effectively manage duplicate elements. This technique proves advantageous, especially in scenarios where the dataset features a high frequency of recurring values. It serves to mitigate the risk of generating highly imbalanced subarrays, ultimately safeguarding the sorting process from potential performance degradation.

However, the efficiency of the sorting process may diminish in cases with numerous duplicates since duplicate items are not explicitly factored in by this technique. This challenge is addressed by implementing the three-way partitioning strategy, which introduces a third section for elements that match the pivot value. To execute this, the boundaries of the segments containing values less than, equal to, and greater than the pivot are monitored using all three indices, which are adjusted as the array is divided into partitions.

This particular strategy offers numerous practical advantages. Initially, it enhances the efficiency of sorting in collections with a high occurrence of duplicate entries by reducing unnecessary comparisons and swaps. Furthermore, it ensures that the recursive sorting process operates on smaller, well-balanced subarrays, thereby enhancing the overall performance of the Quick Sort algorithm. To handle the recursive sorting of these subarrays, the Quick Sort function is updated to include a partitioning function that manages the three segments using distinct indices. This modification is specifically implemented in C programming. By incorporating this slight adjustment, the algorithm's ability to manage duplicate elements is significantly improved. The introduction of three-way segmentation guarantees the reliability and efficiency of the Quick Sort, especially when sorting arrays with a substantial number of duplicate elements.

Q2. What is Quick Sort's average time complexity?

O(n log n) is the answer.

Q3. What is Quick Sort's worst-case time complexity?

O(n^2).

Q4. How can we enhance Quick Sort's functionality?

Employing the three-way partitioning technique involves dividing the array into three distinct sections: elements less than the pivot, elements equal to or less than the pivot, and elements greater than the pivot. This approach is a beneficial enhancement that ensures proper handling of duplicate elements. As a result, it leads to better-balanced partitions and reduces the overall number of comparisons and exchanges required for sorting.

This minor adjustment enhances the algorithm's ability to manage duplicate elements effectively. By incorporating a three-way partitioning scheme, we can ensure the reliability and efficiency of Quick Sort, especially when processing arrays with abundant duplicate data.

Utilizing more advanced strategies, such as employing the median-of-three or random pivot selection, can be beneficial in preventing repetitive selection of the initial or final element as the pivot. This can be particularly advantageous when dealing with datasets that are partially sorted or already categorized, as continuously selecting these elements may lead to suboptimal performance.

By determining the median value among the first, middle, and last elements of the array as the pivot, the median-of-three technique facilitates the creation of more balanced partitions. This, in turn, reduces the risk of encountering the worst-case time complexity of O(n^2).

Integrating a random pivot selection not only helps in mitigating performance-hindering patterns but also serves as a simple yet effective method to enhance the overall efficiency of the algorithm.

Q5. What is the Quick Sort's fundamental function?

Dividing the array based on a Pivot component.

Q6. In Quick Sort, how is the pivot element selected?

The pivoLogic Practice can be chosen in various ways, such as being the initial, final, or randomly selected item.

Q7. What are Quick Sort's fundamental steps?

Choose a pivot element; partition the entire array into smaller sub-arrays by sorting them around the chosen pivot in an iterative manner.