IGNOU BCSL-045-Algorithm Design Lab, Latest Solved Assignment (July 2023 - January 2024 )
Q2. Implement Quick Sort algorithm to sort the following array: 5 70 44 39 25 25 7 12 27 6 and calculate number of comparisons and exchange operations in the program.
Sol)
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high, int *comparisons, int *exchanges) {
int pivot = arr[high];
int i = (low – 1);
for (int j = low; j <= high – 1; j++) {
(*comparisons)++;
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
(*exchanges)++;
}
}
swap(&arr[i + 1], &arr[high]);
(*exchanges)++;
return i + 1;
}
void quickSort(int arr[], int low, int high, int *comparisons, int *exchanges)
{
if (low < high) {
int pi = partition(arr, low, high, comparisons, exchanges);
quickSort(arr, low, pi – 1, comparisons, exchanges);
quickSort(arr, pi + 1, high, comparisons, exchanges);
}
}
int main() {
int arr[] = {5, 70, 44, 39, 25, 25, 7, 12, 27, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int comparisons = 0;
int exchanges = 0;
printf(“Original array: “);
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
printf(“\n\n”);
quickSort(arr, 0, n – 1, &comparisons, &exchanges);
printf(“Sorted array: “);
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
printf(“\n”);
printf(“\nNumber of comparisons: %d\n”, comparisons);
printf(“Number of exchanges: %d\n”, exchanges);
return 0;
}
Output:
Original array: 5 70 44 39 25 25 7 12 27 6
Sorted array: 5 6 7 12 25 25 27 39 44 70
Number of comparisons: 24
Number of exchanges: 12