This C program sorts a given array of integer numbers using Quick Sort technique.
It is comparison sort which works on divide and conquer technique. It is in-place partitioning algorithm and one of the fastest sorting techniques available till date. Average Time Complexity of this algorithm is O(nlog(n)). Increase the value of MAX to generate and array of large number of elements and then apply quick sort algorithm to sort it.
Here is the source code of the C program to sort integers using Quick Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C Program to Perform Quick Sort on Large Number of Elements
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void random_shuffle(int arr[])
{
srand(time(NULL));
int i, j, temp;
for (i = MAX - 1; i > 0; i--)
{
j = rand()%(i + 1);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partion(int arr[], int p, int r)
{
int pivot = arr[r];
int i = p - 1;
int j;
for (j = p; j < r; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[r]);
return i + 1;
}
void quick_sort(int arr[], int p, int q)
{
int j;
if (p < q)
{
j = partion(arr, p, q);
quick_sort(arr, p, j - 1);
quick_sort(arr, j + 1, q);
}
}
int main()
{
int i;
int arr[MAX];
for (i = 0;i < MAX;i++)
arr[i] = i + 99999;
random_shuffle(arr); //To randomize the array
quick_sort(arr, 0, MAX-1); //function to sort the elements of array
for (i = 0; i < MAX;i++)
printf("%d \n", arr[i]);
return 0;
}
$ gcc quicksort.c -o quicksort $ ./quicksort Sorted array is : 0 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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
If you find any mistake above, kindly email to [email protected]Related Posts:
- Check Computer Science Books
- Practice Computer Science MCQs
- Watch Advanced C Programming Videos
- Apply for C Internship
- Check C Books