# Introduction to Algorithms - Solutions - Chapter 2 (Part 1)

The solutions to the things we discussed yesterday

## The Insertion Sort C++ Program

This is the program:

#include <iostream>
using namespace std;

int main()
{
int N; //Here, N is the size of the array

int input_arr[N]; //input_arr is the array we use to store the input

for(int i=0; i<N;i++)
cin>>input_arr[i];

for(int j=1;j<N;j++)
{

int key=input_arr[j];
int i=j-1;

while(i!<0&&input_arr[i]>key) //Here, we have to include the case when i becomes zero, becuase it does
{
input_arr[i+1]=input_arr[i];
i--;
}

input_arr[i+1]=key;

}

for(int i=0;i<N;i++)
cout<<input_arr[i]<<"\n";

return 0;

}


## The Bubble Sort Problem

I wrote the program for bubble sort, so that it’d be easier to understand. Here it is:

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{

int N; //Same as the earlier one
cin>>N;
int input_arr[N];

for(int i=0; i<N;i++)
cin>>input_arr[i];

for(int j=1;j<N;j++)
{

for(int i=0;i<N;i++)
{

if(input_arr[i]>input_arr[j])
swap(input_arr[i],input_arr[j]);

}
}
for(int i=0;i<N;i++)
cout<<input_arr[i]<<"\n";

return 0;
}


### Proving the Correctness of Bubble Sort

Initialisation: At the start, j=1, which means input_arr[1...j+1-1] contains 1 element. Therefore, it is necessarily sorted.

Maintenance: At each loop of j, we get a sorted array from input_arr[1...j+1-1]. Therefore, it is sorted.

Termination: In the final loop of j, we get a sorted array from input_arr[1...N+1-1]. Therefore, it is sorted. (Remember that N in the code implies N+1 in the pseudocode, when you are dealing with array indices).

Hence, the given algorithm is correct.