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