In this tutorial you will learn about the C Program to Implement Quick Sort Algorithm and its application with practical example.
C Program to implement Quick-sort Algorithm
In this tutorial, we will learn to create a C program that will do Quick-sort using C programming.
Prerequisites.
Before starting this tutorial we assume that you are best aware of the following C programming topics:
- Operators in C Programming.
- Basic Input and Output function in C Programming.
- Basic C programming.
- For loop in C Programming.
- Creating and Using the user-defined function in C programming.
What is Quick Sort?
In every programming language, the sorting of data is a very important factor. Sorting works are done mainly with the techniques available in C Language. Many different techniques for sorting are available to work with but in this tutorial, we will focus on the Quick Sort Technique.
The Quicksort is a sorting algorithm based on dividing the array and arranging where an array is divided into sub-arrays and the number is taken from the array itself. Then We will sort that array using the quick sort method.
Program For Quick Sort:-
In this program, we will perform the 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 71 72 73 74 75 76 77 78 79 80 81 82 |
// C Program to Implement Quick Sort Algorithm #include <stdio.h> // function to swap elements void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } // function to find the partition position int partition(int array[], int low, int high) { // select the rightmost element as pivot int pivot = array[high]; // pointer for greater element int i = (low - 1); // traverse each element of the array // compare them with the pivot for (int j = low; j < high; j++) { if (array[j] <= pivot) { // if element smaller than pivot is found // swap it with the greater element pointed by i i++; // swap element at i with element at j swap(&array[i], &array[j]); } } // swap the pivot element with the greater element at i swap(&array[i + 1], &array[high]); // return the partition point return (i + 1); } void quickSort(int array[], int low, int high) { if (low < high) { // find the pivot element such that // elements smaller than pivot are on left of pivot // elements greater than pivot are on right of pivot int pi = partition(array, low, high); // recursive call on the left of pivot quickSort(array, low, pi - 1); // recursive call on the right of pivot quickSort(array, pi + 1, high); } } // function to print array elements void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // main function int main() { //Declaring the reuqired variables for the program int arry[] = {8, 7, 2, 1, 0, 9, 6}; int n = sizeof(arry) / sizeof(arry[0]); //PRinting the unsorted array printf("Unsorted Array\n"); printArray(arry, n); // perform quicksort on arry quickSort(arry, 0, n - 1); //Printing the sorted array printf("Sorted array in ascending order: \n"); printArray(arry, n); } |
Output:-
In the above program, we have first declared and initialized a set of variables required in the program.
- no = it will hold the size of an array.
- x[]= it will hold the elements in an array.
- i= it will hold the integer value to the control array.
- j= it will hold the integer value to the control array.
Printing the unsorted array.
Performing the quick sort on an unsorted array.
The printing sorted array
