Answers
Task 4: Selection Sort
============================================================================================
#include<iostream>
#include<fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
//printf("min index is: %d\n",min_idx);
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
void display(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
int main()
{
ifstream inputFile("descending_mostly_sorted.txt");
int arr[1000];
int count=0;
//start time and end time stored here
clock_t start, end;
long timeElapsed;
if (inputFile.is_open())
{
while(!inputFile.eof())
{
inputFile>>arr[count++];
}
cout<<"Array before sorting: \n";
display(arr,count);
//count the time before searching
start = clock();
selectionSort(arr,count);
//count the time after searching
end = clock();
timeElapsed = end - start;
cout<<"\nArray after sorting: \n";
display(arr,count);
//print the time taken by searching
cout << "\nTime taken for sorting: " << timeElapsed << " milliseconds" << endl;
}
else
cout << "File cannot be opened.";
return 0;
}
============================================================================================
Output
============================================================================================
Task 5: Insertion Sort
============================================================================================
#include<iostream>
#include<fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
void insertionSort(int arr[],int n)
{
int i, j;
int temp;
for (i = 1; i <n; i++)
{
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = temp;
}
}
void display(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
int main()
{
ifstream inputFile("descending_mostly_sorted.txt");
int arr[1000];
int count=0;
//start time and end time stored here
clock_t start, end;
long timeElapsed;
if (inputFile.is_open())
{
while(!inputFile.eof())
{
inputFile>>arr[count++];
}
cout<<"Array before sorting: \n";
display(arr,count);
//count the time before searching
start = clock();
insertionSort(arr,count);
//count the time after searching
end = clock();
timeElapsed = end - start;
cout<<"\nArray after sorting: \n";
display(arr,count);
//print the time taken by searching
cout << "\nTime taken for sorting: " << timeElapsed << " milliseconds" << endl;
}
else
cout << "File cannot be opened.";
return 0;
}
============================================================================================
Ouptut
