Please help with this problem With proper explanations and O

Solution

Hello Please find Below Programme

1)Initializes a Array with 1..Size with unique Random values

2)Alter Size and Number of Iterations manually in code

3) Each sort function write \"Execution Time in nano seconds\" \"Number Of steps\" into test file (int Same Execution folder)

#include <iostream>
#include <time.h>
#include <iostream>
#include <fstream>
using namespace std;
ofstream myfile;
/**
* @brief Funtion for bubble_sort
* @param a -->Array
* @param n -->Size of Array
* @param file --> File pointer to write
*                 Number of Steps   Execution Time
*/
void bubble_sort(int a[],int n ){
    //Variable for Number of Turns
    int numTurns =0 ;
    int temp;
    //Took start Time
    clock_t tStart = clock();
    for(int i=0;i<n;i++) {
        for(int j=0;j<n-i-1;j++){
            //Increment Number of Turns
            numTurns++;
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1]; /*Swap have been done here*/
                a[j+1]=temp;
             }
          }
      }
    clock_t tEnd = clock();
    double executionTime = (double)((clock() - tStart)/CLOCKS_PER_SEC/1000000);

    myfile<<numTurns<<\" \"<<executionTime<<\"\ \";
}
/**
* @brief insertion_sort
* @param a
* @param n
* @param file
*/
void insertion_sort(int a[],int n)
{
    //Variable for Number of Turns
    int numTurns =0 ;
    //Took start Time
    clock_t tStart = clock();
    int key;
    for(int i=1;i<n;i++){
        key=a[i];
        int j=i-1;
        while(j>=0&&a[j]>key){ a[j+1]=a[j];
            //Increase Number of Turns
            numTurns++;
            j=j-1;
        }
        a[j+1]=key;
    }
    double executionTime = (double)((clock() - tStart)/CLOCKS_PER_SEC/1000);

    myfile<<numTurns<<\" \"<<executionTime<<\"\ \";
}
/**
* @brief initializeArray
* @param a ---> Array to Initialize
* @param size ---> Size of Array
*/

void initializeArray(int a[],int size){

    for (int i=0;i<size;i++)
    {
        int num;
        bool unique = true;
            do
            {
                unique = true;
                //Generate a Random Value between 1..Size, Check until a Unique Number found
                num=rand() % size;
                //Check it is Duplicate
                for (int i2=0;i2<i;i2++)
                {
                    if (a[i2]==num)
                    {
                      unique=false;
                      break;
                    }

                }
            } while (!unique);
            //Add to Array if not Difficult
            a[i]=num;
        }

}
/**
* @brief min_elm , for Selection Sort
* @param a
* @param low
* @param up
* @return
*/

int min_elm(int a[],int low,int up,int *turn)
{
    int min=low;
    while(low<up)
    {
        //Increment Number of Turns
        (*turn)++;
        if(a[low]<a[min])
            min=low;
        low++;
    }
    return min;
}
/**
* @brief selection_sort
* @param a
* @param n
*/
void selection_sort(int a[],int n)
{
    //Variable for Number of Turns
    int numTurns =0 ;
    //Took start Time
    clock_t tStart = clock();
    int i=0;
    int loc=0;
    int temp;
    for(i=0;i<n;i++)
    {
        //Increment Number of Turns
        numTurns++;
        loc=min_elm(a,i,n,&numTurns);
        temp=a[loc];
        a[loc]=a[i];
        a[i]=temp;
    }
    double executionTime = (double)((clock() - tStart)/CLOCKS_PER_SEC/1000);

    myfile<<numTurns<<\" \"<<executionTime<<\"\ \";
}
int partition(int a[],int p,int r,int *numTurns)
{
    int x;
    int i;
    x=a[r];
    i=p-1;
    for(int j=p;j<=r-1;j++)
   {
        //Increment Number of Turns
        (*numTurns)++;
       if(a[j]<=x)
       {
           i=i+1;
           swap(a[i],a[j]);
       }
    }
    swap(a[i+1],a[r]);
    return i+1;
}

void quick_sort(int a[],int p,int r,int* numTurns)
{
    bool firstCall = false;
    //Took start Time
    clock_t tStart;
    if((*numTurns) == 0){
        tStart = clock();
        firstCall = true;
    }

    int q;
    if(p<r)
    {
        q=partition(a,p,r,numTurns);
        quick_sort(a,p,q-1,numTurns);
        quick_sort(a,q+1,r,numTurns);
    }
    if(firstCall){
        double executionTime = (double)((clock() - tStart)/CLOCKS_PER_SEC/1000);

        myfile<<numTurns<<\" \"<<executionTime<<\"\ \";
    }

}

int main(int argc, char *argv[])
{

    myfile.open (\"test.txt\");
    //Specify Numbe for iterations
    int numOperations = 100;
    //specify size of Array
    int size = 100;

    int arr[size];
    //call Initialize array method
    initializeArray(arr,size);
    bubble_sort(arr,size);
    cout << \"Hello World!\" << endl;
    return 0;
}