Bubble Sort | Insertion Sort

Sorting Algorithms

Algorithms are used to sort the numbers based on some conditions. These algorithms are further judged based on space & time complexity.

Sorting Algorithms are listed below:

  1. Bubble sort
  2. Insertion sort
  3. Quick sort
  4. Merge sort
  5. Heap sort

BUBBLE SORT

Definition: It is a comparison​-based algorithm. It compares each pair of elements in an array and swaps them if they are out of order until the entire array is sorted. It works by repeatedly swapping the adjacent elements if they are in wrong order.

Logic Behind it:

 

Fig: bubble sort by w3resource

 

Program to implement the logic

include<iostream>

using namespace std;

int main()

{

    int a[50],n,i,j,temp;

    cout<<"Enter the size of array: ";

    cin>>n;

    cout<<"Enter the array elements: ";

    

    for(i=0;i<n;i++)

        cin>>a[i];

        

    for(i=1;i<n;i++)

    {

        for(j=0;j<(n-i);j++)

            if(a[j]>a[j+1])

            {

                temp=a[j];

                a[j]=a[j+1];

                a[j+1]=temp;

            }

    }

    cout<<"Array after bubble sort:";

    for(i=0;i<n;i++)

        cout<<" "<<a[i]   

    return 0;

}

 

Output:

Algorithm Source:

It could be directly forked from my github repo:

https://github.com/anwesha999/Basic_Algorithms

feel free to raise issue, pull requests for further understanding of concepts elaborated in my github repo.

 

INSERTION SORT

 

Definition: The idea of insertion sort algorithm is to build your sorted array in place, shifting elements out of the way if necessary to make room as you go.

Logic Behind insertion sort algorithm

Step 1: call the 1st element of the array sorted.

Step 2: repeat until all the elements are sorted by shifting the requisite no of the elements.

Image result for insertion sort images

Fig: insertion sort logic by w3resource

 

Insertion Sort

#include<iostream>

using namespace std;

int main()

{

            int n, arr[50], i, j, temp;

            cout<<"Enter Array Size : ";

            cin>>n;

    cout<<n<<endl;

            cout<<"Enter Array Elements : ";

            for(i=0; i<n; i++)

            {

                        cin>>arr[i];

            }

    for(i=0; i<n; i++)

            {

                        cout<<arr[i];

            }

            cout<<"Sorting array using selection sort ... \n";

            for(i=1; i<n; i++)

            {

                        temp=arr[i];

                        j=i-1;

                        while((temp>arr[j]) && (j>=0))

                        {

                                    arr[j+1]=arr[j];

                                    j=j-1;

                        }

                        arr[j+1]=temp;

            }

            cout<<"Array after sorting : \n";

            for(i=0; i<n; i++)

            {

                        cout<<arr[i]<<" ";

            }

            return 0;

}

Output:

 

Interesting Question & Solution from Hackerrank

Challenge Q1:

Insertion Sort 
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with a nearly sorted list.

Insert element into sorted list 
Given a sorted list with an unsorted number  in the rightmost cell, can you write some simple code to insert  into the array so that it remains sorted?

Since this is a learning exercise, it won't be the most efficient way of performing the insertion. It will instead demonstrate the brute-force method in detail.

Assume you are given the array  indexed . Store the value of . Now test lower index values successively from  to  until you reach a value that is lower than ,  in this case. Each time your test fails, copy the value at the lower index to the current index and print your array. When the next lower indexed value is smaller than , insert the stored value at the current index and print the entire array.

The results of operations on the example array is:

Starting array:  
Store the value of  Do the tests and print interim results:

1 2 4 5 5

1 2 4 4 5

1 2 3 4 5

Input Format

There will be two lines of input:

The first line contains the integer , the size of the array 
The next line contains  space-separated integers 

Output Format

Print the array as a row of space-separated integers each time there is a shift or insertion.

Sample Input

5

2 4 6 8 3

Sample Output

2 4 6 8 8

2 4 6 6 8

2 4 4 6 8

2 3 4 6 8

 

Solution:

#include<iostream>

using namespace std;

void insertionSort(int n, int *a) {

 int temp,i,j,k;

    for(j=1;j<n;j++)

        {

        temp=a[j];

        i=j-1;

        while(i>=0&&a[i]>temp)

            {

            a[i+1]=a[i];

            i--;

              for(k=0;k<n;k++)

                  cout<<a[k]<<" ";

             cout<<endl;

        }

        a[i+1]=temp;

       

    }

      for(k=0;k<n;k++)

                  cout<<a[k]<<" ";

}

int main(void) {

    int n;

    cin>>n;

    int a[n], i;

    for(i = 0; i < n; i++) {

        cin>>a[i];

    }

    insertionSort(n,a);

    return 0;

}

Analysis of the solution provided:

The above code did the sorting in decreasing order from right to left sorting.

Inorder to do it it from right to left sorting. It could be solved as follows:

#include<iostream>

using namespace std;

void insertionSort(int n, int *a) {

 int temp,i,j,k;

    for(i=1;i<n;i++)

        {

        temp=a[i];

        j=i-1;

        while(j>=0&&a[j]<temp)

            {

            a[j+1]=a[j];

            j--;

              for(k=0;k<n;k++)

                  cout<<a[k]<<" ";

             cout<<endl;

        }

        a[j+1]=temp;

       

    }

      for(k=0;k<n;k++)

                  cout<<a[k]<<" ";

}

int main(void) {

    int n;

    cin>>n;

    int a[n], i;

    for(i = 0; i < n; i++) {

        cin>>a[i];

    }

 

    insertionSort(n,a);

    return 0;

}

Input (stdin)

5

2 4 6 8 3

 

Your Output (stdout)

2 2 6 8 3

4 2 2 8 3

4 4 2 8 3

6 4 2 2 3

6 4 4 2 3

6 6 4 2 3

8 6 4 2 2

8 6 4 3 2

 

Comparative Study of Sorting Algorithms:

Conclusion:

The document is made fully for conceptual understanding of the topic, taken question from hacker rank and given the solution for further understanding of the topic rather than superfluous talk on algorithms. The logic of algorithm is crystal clear as the whole program revolves around it, resource.com images are also incorporated for the benefit of the reader. Moreover, the program is run and the output is displayed. I truly have left no stone unturned to explain the topic in depth.

Feel free to fork my github repo, raise issue and pull request if you solve the problem with the logic illustrated here your preferable language like java.

Follow me on github for the algorithms:

https://github.com/anwesha999/Basic_Algorithms/tree/master

Stay tuned with Techtud for more such concepts.

Contributor's Info

Created:
0Comment
Introduction to sorting

Introduction to Sorting 

Sorting is nothing but storage of data in sorted order, it can be in ascending or descending order. The term Sorting comes into picture with the term Searching. There are so many things in our real life that we need to search, like a particular record in database, roll numbers in merit list, a particular telephone number, any particular page in a book etc.

Sorting arranges data in a sequence which makes searching easier. Every record which is going to be sorted will contain one key. Based on the key the record will be sorted. For example, suppose we have a record of students, every such record will have the following data:

  • Name
  • Roll No.
  • Class
  • Age

Here Student roll no. can be taken as key for sorting the records in ascending or descending order.

Now suppose we have to search a Student with roll no. 25, we don't need to search the complete record we will simply search between the Students with roll no. between 20 to 30. 

Contributor's Info

Created:
0Comment