In this assignment, you are given three sorting algorithms. You are asked to do
ID: 3687128 • Letter: I
Question
In this assignment, you are given three sorting algorithms. You are asked to do the following:
1. Modify the bubble-sort function such that the outer loop stops iterating as soon as there have been no swaps in the inner loop. That is, as soon as the array is already sorted.
2. Modify each function such that you count the number of comparisons between array elements that they perform.
Each function will output the final sorted array and the number of comparisons the function has performed.
3. Write a C++ program that receives as input an array of integers and runs each sorting algorithm (a separate function call on the original input) and outputs the final sorted array and number of comparisons each algorithm performs.
One input to your program is the following: 18 20 11 25 17 27 9 13 24 8 28 14 5 19 23 6 29 4 30 22 10 16 21 3 5 7 26
Selection Sort:
void selection(int a[], int l, int r)
{
for (int i = l; i < r; i++)
{ int min = i;
for (int j = i+1; j <= r; j++)
if (a[j] < a[min]) min = j;
exch(a[i], a[min]); }
}
Insertion Sort:
void insertion(int a[], int l, int r)
{ int i;
for (i = r; i > l; i--)
compexch(a[i-1], a[i]);
for (i = l+2; i <= r; i++)
{
int j = i;
int v = a[i];
while (v < a[j-1])
{ a[j] = a[j-1]; j--; }
a[j] = v; }
}
Bubble Sort:
void bubble(int a[], int l, int r)
{
for (int i = l; i < r; i++)
for (int j = r; j > i; j--)
compexch(a[j-1], a[j]);
}
Explanation / Answer
Answer:
Note: functions are provided in the code:
Modified code:
#include <iostream>
#include <stdlib.h>
using namespace std;
void selection(int a[], int l, int r);
void insertion(int a[], int l, int r);
void bubble(int a[], int l, int r);
void exch(int A,int B)
{
int temp=A;
A=B;
B=temp;
}
void compexch(int A, int B)
{
if (B < A)
exch(A, B);
}
int main()
{
int a[]={18,20,11,25,17,27,9,13,24,8,28,14,5,19,23,6,29,4,30,22,10,16,21,3,5,7,26};
int temp,size;
for(int i=0;i<=size;i++)
{
selection(a[],size,temp);
insertion(a[],size,temp);
bubble(a[],size,temp);
}
return 0;
}
void selection(int a[], int l, int r)
{ for (int i = l; i < r; i++)
{ int min = i;
for (int j = i+1; j <= r; j++)
if (a[j] < a[min]) min = j;
exch(a[i], a[min]);
}
}
void insertion(int a[], int l, int r)
{ int i;
for (i = r; i > l; i--) compexch(a[i-1], a[i]);
for (i = l+2; i <= r; i++)
{ int j = i;
int v = a[i];
while (v < a[j-1])
{ a[j] = a[j-1]; j--; }
a[j] = v;
}
}
void bubble(int a[], int l, int r)
{ for (int i = l; i < r; i++)
for (int j = r; j > i; j--)
compexch(a[j-1], a[j]);
}