IGNOU BCSL-045-Algorithm Design Lab, Latest Solved Assignment (July 2023 - January 2024 )

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