Quicksort in C

20 Jul 2022 coding c

Quicksort

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.

Algorithm

Pick an element, called a pivot, from the array.
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.
Recursively sort the left side of the array and the right side of the array.
Return the array.

Problem description

Given an array of integers, sort the array using an implementation of the quick sort algorithm in C.

Problem Solution

To approach this problem, we will use the divide and conquer algorithm. We will start by picking a pivot element, and partitioning 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.

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. It will then pick a pivot element, and partition the array into two halves. It will then iterate through the array again, and pick a new pivot element, and partition the array into two halves. It will continue this process until we have only one element left in the array.

Approach

Pick a pivot element, and partition the array into two halves.
Iterate through the array, and pick a new pivot element, and partition the array into two halves.
Continue this process until we have only one element left in the array.
Return the array.

Examples

Suppose we have the following array: {4, 7, 2, 9, 11, 3, 1, 6} We 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. We then increment 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. We then 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. We then 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. We call the same function recursively on the left side of the array and the right side of the array. Finally, we return the array.

Program/Source code

/* 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("%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;
}

Explanation

The program starts with asking the user for entering the size for the array and subsequently entering the array elements. Then 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. We will then return the array.

Output

> ./quick0
Enter the number of elements in the array: 
8
Enter the elements of the array: 
0: 4   
1: 7 
2: 2 
3: 9
4: 11 
5: 3
6: 1
7: 6
The sorted array is: 
1 2 3 4 6 7 9 11

Recursive Approach

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

Approach

1. Pick a pivot element, and partition the array into two halves.
2. Recursively sort the left side of the array and the right side of the array.
3. Return the array.

Examples

For example, suppose we have the following array: {5, 2, 9, 1, 3, 7, 8, 6} 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. 6. 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.

Program/Source code

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

Explanation

The program starts with asking the user to enter the size of the array. Then we will enter the elements of the array. We will then 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. We will then recursively sort the left side of the array and the right side of the array. We will then return the array.

Output

> ./quicksort-recur
Enter the number of elements in the array: 
6
Enter the elements of the array: 
0: 12
1: 76
2: 33
3: 65
4: 5
5: 88
The sorted array is: 
5 12 33 65 76 88

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.

Approach

Pick a pivot element, and partition the array into two halves.
Recursively sort the left side of the array and the right side of the array.
At the places of swap, use the defined swap function to swap the elements.
Return the array.

Examples

Suppose we have the following array: {4, 6, 3, 5, 1, 2, 7, 8} defined through malloc. We will 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.

Program/Source code

// C program to perform QuickSort on a user provided array using recursion.

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

Explanation

The program starts with asking the user to enter the size of the array and then assigns it space with malloc. Then the user enters the elements of the array. We then 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. We will then recursively sort the left side of the array and the right side of the array. We will then return the array.

Output

> ./quicksort-func    
Enter the number of elements in the array: 
7
Enter the elements of the array: 
0: 9
1: 69
2: 12
3: 34
4: 22
5: 1
6: 7
arr[] = [ 1 7 12 34 22 9 69 ]

arr[] = [ 1 7 9 34 22 12 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

arr[] = [ 1 7 9 12 22 34 69 ]

Quicksort in C

Quicksort

Algorithm

Problem description

Problem Solution

Naive Approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Recursive Approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Recursion and modular approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Time and space complexity analysis for QuickSort algorithm

Time complexity

Space Complexity

Quicksort in C

Quicksort #

Algorithm #

Problem description #

Problem Solution #

Naive Approach #

Methods used #

Approach #

Examples #

Program/Source code #

Explanation #

Output #

Recursive Approach #

Methods used #

Approach #

Examples #

Program/Source code #

Explanation #

Output #

Recursion and modular approach #

Methods used #

Approach #

Examples #

Program/Source code #

Explanation #

Output #

Time and space complexity analysis for QuickSort algorithm #

Time complexity #

Space Complexity #

Quicksort

Algorithm

Problem description

Problem Solution

Naive Approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Recursive Approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Recursion and modular approach

Methods used

Approach

Examples

Program/Source code

Explanation

Output

Time and space complexity analysis for QuickSort algorithm

Time complexity

Space Complexity