Insertion Sort Part 1 Hackerrank problem solution

                          Insertion Sort Part 1 Hackerrank

Insertion Sort – Part 1

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

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

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

Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

Guideline: You can copy the value of e to a variable and consider its cell “empty”. Since this leaves an extra cell empty on the right, you can shift everything over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with .

Input Format
There will be two lines of input:

Size – the size of the array
Arr – the unsorted array of integers
Output Format
On each line, output the entire array every time an item is shifted in it.

Constraints
1<=Size<=1000
-10000<=e<=10000 e{Arr}

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

Explanation

3 is removed from the end of the array.
In the 1st line 8>3, so 8 is shifted one cell to the right.
In the 2nd line 6>3, so 6 is shifted one cell to the right.
In the 3rd line 4>3, so 4 is shifted one cell to the right.
In the 4th line 2<3, so 2 is placed at position .

Task

Complete the method insertionSort which takes in one parameter:

Arr – an array with the value in the right-most cell.

Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
void print(int ar_size, int *ar)
{
for (int i = 0; i< ar_size; i++)
{
     printf("%d ", ar[i]);   
}
printf("\n");

}

void insertionSort(int ar_size, int *  ar)
{
int small, sorted = 1, position;
//finding the small value 
for (int i = 0; i< ar_size; i++)
{
    if (ar[i] > ar[i+1])
    {
        small = ar[i+1]; 
        position = i; 
        break; 
    }
}

//sort the array and print
while (sorted != 0)
{

    ar[position + 1] = ar[position]; 
    print(ar_size, ar);
    if (small < ar[position - 1])
    {
        position--; 
        continue;
    }

    ar[position] = small;
    print(ar_size, ar);
    sorted = 0;     
}

}

int main(void) {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size, _ar);
   
   return 0;
}
n = int(raw_input())
test = raw_input()
a = test.split()
val = a[n-1]
for i in range(n-2,-2,-1):
    test=test.split()
    if i == -1:
        test[i+1] = val
        break
    elif int(test[i])>int(val):
        test[i+1]=test[i]
    
    else:
        test[i+1] = val
        break
    test = ' '.join(test)
    print test  
test = ' '.join(test)
print test

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

/* Head ends here */

void insertionSort(vector <int>  ar) {
    int n = ar.size();
    if(n==0)
        return;
    if(n==1)
        cout<<ar[n-1]<<endl;
    int curr = ar[n-1];
    int i=n-2;
    while(i>=0){
        if(ar[i]>=curr){
            ar[i+1]=ar[i];
        }
        else{
            ar[i+1]=curr;
            i=-1;
        }
        for(int j=0;j<n;j++)
            cout<<ar[j]<<" ";
        cout<<endl;
        if(i==0){
            ar[i]=curr;
            for(int j=0;j<n;j++)
                cout<<ar[j]<<" ";
            cout<<endl;
        }
        i--;
    }

}


/* Tail starts here */
int main() {
   vector <int>  _ar;
   int _ar_size;
cin >> _ar_size;
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
   int _ar_tmp;
   cin >> _ar_tmp;
   _ar.push_back(_ar_tmp); 
}

insertionSort(_ar);
   
   return 0;
}
import java.util.Scanner;

public class Solution {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       Scanner scan=new Scanner(System.in);
        int s=scan.nextInt();
        int ar[]=new int[s];
        boolean check=false;
        for(int i=0;i<s;i++)
        {
            ar[i]=scan.nextInt();
        }
        int var=ar[s-1];
        for(int i=s-2;i>=-1;i--)
        {
            if(i!=-1)
            {
            if(var<ar[i])
            {
                ar[i+1]=ar[i];
            }
            else
            {
                ar[i+1]=var;
                check=true;
            }
            }
            else
            {
                ar[0]=var;
            }
            for(int j=0;j<s;j++)
                System.out.print(ar[j]+" ");
            System.out.println();
            if(check)
                break;
        }
    }
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.