Quick Sort Program in C

Problem Description

Write a C program to implement the Quick Sort algorithm.

Problem Solution

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

What is Quick Sort?

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.

Quick Sort Algorithm:

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

Method 1: QuickSort in C using Naive Approach

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.

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

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).

Runtime Test Cases

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

Method 2: (Recursion)

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)

Program/Source Code

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]);
```
```
    }
```
```
}
```

Program Explanation

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).

Runtime Test Cases

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

Method 3: (Recursion and Modular Approach)

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.

Program/Source Code

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);
```
```
}
```

Program Explanation

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).

Runtime Test Cases

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

Method 4: Quick Sort in C using Randomization

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

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

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]

« Prev - C Program to Find the Median of Two Sorted Arrays of Same Size

» Next - C Program to Implement Merge Sort Algorithm

Related Posts:

Recommended Articles: