Insertion Sort Part 2 Hackerrank problem solution

Insertion Sort Part 2 Hackerrank

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an element with just the first element – that is already “sorted” since there’s nothing to its left that is smaller.

In this challenge, don’t print every time you move an element. Instead, print the array after each iteration of the insertion-sort, i.e., whenever the next element is placed at its correct position.

Since the array composed of just the first element is already “sorted”, begin printing from the second element and on.

Input Format
There will be two lines of input:

s- the size of the array
ar- a list of numbers that makes up the array

Output Format
On each line, output the entire array at every iteration.

Constraints
1<=s<=1000 -10000<=x<=10000 x{arr} Sample Input

6
1 4 3 5 6 2

Sample Output

1 4 3 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 2 3 4 5 6


Explanation
Insertion Sort checks 4 first and doesn’t need to move it, so it just prints out the array. Next, 3 is inserted next to 1, and the array is printed out. This continues one element at a time until the entire array is sorted.

Task
The method insertionSort takes in one parameter: ar, an unsorted array. Use an Insertion Sort Algorithm to sort the entire array.

Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
void insertionSort(int ar_size, int *  ar) {
int i,j,k,v; 
    for(i=1;i<=ar_size-1;i++) { 
        v = ar[i];
            j = i;
        while(ar[j-1]>v && j>=1) {
            ar[j] = ar[j-1];
            j--; 
        } 
        ar[j] = v;
        k = 0;
        while(k < ar_size)
                printf("%d\t", ar[k++]);
        printf("\n"); 
    }

}
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;
}
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();
        }
        for(int i=1;i<s;i++)
        {
            int temp=ar[i];
            for(int j=i-1;j>=0 && temp<ar[j];j--)
            {
                ar[j+1]=ar[j];
                ar[j]=temp;
            }
            for(int j=0;j<s;j++)
                System.out.print(ar[j]+" ");
            System.out.println();
        }
    }
}
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

/* Head ends here */

void insertionSort(vector <int>  ar) {
  int size = ar.size();
  for(int tmp_size = 2; tmp_size<=size; tmp_size++) {
    int num = ar[tmp_size-1], i;
    for(i=tmp_size-2; ar[i]>num && i>=0; i--) {
      ar[i+1] = ar[i];
      //for(int j=0; j<size; j++)
        //cout << ar[j] << " ";
      //cout << endl;
    }
    ar[i+1] = num;
    for(int j=0; j<size; j++)
      cout << ar[j] << " ";
    cout << endl;
  }
}


/* 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;
}
#!/bin/python

# Head ends here
def printArray(a):
	x=""
	for number in a:
		x += str(number) + " "
	print x

def insertionSort(a):    
	for i in xrange(0, len(a)):
		j = i;
		while (j > 0 and a[j] < a[j-1]):
			temp = a[j];
			a[j] = a[j-1];
			a[j-1] = temp;
			j -= 1;
		if (i != 0): printArray(a)

# Tail starts here

m = input()
ar = [int(i) for i in raw_input().strip().split()]
insertionSort(ar)

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.