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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Next Steps:
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Computer Science Internship
- Buy Computer Science Books
- Apply for C Internship
- Buy C Books
- Watch Advanced C Programming Videos