The following algorithms and their complexity: Selection Sort Quick Sort Bubble

Question

The following algorithms and their complexity:

Selection Sort

Quick Sort

Bubble Sort

Merge Sort

Insertion Sort

For this program you will run each sort and measure the execution time. Then you will present a table with the type of sort, the complexity and the average execution time for each type of input. Then you will decide if the results are consistent with the complexity estimate.

Before the program you can do the following. Assemble the code. There are algorithms for 4 of the algorithms in the slides so you must find code or an algorithm for merge sort to use or implement. For this program you can use code written by someone else. Always cite your source! You only need to read the file. You are not required to save the sorted data.

You should prepare the data files. You should have large data sets. We will work with only integer values. To save time you should prepare 3 data files in advance. One has the numbers in random order. One is already sorted. The third is sorted, but in reverse order.

SUGGESTION: You can create a file with the random order. Implement a sorting algorithm and sort that file. Modify the comparison in your algorithm to sort it in reverse order.

Create a table of the results. Compare your results to the Big-O estimates of complexity. Are they consistent? If they are not consistent can you explain the difference?

Explanation / Answer

Hi,

Below is the solution to your problem:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

long length = 1000;
const long max_length = 300000;

int list[max_length];

void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void selection_sort(int i, int length)
{
int min_ele_loc;
for (long i = 0; i < length; ++i)
{
//Find minimum element in the unsorted array
//Assume it's the first element
min_ele_loc = i;
   //Loop through the array to find it
for (long j = i + 1; j < length; ++j)
{
if (ar[j] < ar[min_ele_loc])
{
//Found new minimum position, if present
min_ele_loc = j;
}
}
}
//Swap the values
swap (ar[i], ar[min_ele_loc]);
}  
}

void bubbleSort()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list[j] > list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void merge(int *,int, int , int );
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(int *a, int low, int high, int mid)
{
long i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}
void insertionSort()
{
int temp;
for(long i = 1; i < length; 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;
   double value1,value2,value3,value4,value5;

for (length = 1000; length <= max_length; )
{
cout << " Length : " << length << ' ';

read();
t1 = clock();
bubbleSort();
t2 = clock();
       value1=(t2 - t1)/CLK_TCK;
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";
      

read();
t3 = clock();
insertionSort();
t4 = clock();
       value2=(t4 - t3)/CLK_TCK;
cout << "Insertion Sort : " << (t4 - t3)/CLK_TCK << " sec ";
  
read();
t5 = clock();
quickSort(0, length - 1);
t6 = clock();
       value3=(t6 - t5)/CLK_TCK;
cout << "Quick Sort : " << (t6 - t5)/CLK_TCK << " sec ";
      
       read();
       t7=clock();
       mergesort(i, 0, length-1);
       t8=clock();
       value4=(t8-t7)/CLK_TCK;
       cout<< "Merge Sort :"<<(t8-t7)/CLK_TCK<<"Sec ";
      
       read();
       t9=clock();
       selection_sort (i, length);
       t10=clock();
       value5=(t10-t9)/CLK_TCK;
       cout<< "Merge Sort :"<<(t10-t9)/CLK_TCK<<"Sec ";

switch (length)
{
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;
}
}
cout<<"Lets print the table for time taken by each sort:"<<" ";
   cout<<"Table1:"<<" ";
   cout<<"Bubble sort"<<" " " " " ";
   cout<<"value1"<<" ";
   cout<<"Insertion sort"<<" " " " " ";
   cout<<"value2"<<" ";
   cout<<"Quick Sort"<<" " " " " ";
   cout<<"value3"<<" ";
   cout<<"Merge sort"<<" " " " " ";
   cout<<"value4"<<" ";
   cout<<"Selection sort"<<" " " " " ";
   cout<<"value5"<<" ";
return 0;
}

------------------------------------------------------------------------------------------------------------------------------------------

You can use this program on a filr called random.dat which can be created using the following code:

1.This will give a file random.dat that gives the data set1 with random values.

#include <fstream>

#include <cstdlib>

#include <ctime>

using namespace std;

const size_t length = 300000;

int main()

{

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

    srand(time(NULL));

    int r;

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

    {

        r = rand();

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

    }

    fout.close();

    return 0;

}

-----------------------------------------------------------------------------------------------------------------------------------------------

2.Dataset with sorted values.

And you can use any of the sort to sort the same random.dat file to run the same program in order to get a dataset with sorted values:

------------------------------------------------------------------------------------------------------------------------------------------------

3.Dataset with values sorted in reverse order.

Use the same random.dat file that sorts the values and then run the same file to sort the elements in reverse order.

Hope this helps...HAPPY ANSWERING!!!!!!!!!!!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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