C Program For Quick Sort Algorithm in Data Structure
Learn How To Sort an Integer Array using Quick Sort Algorithm in C Programming Language. Quick sort technique is the fastest sorting method. Find Explanation and Output of the Quick Sort Algorithm at the bottom.
What is Quick Sort?
The Quick Sort technique is based on Divide and Conquer Technique. Its also known as Partition Exchange Algorithm. It was designed by C.A.R. Hoare in 1962. In this algorithm, a problem is divided into small problems which are again divided into smaller problems and it continues.
Quick Sort Technique is one of the fastest sorting algorithms available. The Quick Sort Algorithm works on Divide and Conquer Algorithm where a given problem is divided into smaller subdivisions. It is similar to binary search algorithm.
An element (called as pivot element) is chosen from the array and placed at its proper position in the array by considering the following points:
- The elements on the left hand side of the pivot element are smaller than or equal to the pivot element.
- The elements on the right hand side of the pivot element are greater than or equal to the pivot element.
After this process, two sub lists are created and again the same process is continued through recursion method.
Quick Sort Algorithm Analysis
Quick Sort is Not a Stable Sort. Since it requires only one Temporary variable, it is an In-Place Sort. Space Complexity is O(n log n).
Average Case Performance: O(n log n)
Worst Case Performance: O(n2)
Best Case Performance: O(n log2n)
C Program To Sort Arrays using Quick Sort Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<stdio.h> void quick_sort(int elements[], int min, int max); int sublist_builder(int elements[], int min, int max); int main() { int elements[30], limit, count; printf("Enter Limit for Array:\t"); scanf("%d", &limit); printf("\nEnter %d Elements in the Array\n", limit); for(count = 0; count < limit; count++) { scanf("%d", &elements[count]); } quick_sort(elements, 0, limit - 1); printf("\nSorted List:\n"); for(count = 0; count < limit; count++) { printf("%d\t", elements[count]); } printf("\n"); return 0; } void quick_sort(int elements[], int min, int max) { int pivot_index; if(min >= max) { return; } pivot_index = sublist_builder(elements, min, max); quick_sort(elements, min, pivot_index - 1); quick_sort(elements, pivot_index + 1, max); } int sublist_builder(int elements[], int min, int max) { int temp, x, y, pivot_element; x = min + 1; y = max; pivot_element = elements[min]; while(x <= y) { while((elements[x] < pivot_element) && (x < max)) { x++; } while(elements[y] > pivot_element) { y--; } if(x < y) { temp = elements[x]; elements[x] = elements[y]; elements[y] = temp; x++; y--; } else { x++; } } elements[min] = elements[y]; elements[y] = pivot_element; return y; } |
Output
If you have any compilation errors or doubts in this Code To Sort Array using Quick Sort C Program in Data Structures, let us know about in the Comment Section below.
This algorithm of quick sort in c is faster than bubble sort, selection sort and insertion sort algorithms.
Nice program. Thanks. I could understand this code of quick sort in c so easily. It has been really simplified by you.
Quick sorting method is again uses too many recursive calls which makes it too complex to understand.