C++ code: You are going to compare the runtime of Bubble, Selection, and Inserti
ID: 3683929 • Letter: C
Question
C++ code:
You are going to compare the runtime of Bubble, Selection, and Insertion sort on 10,000 data points. You will read in 3 datasets from files (these names will be hard coded):
1) Random data a. random.txt 2) Data in reverse order (minimum to maximum) a. reversed.txt 3) Data that is nearly sorted (some data is swapped, but overall it is in order) a. nearly.txt
You will be sorting from largest to smallest.
Bubble and Selection sort will be implemented on arrays; Insertion sort will be implemented on a LinkedList (see class structure below).
Also implement Insertion sort on an array and compare that time as well.
To determine the time an algorithm takes, you will need to use the clock() function.
You will need to use a try-catch to be sure that the files can be read
Specifications:
Inputs:
1) From file a. 3 files (above) b. Hard coded names c. Each has the same 10,000 numbers in different orders
Outputs:
1) A table of runtimes from each algorithm on each different data set. a. Each time you run your code may result in different runtimes, this is normal
Functions:
1) double bubbleSort(int sz, int A[]) a. performs a bubble sort and returns the time required 2) double selectionSort(int sz, int A[]) a. performs a selection sort and returns the time required 3) double insertionSort (int sz, int A[]) a. performs a insertion sort and returns the time required b. LinkedList class is called here 4) If you do the extra credit: a. double insertionSortArray(int sz, int A[]) i. performs a insertion sort and returns the time required
Class:
You will need to create a LinkedList class: 1) structs a. struct ListNode i. int value ii. ListNode *next iii. ListNode(int v, ListNode *n) 2) Attributes a. ListNode *head 3) Functions a. LinkedList() b. ~LinkedList() c. void add(int v) d. void printList()
Explanation / Answer
#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 d = 0; d < length; d++)
{
fin.read((char*)&list[d], sizeof(int));
}
fin.close();
}
void bubbleSort()
{
int temp;
for(long d = 0; d < length; d++)
{
for(long m = 0; m < length-d-1; m++)
{
if (list[m] > list[m+1])
{
temp = list[m];
list[m] = list[m+1];
list[m+1] = temp;
}
}
}
}
void insertionSort()
{
int temp;
for(long d = 1; d < length; d++)
{
temp = list[d];
long m;
for(m = d-1; m >= 0 && list[m] > temp; m--)
{
list[m+1] = list[m];
}
list[m+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);
}
}
/*main method*/
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; )
{
cout << " Length : " << length << ' ';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort : " << (t2 - t1)/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;
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.