C Program to Implement Quick Sort with Given Complexity Constraint

This is a C Program to implement Quick sort. This program sorts numbers using randomized quick sort.

Here is source code of the C Program to Implement Quick Sort with Given Complexity Constraint. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
#define MAX 10
```
```
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 pivotIndex = p + rand() % (r - p + 1); //generates a random number as a pivot

```
    int pivot;
```
```
    int i = p - 1;
```
```
    int j;
```
```
    pivot = arr[pivotIndex];
```
```
    swap(&arr[pivotIndex], &arr[r]);
```
```
    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;
```

    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 ", arr[i]);
```
```
    return 0;
```
```
}
```

Output:

$ gcc QuickSortComplexityConstraint.c
$ ./a.out
 
0 1 2 3 4 5 6 7 8 9

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself

» Next - C Program to Generate All Possible Subsets using Lexicographic Order

Related Posts:

Recommended Articles: