Question

The purpose here is to implement the QuickSort sorting algorithm to sort integers.

Write a C program which accepts 1 command-line argument: the name of a text file which contains integers, one-per line. Your C program must be named project3.

Your C program needs to implement the QuickSort algorithm to sort the integers read from the file specified on the command-line. Your QuickSort implementation must utilize the median-of-three algorithm for choosing a pivot, and BubbleSort any sub arrays with less than 10 elements. Your C program should also output the sorted list of integers, one per line. The last two lines of output should be the Number of Comparisons and the Number of Swaps (with appropriate labels)

Answer 1

//project3.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ELEMENTS 1024 //change it if required

int Partition(int *array, int l, int r);
int QuickSort(int *array, int l, int r);
int comparisons = 1;
int no_of_swap = 0;

void swap(int *array, int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
    no_of_swap++;
}

int Partition(int *array, int l, int r)
{
    int n = r - l;
    int middle = ((n - (n % 2)) / 2) + l;

    // order left and middle value
    if(array[l] > array[middle]) {
        swap(array, l, middle);
    }
    // order left and right values
    if(array[l] > array[r]) {
        swap(array, l, r);
    }
    // order middle and right values
    if(array[middle] > array[r]) {
        swap(array, middle, r);
    }
    swap(array, l, middle);
    int p = array[l];
    int i = l + 1;
    int end = 0;
    int j;
    for (j = l + 1; j <= r; j++)
    {
        if (array[j] < p){
            int k = array[j];
            array[j] = array[i];
            array[i] = k;
            i++;
        }
        end = j;
    }
    //swap A[l] and A[i-1]
    int a = array[l];
    array[l] = array[i-1];
    array[i-1] = a;
    QuickSort(array, l, i - 2);
    QuickSort(array, i, end);
}

int QuickSort(int *array, int l, int r)
{
    if (l < r)
    {
        Partition(array, l, r);
        comparisons = comparisons + (r - l);
    }
    else
    {
        return 0;
    }
}
void main(int argc, char *argv[] )
{

   char *file_name;
   int array[MAX_ELEMENTS];
   FILE *fp;
   int i=0;
   int j = 0;

   if(argc < 2){
      printf("invalid argument \n");
       return;
   }
       else{
       file_name = malloc(strlen(argv[1]));
       strcpy(file_name,argv[1]);
   }
  
   fp = fopen(file_name,"r");
   if(fp == NULL) {
            printf("Unable to open file!");
            return;
   }

   char chunk[128];  
   while(fgets(chunk, sizeof(chunk), fp) != NULL) {
       array[i] = atoi(chunk);
       i++;
      
   }
  
   QuickSort(array, 0, i - 1);

   for(j=0;j<i;j++){
       printf("%d\n",array[j]);
   }

   printf("comparisons = %d\nSwap = %d\n",comparisons,no_of_swap);
}