In this source code example, we will write a code to implement the Quick Sort algorithm in the C programming language.
Quick sort is an algorithm for sorting the elements of a collection in an organized way. Parallelized quick sort is two to three times faster than merge sort and heap sort. The algorithm's performance is of the order O(n log n). This algorithm is a space-optimized version of the binary tree sort algorithm.
Quick Sort in C programming
In this C program, we will take input from the User or console. Let's write a C program to sort N numbers in ascending order using the Quick Sort algorithm:
#include<stdio.h>
void Quicksort(int[], int, int);
int partition(int[], int, int);
void main() {
int x[20], i, n;
printf("\n Enter the no of element to be sorted:");
scanf("%d", &n);
printf("\n Enter %d elements:", n);
for (i = 0; i < n; i++)
scanf("%d", &x[i]);
Quicksort(x, 0, n - 1);
printf("\n The sorted array is:\n");
for (i = 0; i < n; i++)
printf("%4d", x[i]);
}
void Quicksort(int a[], int p, int r) {
int q;
if (p < r) {
q = partition(a, p, r);
Quicksort(a, p, q);
Quicksort(a, q + 1, r);
}
}
int partition(int a[], int p, int r) {
int k, i, j, temp;
k = a[p];
i = p - 1;
j = r + 1;
while (1) {
do {
j = j - 1;
} while (a[j] > k);
do {
i = i + 1;
} while (a[i] < k);
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
} else
return (j);
}
}
Output:
Enter the no of element to be sorted:
5
Enter 5 elements:
40
10
20
30
50
The sorted array is:
10 20 30 40 50
Comments
Post a Comment