CalSelectionSortExecutionTime : https://app.box.com/s/r5zyc652vatqpzz8r3gmgktdnd
ID: 645009 • Letter: C
Question
CalSelectionSortExecutionTime : https://app.box.com/s/r5zyc652vatqpzz8r3gmgktdndoik10r
bubbleSort.java : https://app.box.com/s/iin2q7xc560wjvnxjm823ksuoek15ka6
insertSort.java : https://app.box.com/s/9jrksplmru00gs4uyfgxnosv7in2qyo1
I don't really know what is meant by new insertion sort also :(
In-Lab Exercise 2: Runtime Measurement A better way to measure elapsed system time for programs is to use the standard clock function. The clock function takes no arguments and returns the amount of time the processing unit of the computer has used in the execution of the program. (use System.currentTimeMillis() method for getting current time in milliseconds) Use the three sorting algorithms from textbook, time the execution of the algorithms on different sizes of elements - 256, 512, 1024, and 2048. Do you see the pattern in how the execution time increases? Record your findings in the table below: sem142 cs204 W4-Sort Array size 256 512 1024 2048 Bubble sort Insertion sort New Insertion sortExplanation / Answer
Answer
#include
#include
#include
#include
using namespace std;
long length = 256;
const long max_length = 2048;
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 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 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;
for (length = 256; 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 256 :
length = 512;
break;
case 512 :
length = 1024;
break;
case 1024 :
length = 2048;
break;
case 2048 :
length = 2050;
break;
}
}
return 0;
}