In this tutorial, we will see another sorting technique which is Quick sort and Quick Sort Program in C.
Quick sort: Quick sort is the fastest internal sorting algorithm without any additional memory for sorting data.
In quick sort, first, we choose the key element in the list which is called Pivot element. Then we reorder the list with the rule that all elements which are less than pivot come before pivot element and so that all greater will come after pivot. After this partitioning, the pivot is in its final position.
Also Read: Introduction of Data Structure
Then, recursively reorder the list.
Quick sort time complexity: The time complexity of quick sort is the O (n log n). For average case and worst case the time complexity is O (n2).
| Time Complexity of Quick sort = O (n2 ) |
Quicksort Algorithm
- while data[low_big-index] <= data[pivot]
++low
- while data[low_small_index] <= data[pivot]
high—
- if low_big_index < low_small_index
data[low_big_index] & data[low_small_index]
- while(low_small_index > low_big_index)
goto step 1
- swap data[low_small_index] with pivot.
Quick sort example:
Quick sort program in c
| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 | #include<stdio.h>#include<conio.h>#define MAX_SIZE 5void quick_sort(int, int);int arr_sort[MAX_SIZE];int main() { int i; printf(” Quick Sort -\n”); printf(“\nEnter %d Elements for Sorting\n”, MAX_SIZE); for (i = 0; i < MAX_SIZE; i++) scanf(“%d”, &arr_sort[i]); printf(” Given array :”); for (i = 0; i < MAX_SIZE; i++) { printf(“\t%d”, arr_sort[i]); } quick_sort(0, MAX_SIZE – 1); printf(“\n\nSorted array :”); for (i = 0; i < MAX_SIZE; i++) { printf(“\t%d”, arr_sort[i]); } getch();}void quick_sort(int f, int l) { int i, j, t, p = 0; if (f < l) { p = f; i = f; j = l; while (i < j) { while (arr_sort[i] <= arr_sort[p] && i < l) i++; while (arr_sort[j] > arr_sort[p]) j–; if (i < j) { t = arr_sort[i]; arr_sort[i] = arr_sort[j]; arr_sort[j] = t; } } t = arr_sort[p]; arr_sort[p] = arr_sort[j]; arr_sort[j] = t; quick_sort(f, j – 1); quick_sort(j + 1, l); }} |
Output:
Comment below if you are facing any problem in this quick sort program in c.