Consider the following C++ programs:- 1. Bubble Sort 2. Insertion Sort 3. Selection Sort
Answer:
Step 1
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp, flag=0;
for(i = 0; i < n; i++)
{
for(j = 0; j < n-i-1; j++)
{
// introducing a flag to monitor swapping
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
// if swapping happens update flag to 1
flag = 1;
}
}
// if value of flag is zero after all the iterations of inner loop
// then break out
if(flag==0)
{
break;
}
}
// print the sorted array
printf("Sorted Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], i, n, step, temp;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
{
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function bubbleSort
bubbleSort(arr, n);
return 0;
}
Step 2
In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,
(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n2)
Hence the time complexity of Bubble Sort is O(n2).
The main advantage of Bubble Sort is the simplicity of the algorithm.
The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable.
Also, the best case time complexity will be O(n), it is when the list is already sorted.
Following are the Time and Space complexity for the Bubble Sort algorithm.
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
Step 3
#include <stdlib.h>
#include <iostream>
using namespace std;
//member functions declaration
void insertionSort(int arr[], int length);
void printArray(int array[], int size);
// main function
int main()
{
int array[5] = {5, 1, 6, 2, 4, 3};
// calling insertion sort function to sort the array
insertionSort(array, 6);
return 0;
}
void insertionSort(int arr[], int length)
{
int i, j, key;
for (i = 1; i < length; i++)
{
j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
key = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = key;
j--;
}
}
cout << "Sorted Array: ";
// print the sorted array
printArray(arr, length);
}
// function to print the given array
void printArray(int array[], int size)
{
int j;
for (j = 0; j < size; j++)
{
cout <<" "<< array[j];
}
cout << endl;
}
output:-
Sorted Array: 1 2 3 4 5 6
Step 4
As we mentioned above that insertion sort is an efficient sorting algorithm, as it does not run on preset conditions using for loops, but instead it uses one while loop, which avoids extra steps once the array gets sorted.
Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
Step 5
// C program implementing Selection Sort
# include <stdio.h>
// function to swap elements at the given index values
void swap(int arr[], int firstIndex, int secondIndex)
{
int temp;
temp = arr[firstIndex];
arr[firstIndex] = arr[secondIndex];
arr[secondIndex] = temp;
}
// function to look for smallest element in the given subarray
int indexOfMinimum(int arr[], int startIndex, int n)
{
int minValue = arr[startIndex];
int minIndex = startIndex;
for(int i = minIndex + 1; i < n; i++) {
if(arr[i] < minValue)
{
minIndex = i;
minValue = arr[i];
}
}
return minIndex;
}
void selectionSort(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
int index = indexOfMinimum(arr, i, n);
swap(arr, i, index);
}
}
void printArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {46, 52, 21, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Note: Selection sort is an unstable sort i.e it might change the occurrence of two similar elements in the list while sorting. But it can also work as a stable sort when it is implemented using linked list.
Step 6
Selection Sort requires two nested for loops to complete itself, one for loop is in the function selectionSort, and inside the first loop we are making a call to another function indexOfMinimum, which has the second(inner) for loop.
Hence for a given input size of n, following will be the time and space complexity for selection sort algorithm:
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n2)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
