Implement the following sorting algorithms: selection sort, insertion sort, quic
ID: 673310 • Letter: I
Question
Implement the following sorting algorithms: selection sort, insertion sort, quick sort and merge sort, and compare them by real running time Requirements Find the running time as follows: check the current time t1; repeat the folio wing steps 1000 times { randomly generate 100000 integers and save into array A; sort the integers in A using selection sort (or insertion sort, quick sort, merge sort); } check the current time t2; running time of selection sort (or insertion sort, quick sort, merge sort) : =t2 - tl; Implement the algorithms using C, C++, C#, or any other programming language. Submission Project description, Algorithms, Algorithm time complexity, Experiment output (average running time from 5 tests for each algorithm), comparison/analysis of the running times of different algorithms, Code.Explanation / Answer
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
void selectSort(int arr[], int n)
{
//pos_min is short for position of min
int pos_min,temp;
for (int i=0; i < n-1; i++)
{
pos_min = i;//set pos_min to the current index of array
for (int j=i+1; j < n; j++)
{
if (arr[j] < arr[pos_min])
pos_min=j;
//pos_min will keep track of the index that min is in, this is needed when a swap happens
}
//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
if (pos_min != i)
{
temp = arr[i];
arr[i] = arr[pos_min];
arr[pos_min] = temp;
}
}
}
void insertionSort(int arr[], int n) {
int temp;
for (int i = 1; i < n; i++)
{
for (int j = i; j >= 1; j--)
{
if (arr[j] < arr[j-1])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
else
break;
}
}
}
int partition(int *arr, const int left, const int right) {
const int mid = left + (right - left) / 2;
const int pivot = arr[mid];
// move the mid point value to the front.
std::swap(arr[mid],arr[left]);
int i = left + 1;
int j = right;
while (i <= j) {
while(i <= j && arr[i] <= pivot) {
i++;
}
while(i <= j && arr[j] > pivot) {
j--;
}
if (i < j) {
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i - 1],arr[left]);
return i - 1;
}
void quicksort(int *arr, const int left, const int right, const int sz){
if (left >= right) {
return;
}
int part = partition(arr, left, right);
quicksort(arr, left, part - 1, sz);
quicksort(arr, part + 1, right, sz);
}
void merge(int *a, int low, int high, int mid)
{
int i, j, k, c[100000];
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 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;
}
int main() {
//random number seed
srand (time(NULL));
int l = 1;
const clock_t begin_time1 = clock();
for(int i=0; i<l; i++) {
int rno[100000];
for(int j=0; j<100000; j++)
rno[i] = rand() % 10000;
int len = 100000;
selectSort(rno, len);
}
cout <<" Time taken for selection sort: "<<float( clock () - begin_time1 ) / CLOCKS_PER_SEC;
const clock_t begin_time2 = clock();
for(int i=0; i<l; i++) {
int rno[100000];
for(int j=0; j<100000; j++)
rno[i] = rand() % 10000;
int len = 100000;
insertionSort(rno, len);
}
cout <<" Time taken for insertion sort: "<<float( clock () - begin_time2 ) / CLOCKS_PER_SEC;
const clock_t begin_time3 = clock();
for(int i=0; i<l; i++) {
int rno[100000];
for(int j=0; j<100000; j++)
rno[i] = rand() % 10000;
int len = 100000;
quicksort(rno, 0, len-1, len);
}
cout <<" Time taken for quick sort: "<<float( clock () - begin_time3 ) / CLOCKS_PER_SEC;
const clock_t begin_time4 = clock();
for(int i=0; i<l; i++) {
int rno[100000];
for(int j=0; j<100000; j++)
rno[i] = rand() % 10000;
int len = 100000;
mergesort(rno, 0, len-1);
}
cout <<" Time taken for merge sort: "<<float( clock () - begin_time4 ) / CLOCKS_PER_SEC;
cout<<" ";
return 0;
}