Implement quicksort algorithm using C programming language

Implement quicksort algorithm using C programming language

Code:

#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Partitioning function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the pivot as the last element
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Quicksort function
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

// Recursive calls on the two sub-arrays
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

// Utility function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {12, 5, 7, 23, 9, 14, 2, 15};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");
printArray(arr, size);

quicksort(arr, 0, size - 1);

printf("Sorted array: ");
printArray(arr, size);

return 0;
}

 

This implementation defines the swap, partition, and quicksort functions, and then demonstrates their usage in the main function. The quicksort function sorts an array in-place using the Quicksort algorithm. The partition function selects the pivot element and rearranges the elements around the pivot. The swap function is a simple utility function to swap two elements.

Remember to compile and run the code in a C compiler to see the results.

Explanation:

#include <stdio.h>

This line includes the standard input-output header file, which is required for functions like printf and scanf.

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

This is a function called swap that takes two pointers to integers (int* a and int* b) as parameters and swaps the values they point to.

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

This function is the heart of the Quicksort algorithm. It takes an array arr, and two indices low and high as parameters, indicating the portion of the array to partition. It selects the pivot element (in this case, the last element), rearranges the elements such that elements less than the pivot are on the left side, and elements greater than or equal to the pivot are on the right side. The index i keeps track of the position where smaller elements will be placed.

void quicksort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

This function is the main Quicksort algorithm implementation. It takes an array arr, and two indices low and high to indicate the range to be sorted. It first checks if low is less than high, meaning there's more than one element in the range. If so, it calculates the pivot index using the partition function, then recursively applies the quicksort function on the left and right sub-arrays.

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

This function takes an array arr and its size as parameters and prints the elements of the array.

int main() {
int arr[] = {12, 5, 7, 23, 9, 14, 2, 15};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");
printArray(arr, size);

quicksort(arr, 0, size - 1);

printf("Sorted array: ");
printArray(arr, size);

return 0;
}

The main function is where the program starts execution. It initializes an array called arr with some values and calculates its size. It then prints the original array, sorts it using the quicksort function, and prints the sorted array. Finally, it returns 0 to indicate successful execution.

When you run the program, it will demonstrate the Quicksort algorithm by sorting the provided array.

 

Time Complexity:

In the best and average cases, where the pivot choices are balanced and the partitioning consistently divides the array into roughly equal halves, the time complexity is O(n log n), where 'n' is the number of elements in the array.

In the worst case, where the pivot selection and partitioning consistently result in highly imbalanced sub-arrays, the time complexity is O(n^2). This worst-case scenario occurs when the pivot selection strategy consistently chooses the smallest or largest element as the pivot.

However, since the provided program always chooses the last element as the pivot, it is susceptible to worst-case behavior for certain input distributions. If the input array is already sorted or nearly sorted, choosing the last element as the pivot in each step can lead to a worst-case time complexity of O(n^2).

In practice, using randomized pivot selection, median-of-three pivot selection, or other techniques to choose a good pivot can help mitigate the risk of worst-case behavior and lead to an average time complexity of O(n log n) even for real-world input distributions.

In summary:

• Best-case time complexity: O(n log n)

• Average-case time complexity: O(n log n)

• Worst-case time complexity: O(n^2)

 

Space Complexity:

The space complexity of the above Quicksort program is determined by the memory used by the recursive function calls and the auxiliary variables used in each call. Let's break down the main contributors to the space complexity:

1. Recursive Call Stack: The primary space usage comes from the call stack during the recursive calls. In each recursive call to the quicksort function, two more recursive calls are made. The maximum depth of the call stack is determined by the number of recursive calls made until the base case is reached (i.e., until the sub-arrays have only one element or are empty).

2. Auxiliary Variables: The additional space used by local variables within each function call also contributes to the space complexity. This includes variables like pivot, i, j, and the temporary variable temp used in the swap function.

Given these considerations, the space complexity of the provided Quicksort program is O(log n) on average, and in the worst case, it can go up to O(n) due to the maximum depth of the recursive call stack. The best-case space complexity is O(log n) as well, considering a balanced partitioning.

It's important to note that the space complexity mentioned here is related to the extra memory used by the program for function call overhead and local variables. The input array itself doesn't contribute significantly to the space complexity.