Write a C program to implement the Quick Sort algorithm.

To approach this problem, we will use the divide and conquer algorithm.

**Quick sort** is a divide and conquer algorithm. It works by recursively partitioning the array into two parts, the left side of the array containing elements less than the pivot element, and the right side of the array containing elements greater than the pivot element.

1. Pick an element, called a pivot, from the array.

2. Partition the array into two halves, the left side of the array containing elements less than the pivot element, and the right side of the array containing elements greater than the pivot element.

3. Recursively sort the left side of the array and the right side of the array.

4. Return the array.

There are several ways to write an Quick Sort program in C language. Let’s discuss all the ways in detail.

- Quick Sort Program in C using Naive Approach
- Quick Sort Program in C using Recursion
- Quick Sort Program in C using Recursion and Modular Approach
- Quick Sort in C using Randomization

In this approach we will not use recursion. We will instead use a while loop to iterate through the array. We will pick a pivot element, and partition the array into two halves. We will then iterate through the array again, and pick a new pivot element, and partition the array into two halves. We will continue this process until we have only one element left in the array.

**Methods used:**

**int quickSort(int arr[], int low, int high):** This function will take in an array, and the low and high indices of the array.

Here is source code of the C Program to sort an array of integers using QuickSort Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

`/*`

`* C Program to sort an array of integers using Quick Sort without recursion`

`*/`

`#include <stdio.h>`

`#include <stdlib.h>`

int quickSort(int *arr, int low, int high)

`{`

int i = low, j = high;

int pivot = arr[(low + high) / 2];

while (i <= j)

`{`

while (arr[i] < pivot)

`i++;`

while (arr[j] > pivot)

`j--;`

if (i <= j)

`{`

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

`i++;`

`j--;`

`}`

`}`

if (low < j)

quickSort(arr, low, j);

if (i < high)

quickSort(arr, i, high);

return 0;

`}`

int main(void)

`{`

puts("Enter the number of elements in the array: ");

int n;

scanf("%d", &n);

int arr[n];

puts("Enter the elements of the array: ");

for (int i = 0; i < n; i++)

`{`

printf("arr[%d]: ", i);

scanf("%d", &arr[i]);

`}`

int low = 0;

int high = n - 1;

int pivot = arr[high];

int k = low - 1;

for (int j = low; j < high; j++)

`{`

if (arr[j] <= pivot)

`{`

`k++;`

int temp = arr[k];

arr[k] = arr[j];

arr[j] = temp;

`}`

`}`

int temp = arr[k + 1];

arr[k + 1] = arr[high];

arr[high] = temp;

int pi = k + 1;

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

puts("The sorted array is: ");

for (int i = 0; i < n; i++)

`{`

printf("%d ", arr[i]);

`}`

return 0;

`}`

1. The program starts with asking the user for entering the size for the array and subsequently entering the array elements.

2. Then we will pick a pivot element, and partition the array into two halves.

3. We will then iterate through the array again, and pick a new pivot element, and partition the array into two halves.

4. We will continue this process until we have only one element left in the array.

5. The final array will then be returned and printed.

**Example:**

- Suppose we have the following array: {4, 7, 2, 9, 11, 3, 1, 6}
- Assign
**low**as**0**and**high**as**n – 1**. We set the pivot element to the element with the index high. - Here,
**high**is 7 and**pivot**is 6. We set**k**as**low – 1**which is -1 here. While entering the loop,**k**becomes 1 and for all elements with indices equal to low and less than high are compared and if they are less than or equal to the pivot element, we swap them. - We set temp as the element at index
**k + 1**and swap it with the element at index high. We then set**pi**as**k + 1**. - We continue this process until we have only one element left in the array. We finally sent the array, lower index and upper index to the
**quickSort**function. - In the
**quickSort**function, we assign**i**as low and**j**as high. We set the element at the middle index as the**pivot**. - Increment the
**i**by the number of elements which are less than the pivot element. We then decrement**j**by the number of elements which are greater than the**pivot**element. - Swap the element at index
**i**with the element at index**j**. If**i**is less than equal to**j**which means we are checking here for the condition when all the elements have been sorted then it should not work. - Next, set the pivot element as the element at index
**j**. We then continue this process until we have only one element left in the array and this loop continues until**i**is not greater than**j**. - Call the same function recursively on the left side of the array and the right side of the array.
- Finally, print the array.

**Time Complexity: O(N log N)**

The time complexity of the quick sort algorithm is O(N log N).

**Space Complexity: O(n)**

The space complexity for quick sort is O(n).

Here’s the run time test cases for Quick Sort algorithm for 2 different input cases.

**Test Case 1:** Here, the elements are entered in random order.

Enter the number of elements in the array: 8 Enter the elements of the array: arr[0]: 4 arr[1]: 7 arr[2]: 2 arr[3]: 9 arr[4]: 11 arr[5]: 3 arr[6]: 1 arr[7]: 6 The sorted array is: 1 2 3 4 6 7 9 11

**Test Case 2:** Here, the elements are reverse sorted.

Enter the number of elements in the array: 5 Enter the elements of the array: arr[0]: 7 arr[1]: 3 arr[2]: 2 arr[3]: 1 arr[4]: -6 The sorted array is: -6 1 2 3 7

In this approach we will use recursion. We will pick a pivot element, and partition the array into two halves. We will then recursively sort the left side of the array and the right side of the array. We will then return the array.

**Methods used:**

The methods used are:

- void quickSort(int arr[], int low, int high)
- int partition(int arr[], int low, int high)

Here is source code of the C program to perform quick sort on a user provided array using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

`/*`

`* C program to perform quick sort on a user provided array using recursion`

`*/`

`#include <stdio.h>`

int partition(int ar[], int low, int high)

`{`

int pivot = ar[high];

int i = low - 1;

for (int j = low; j < high; j++)

`{`

if (ar[j] <= pivot)

`{`

`i++;`

int temp = ar[i];

ar[i] = ar[j];

ar[j] = temp;

`}`

`}`

int temp = ar[i + 1];

ar[i + 1] = ar[high];

ar[high] = temp;

return i + 1;

`}`

void quickSort(int arr[], int low, int high)

`{`

if (low < high)

`{`

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

`}`

`}`

int main(void)

`{`

puts("Enter the number of elements in the array: ");

int n;

scanf("%d", &n);

int arr[n];

puts("Enter the elements of the array: ");

for (int i = 0; i < n; i++)

`{`

printf("%d: ", i);

scanf("%d", &arr[i]);

`}`

quickSort(arr, 0, n - 1);

puts("The sorted array is: ");

for (int i = 0; i < n; i++)

`{`

printf("%d ", arr[i]);

`}`

`}`

1. The program starts with asking the user to enter the size of the array.

2. Then we will enter the elements of the array.

3. Call the **quickSort** function on the array.

4. Check if **low** is less than **high**, if it is then we will pick a **pivot** element, and partition the array into two halves.

5. We will then recursively sort the left side of the array and the right side of the array.

6. Print the array.

**Example:**

- For example, suppose we have the following array: {12, 76, 33, 65, 5, 88} Control goes into
**quickSort(arr, 0, 5)**. - Low is less than high, thus
**partition(arr, 0, 5)**is invoked.**pivot**is the last element ie. 4. We set**i**as**low – 1**which is -1 here. - While entering the loop,
**k**becomes 1 and for all elements with indices equal to**low**and less than**high**are compared and if they are less than or equal to the**pivot**element, we swap them. - We set
**temp**as the element at index**i + 1**and swap it with the element at index high. We then return and set**pi**as**i + 1**. - We continue this process until we have only one element left in the array. We then print the result.

**Time Complexity: O(N log N)**

The time complexity of the quick sort algorithm is O(N log N).

**Space Complexity: O(n)**

The space complexity for quick sort is O(n).

In this case, the elements are entered in a random order. The elements entered to sort the array using quick sort are “12, 76, 33, 65, 5, 88”.

Enter the number of elements in the array: 6 Enter the elements of the array: arr[0]: 12 arr[1]: 76 arr[2]: 33 arr[3]: 65 arr[4]: 5 arr[5]: 88 The sorted array is: 5 12 33 65 76 88

In this approach, in addition to having recursion in order to keep our code as small as possible, we’ll also be taking care not to reuse things and taking care for memory safety whenever possible. For this, we make sure that we don’t use the same array twice, and that we don’t use the same pointer twice. We’ll also use malloc to allocate memory for the array and swap function to swap two elements.

**Methods used:**

The methods used are:

- `
**malloc**` to allocate memory for the array — inbuilt function. - `
**swap**` to swap two elements. — without using auxillary variable. - `
**partition**` to partition the array. - `
**quickSort**` to sort the array.

Here is source code of the C program to perform quick sort on a user provided array using recursion and malloc. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

`/*`

`* C program to perform quick sort on a user provided array using recursion and malloc`

`*/`

`#include <stdio.h>`

`#include <stdlib.h>`

int n;

void printarray(int ar[], const char *name, unsigned int size)

`{`

printf("%s[] = [", name);

for (unsigned int i = 0; i < size; i++)

printf(" %d", ar[i]);

puts(" ]\n");

`}`

void swap(int *a, int *b)

`{`

if(*a == *b) return;

*a = *a + *b;

*b = *a - *b;

*a = *a - *b;

`}`

int partition(int *ar, int low, int high)

`{`

int pivot = ar[high];

int i = low - 1;

for (int j = low; j < high; j++)

`{`

if (ar[j] <= pivot)

`{`

`i++;`

swap(&ar[i], &ar[j]);

`}`

`}`

swap(&ar[i + 1], &ar[high]);

return i + 1;

`}`

void quickSort(int *arr, int low, int high)

`{`

if (low < high)

`{`

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

printarray(arr, "arr", (unsigned) n);

quickSort(arr, pi + 1, high);

printarray(arr, "arr", (unsigned) n);

`}`

`}`

int main(void)

`{`

puts("Enter the number of elements in the array: ");

scanf("%d", &n);

int *arr = malloc((size_t) n * sizeof(n));

puts("Enter the elements of the array: ");

for (int i = 0; i < n; i++)

`{`

printf("%d: ", i);

scanf("%d", &arr[i]);

`}`

quickSort(arr, 0, n - 1);

`}`

1. The program starts with asking the user to enter the size of the array and then assigns it space with **malloc**.

2. Then the user enters the elements of the array.

3. Call the **quickSort** function on the array. We check if low is less than high, if it is then we will pick a **pivot** element, and partition the array into two halves.

4. We will then recursively sort the left side of the array and the right side of the array.

5. Print the array.

**Example:**

- Suppose we have the following array: {4, 6, 3, 5, 1, 2, 7, 8} defined through
**malloc**. - Call the
**quickSort**function on the array. Control goes into**quickSort(arr, 0, 7)**. Low is less than high, thus**partition(arr, 0, 7)**is invoked.**pivot**is the last element ie. 8. - We set
**i**as**low – 1**which is -1 here. While entering the loop,**k**becomes 1 and for all elements with indices equal to low and less than high are compared and if they are less than or equal to the pivot element, we swap them using the swap function. - We set temp as the element at index
**i + 1**and swap it with the element at index high. We then return and set**pi**as**i + 1**. - We continue this process until we have only one element left in the array. We then print the result.

**Time Complexity: O(N log N)**

The time complexity of the quick sort algorithm is O(N log N).

**Space Complexity: O(n)**

The space complexity for quick sort is O(n).

In this case, the elements are entered in a random order. The elements entered to sort the array using quick sort are “4, 6, 3, 5, 1, 2, 7, 8”.

Enter the number of elements in the array: 8 Enter the elements of the array: arr[0]: 4 arr[1]: 6 arr[2]: 3 arr[3]: 5 arr[4]: 1 arr[5]: 2 arr[6]: 7 arr[7]: 8 The sorted array is: 1 2 3 4 5 6 7 8

In this approach, it sorts a given array of integer numbers using randomized Quick sort technique.

Here is source code of the C program to perform quick sort using randomization. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

`/*`

`* C Program to Implement Quick Sort Using Randomization`

`*/`

`#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 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 \n", arr[i]);

return 0;

`}`

1. This code implements the Quick Sort algorithm to sort an array of integers.

2. The code first randomly shuffles the array using the **random_shuffle** function.

3. Then, it calls the **quick_sort** function to recursively sort the array.

4. The **quick_sort** function partitions the array around a pivot element and then recursively sorts the two subarrays.

5. Finally, the code prints the sorted array.

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

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Computer Science Books
- Check C Books
- Practice Computer Science MCQs
- Practice BCA MCQs
- Apply for C Internship