Respuesta :
Answer:
The code is given in C++. The variable name is arraySize. It should be replaced with listSize
Explanation:
// header file
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<chrono>
using namespace std;
using namespace std::chrono;
// bubble sort algorithm
void bubbleSort(int *a, int size) {
for (int i = 0; i<size - 1; i++) {
for (int j = 0; j<size - i - 1; j++) {
if (a[j]>a[j + 1]) {
//swap
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
// selection sort
void selectionSort(int *a, int size) {
for (int i = 0; i<size - 1; i++) {
int m_i = i;
for (int j = i + 1; j<size; j++) {
if (a[j]<a[m_i]) {
m_i = j;
}
}
//swap
int temp = a[i];
a[i] = a[m_i];
a[m_i] = a[i];
}
}
// insertion sort
void insertionSort(int *a, int size) {
for (int i = 1; i<size; ++i) {
int key = a[i];
int j=i-1;
for (; (j >= 0 && key < a[j]); j--) {
a[j + 1] = a[j];
}
a[j + 1] = key;
}
}
// make partition on array
int getPartition(int *a, int l, int h) {
int pvt = a[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++) {
if (a[j]<pvt) {
i++;
//swap
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
//swap
int tmp = a[i + 1];
a[i + 1] = a[h];
a[h] = tmp;
return(i + 1);
}
// quick sort
void quickSort(int *a, int l, int h) {
if (l<h) {
int p = getPartition(a, l, h);
quickSort(a, l, p - 1);
quickSort(a, p + 1, h);
}
}
// merge array
void merge(int *a, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int *L = new int[n1];
int *R = new int[n2];
for (int i = 0; i<n1; i++) {
L[i] = a[i + l];
}
for (int j = 0; j<n2; j++) {
R[j] = a[m + j + 1];
}
int i = 0, j = 0, k = 1;
while (i<n1 && j<n2) {
if (L[i] <= R[j]) {
a[k] = L[i];
i++;
}
else {
a[k] = R[j];
j++;
}
k++;
}
while (i<n1) {
a[k] = L[i];
i++;
k++;
}
while (j<n2) {
a[k] = R[j];
j++;
k++;
}
}
// merge sort
void mergeSort(int *a, int l, int r) {
if (l<r) {
int m = l + (r - l) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}
int* randomData(int size) {
int *ar = new int[size];
for (int i = 0; i<size; i++) {
ar[i] = rand();
}
return(ar);
}
void copyAry(int *a, int *b, int size) {
for (int i = 0; i < size; i++) {
a[i] = b[i];
}
}
int main() {
int arraySize = 1000;
int *arrLst = new int[arraySize];
int *arLst = new int[arraySize];
arrLst = randomData(arraySize);
//copy array
// because after sorting arry will be sorted
copyAry(arLst, arrLst, arraySize);
auto start1 = high_resolution_clock::now();
bubbleSort(arLst, arraySize);
auto end1 = high_resolution_clock::now();
auto duration1 = duration_cast<microseconds>(end1 - start1);
cout << duration1.count()<<endl;
// copy array for new sort
copyAry(arLst, arrLst, arraySize);
auto start2 = high_resolution_clock::now();
selectionSort(arLst, arraySize);
auto end2 = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(end2 - start2);
cout << duration2.count() << endl;
// copy array for new sort
copyAry(arLst, arrLst, arraySize);
auto start3 = high_resolution_clock::now();
insertionSort(arLst, arraySize);
auto end3 = high_resolution_clock::now();
auto duration3 = duration_cast<microseconds>(end3 - start3);
cout << duration3.count() << endl;
// copy array for new sort
copyAry(arLst, arrLst, arraySize);
auto start4 = high_resolution_clock::now();
mergeSort(arLst, 0,arraySize-1);
auto end4 = high_resolution_clock::now();
auto duration4 = duration_cast<microseconds>(end4 - start4);
cout << duration4.count() << endl;
// copy array for new sort
copyAry(arLst, arrLst, arraySize);
auto start5 = high_resolution_clock::now();
quickSort(arLst, 0,arraySize-1);
auto end5 = high_resolution_clock::now();
auto duration5 = duration_cast<microseconds>(end5 - start5);
cout << duration5.count() << endl;
ofstream out("GroupAssignment2Results.csv");
out << "Array Size,Bubble Sort Time,Selection Sort Time,Insertion Sort Time,Quick Sort Time,Merge Sort Time\n";
out << arraySize << "," << duration1.count() << "," << duration2.count() << "," << duration3.count() << "," << duration5.count() << "," << duration4.count();
cout << "\nOutput in File.";
out.close();
cin.get();
return(0);
}
