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

in Study / Notes on Algorithms

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.