Question

Consider, the following elements:

12, 5, 34, 78, 11, 4
a) Apply Quick Sort and rearrange them in an ascending order. Write a program in C for this sorting technique.
b) What is the time complexity of quick sort for worst case?

Answer 1

The Quick Sort algorithm is implemented in a C program, which arranges a given set of numbers in ascending order. The worst-case time complexity of Quick Sort is O(n^2), which occurs when the chosen pivot is always the smallest or largest element.

Step-by-step explanation:

To arrange the numbers 12, 5, 34, 78, 11, 4 in ascending order using the Quick Sort algorithm, we implement the following C program:

#include

void quickSort(int *, int, int);
int partition(int *, int, int);

int main() {
int arr[] = {12, 5, 34, 78, 11, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n-1);
for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

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 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}

The time complexity of quick sort in the worst case is O(n^2), which happens when the pivot element is always the smallest or largest element in the subset of the array that is being sorted, causing one partition to have n-1 elements and the other to have 0 elements.