need help with this Time and compare the algorithms (from the HSR text) for inse

Question

need help with this

Time and compare the algorithms (from the HSR text) for insertion sort, merge sort and quicksort Measure average time by generating n random data values and calling the three sorts for the same data Vary n and graph the times Tin) as a function of n To obtain the elapsed tme call a timing function within your program, that starts the timer just before and stops it just after the section to be timed Be .To obtain accurate timings Tin). run the program (for a particular n) with the same data in a loop, and divide the total time for the loop by the number of . To check your program sorts correctly, also output the sequence of points to be sorted as well as te sorted sequence (with each sort) for n . 10 only for each sort. The range of n should be determined so that it allows to compare the performance of the algorithms sure that there is no l/O in the tirned section iterations 0e, take the average time per iteration) this will give you one data point as the time T(n) in your graph of log file or screenshots to show these On inux or mac use "script to generate a typescript file showing your compilation and execution with output of the program. Otherwise add another type Subit your program, input and output for small (n-10) runs, and report describing methods used (including random number generator, data range used timing function and its precision). The program should be well-commented and have a description of input and output parameters for each sorting function Your report should further contain your plots and a discussion of the results, also comparing your observations to the theoretical time complexity

Explanation / Answer

#include <fstream>

#include <cstdlib>

#include <ctime>

using namespace std;

const size_t size = 300000;

int main()

{

    ofstream fout("random.dat", ios::binary);

    srand(time(NULL));

    int k;

    for (size_t i = 0; i < length; i++)

    {

k = rand(); //rand function is used to generate the random numbers.

        fout.write((char*)&k, sizeof(k));

    }

    fout.close();

    return 0;

}

Comparision code for insrtion sort, merge sort and qiuck sort.

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <ctime>

using namespace std;

long length = 1000;

const long max_size = 300000;

int list[maxsize];

void read()

{

    ifstream fin("random.dat", ios::binary);

    for (long i = 0; i < size; i++)

    {

        fin.read((char*)&list[i], sizeof(int));

    }

    fin.close();

}

void MergeSort()

{

    int temp;

    for(long i = 0; i < size; i++)

    {

        for(long j = 0; j < size-i-1; j++)

        {

            if (list[j] > list[j+1])

            {

                temp        = list[j];

                list[j]     = list[j+1];

                list[j+1]   = temp;

            }

        }

    }

}

void insertionSort()

{

    int temp;

    for(long i = 1; i < size; i++)

    {

        temp = list[i];

        long j;

        for(j = i-1; j >= 0 && list[j] > temp; j--)

        {

            list[j+1] = list[j];

        }

        list[j+1] = temp;

    }

}

long partition(long left, long right)

{

    int pivot_element = list[left];

    int lb = left, ub = right;

    int temp;

    while (left < right)

    {

        while(list[left] <= pivot_element)

            left++;

        while(list[right] > pivot_element)

            right--;

        if (left < right)

        {

            temp        = list[left];

            list[left] = list[right];

            list[right] = temp;

        }

    }

    list[lb] = list[right];

    list[right] = pivot_element;

    return right;

}

void quickSort(long left, long right)

{

    if (left < right)

    {

        long pivot = partition(left, right);

        quickSort(left, pivot-1);

        quickSort(pivot+1, right);

    }

}

int main()

{

    double t1, t2;

    for (size = 1000; size <= max_size; )

    {

        cout << " Length : " << size << ' ';

        read();

        t1 = clock();

MergeSort();

        t2 = clock();

        cout << "Merge Sort : " << (t2 - t1)/CLK_TCK << " sec "; //Timing calculation for mergesort

        read();

        t1 = clock();

        insertionSort();

        t2 = clock();

        cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec "; timing calculatin for insertion sort

        read();

        t1 = clock();

        quickSort(0, length - 1);

        t2 = clock();

        cout << "Quick Sort : " << (t2 - t1)/CLK_TCK << " sec "; //timing calculation for quicksort.

        switch (size) . //testcase length switcher.

        {

        case 1000 :

            length = 5000;

            break;

        case 5000 :

            length = 10000;

            break;

        case 10000 :

            length = 50000;

            break;

        case 50000 :

            length = 100000;

            break;

        case 100000 :

            length = 200000;

            break;

        case 200000 :

            length = 300000;

            break;

        case 300000 :

            length = 300001;

            break;

        }

    }

    return 0;

}

Please rate me, any sort of help please comment me

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.