C program to Sort Integers using Quick Sort Technique

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