Problem #5. (Programming) Sorting (30 pts) Implement Bubble Sort, Insertion Sort
ID: 3589134 • Letter: P
Question
Problem #5. (Programming) Sorting (30 pts) Implement Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, and Quicksort for a list of integers. Your program will get 3 arguments in the command line which are 1) a character indicating the sorting method, 2) input file name, and 3) output file name, as follows: Your Executable.exe Q input sort. txt output sort.txt where 'Q' indicates Quicksort, and "input_sort.txt" and "output sort.txt" are input and output file names, respectively. You must use "B',M,Hand 'Q' for Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, and Quicksort, respectively You will have the number of objects N followed by the numbers a, a2aw in the input file. The output format is similar but the items should be sorted. Refer the following example: my list.txt my list sorted.txt 10 54123109882 10 122345889 10 Assume that the numher of objects N ranges 1 s N s 10,000,000 and the objects are 32-bit integens. You are also required to report the running time to the console. For instance: > Your Executable.exe Q my list.txt my list sorted.txt Quicksort for 10 integers took 0.265512 seconds. Note that, you need to mecasure the computational time only for sorting by excluding times for L/O You are additionally asked to perform a simple empirical analysis on running times of four different sorting algorithms with respect to the number of items N 100, 1000, 10000,... 10000000 Uilize randomly distributed lists for the experiment and provide a resulting table as follows: 10.010:000100.00 1,000,000 10,000,000 Bubble Sort NN Insertion Sot mSKX ms xx ms N/A VA N/A NA N/A Merge Sortxxms Heup Sort Quicksort You can fill "N/A if the algorithm is too slow (eg, - 10 sec) to solve the problem. Note that, you are recommeded to build your program in the release mode for a faster performance. You ars anked to brichy deerabe your algorithims in the repot and name your Hource code tile ID AI Sort.eppExplanation / Answer
#include<iostream>
#include <fstream>
#include<cstring>
#include<time>
using namespace std;
void accept(int intArray[], long int s);
void display(int intArray[], long int s);
void insertionSort(int intArray[], long int s);
void ssort(int intArray[], long int s);
void bubbleSort(int intArray[],long int s);
void quickSort(int intArray[], int low, long int high);
int partition (int intArray[], int low, long int high);
void swap(int* a, int* b);
void mergeSort(int *a, int low, long int high);
void merge(int *a, int low, long int high, long int mid);
void findMaxHeap(int a[], int i, long int n);
void heapSort(int a[], long int n);
void generateMaxHeap(int a[], long int n);
int main(int argc, char *argv[])
{
int a, i=0;
long int n;
int *intArray;
string sortType, sortName;
string inputFileName,outputFileName;
sortType = argv[1];
inputFileName = argv[2];
outputFileName = argv[3];
std::fstream inputFile(inputFileName, std::ios_base::in);
inputFile >> n;
intArray = new int[n];
while (inputFile >> a)
{
intArray[i] = a;
i++;
}
clock_t start = clock();
switch(sortType)
{
case "B":bubbleSort(intArray,n);
sortName = "Bubble Sort";
break;
case "I":insertionSort(intArray,n);
sortName = "Insertion Sort";
break;
case "M":mergeSort(intArray, 0, n);
sortName = "Merge Sort";
break;
case "H":generateMaxHeap(intArray, n-1);
heapSort(intArray, n-1);
sortName = "Heap Sort";
break;
case "Q":quickSort(intArray, 0, n);
sortName = "Quick Sort";
break;
default:cout<<" Invalid choice";
}
clock_t stop = clock();
cout<<" "<<sortname<<" for"<< n << " integers took" << (double)(clock() - tStart)<<" seconds";
return 0;
}
// Method to perform insertion sort
void insertionSort(int intArray[], long int s)
{
int I,J,Temp;
for(I=1;I<s;I++)
{
Temp=intArray[I];
J=I-1;
while((Temp<intArray[J]) && (J>=0))
{
intArray[J+1]=intArray[J];
J--;
}
intArray[J+1]=Temp;
}
}
// Method to perform bubble sort
void bubbleSort(int intArray[],long int s)
{
int I,J,Temp;
for(I=0;I<s-1;I++)
{
for(J=0;J<(s-1-I);J++)
if(intArray[J]>intArray[J+1])
{
Temp=intArray[J];
intArray[J]=intArray[J+1];
intArray[J+1]=Temp;
}
}
}
// Method to provide partiotion for quick sort
int partition (int intArray[], int low, long int high)
{
int pivot = intArray[high];
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if (intArray[j] <= pivot)
{
i++;
swap(&intArray[i], &intArray[j]);
}
}
swap(&intArray[i + 1], &intArray[high]);
return (i + 1);
}
// Method to perform quick sort
void quickSort(int intArray[], int low, int long high)
{
if (low < high)
{
int part = partition(intArray, low, high);
quickSort(intArray, low, part - 1);
quickSort(intArray, part + 1, high);
}
}
// Method to swap positions
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// Method to perform merge sort via merging divided array
void merge(int *a, int low, long int high, long int mid)
{
long int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// Mergesort method to divide array
void mergeSort(int *a, int low, long int high)
{
long int mid;
if (low < high)
{
mid=(low+high)/2;
mergeSort(a, low, mid);
mergeSort(a, mid+1, high);
merge(a, low, high, mid);
}
}
// Method to find max heap
void findMaxHeap(int a[], int i, long int n)
{
long int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
// Method to perform heap sort
void heapSort(int a[], long int n)
{
long int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
findMaxHeap(a, 1, i - 1);
}
}
// Method to generate max heap
void generateMaxHeap(int a[], long int n)
{
long int i;
for(i = n/2; i >= 1; i--)
findMaxHeap(a, i, n);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.