LAB EXERCISE – 1
NAME: BANGI PAVAN KUMAR
REG_NO: 21BRS1612
INSERTION SORT ANALYSIS
Instructions
1. BEST CASE ANALYSIS (Min for 5 values of n)
2. WORST CASE ANALYSIS (Min for 5 values of n)
[Link] CASE ANALYSIS CODE:
#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>
#include <random>
using namespace std;
vector<int> insertionSort(vector<int>&);
int main() {
vector<int> n_values = {10, 50, 100, 500, 1000};
for (int n : n_values) {
vector<int> avector(n);
for (int i = 0; i < n; ++i) {
avector[i] = i + 1;
auto startTime = chrono::high_resolution_clock::now();
avector = insertionSort(avector);
auto endTime = chrono::high_resolution_clock::now();
chrono::duration<double> elapsedTime = endTime - startTime;
cout << "Best Case Analysis for n = " << n << endl;
cout << "Time taken: " << fixed << setprecision(9) << [Link]() << " seconds" << endl;
cout << endl;
}
return 0;
vector<int> insertionSort(vector<int>& avector) {
for (unsigned int index = 1; index < [Link](); index++) {
int currentValue = avector[index];
unsigned int position = index;
while (position > 0 && avector[position - 1] > currentValue) {
avector[position] = avector[position - 1];
position--;
avector[position] = currentValue;
return avector;
[Link] CASE ANALYSIS
#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>
#include <random>
using namespace std;
vector<int> insertionSort(vector<int>&);
int main() {
vector<int> n_values = {10, 50, 100, 500, 1000};
for (int n : n_values) {
vector<int> avector(n);
for (int i = 0; i < n; ++i) {
avector[i] = n - i;
auto startTime = chrono::high_resolution_clock::now();
avector = insertionSort(avector);
auto endTime = chrono::high_resolution_clock::now();
chrono::duration<double> elapsedTime = endTime - startTime;
cout << "Worst Case Analysis for n = " << n << endl;
cout << "Time taken: " << fixed << setprecision(9) << [Link]() << " seconds" << endl;
cout << endl;
return 0;
vector<int> insertionSort(vector<int>& avector) {
for (unsigned int index = 1; index < [Link](); index++) {
int currentValue = avector[index];
unsigned int position = index;
while (position > 0 && avector[position - 1] > currentValue) {
avector[position] = avector[position - 1];
position--;
avector[position] = currentValue;
return avector;
}
OUTPUTS:
*”CODE FOR INSERTION SORT N NUMBERS”
TABLE Best Case Analysis:
n Time Taken (seconds)
10 0.000002390
50 0.000001320
100 0.000001100
500
0.000004320
1000 0.000010270
1300 0.000011300
1500 0.000036390
1700 0.000024310
2000 0.000018850
2500 0.000052190
3000 0.000045609
TABLE Worst Case Analysis:
n Time Taken (seconds)
10 0.000004600
50 0.000015160
100 0.000058800
500 0.001312020
1000 0.004770059
1300 0.008821368
1500 0.010888449
1700 0.081014307
2000 0.017248518
2500 0.090462606
3000 0.100065335
GRAPH FOR BESTAND WORST CASE ANALYSIS: