# Insertion Sort - Part 2

# Insertion Sort - Part 2

cdima + 5 comments Pretty badly described algorithm, needs a better description of the steps.

lk00100100 + 0 comments [deleted]lk00100100 + 6 comments You can sort of follow this GIFFY

https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif

- KD
krishna3317 + 0 comments Thanks it helped me

surya_palla1 + 0 comments thank u , it helped me.

- HL
dlgustlr45 + 0 comments Thank you very much!!

- ME
Lundii + 0 comments Thanks. Very helpful.

- KM
mohansai01234 + 0 comments thanks bro. it helped me a lot

wqian + 0 comments Thank you! It helped me!

sshivasurya + 1 comment https://github.com/shivasurya/cc150/blob/master/sorting/insertions%20sort/C%20lang/insertion.c

check this with algorithm description

wqian + 0 comments Wow, thank you for sharing! It helped me!

- LO
duniya_ke_neta + 1 comment [deleted]- A
alison_thaung + 0 comments Here's another, slightly condensed Python3 solution

s = int(input().strip()) ar = [int(temp) for temp in input().strip().split(' ')] def insertionSort(ar, i): new = sorted(ar[:i+1]) + ar[i+1:] return ' '.join(str(k) for k in new) for i in range(1, s): print(insertionSort(ar, i))

formiaczek + 3 comments agreed, it's a shame that it assumes some iterations that print the array even if nothing was moved, i.e.:

Input 6 1 4 3 5 6 2 Expected 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

And solutions like:

void insertion_sort(vector<int> values) { print_values(values); while(true) { auto what = std::adjacent_find(values.begin(), values.end(), std::greater<int>()); if(what == values.end()) { return; } auto last = what+1; auto v = *last; auto tmp = *last; auto where = std::lower_bound(values.begin(), what, v); for(auto x = last; x != where; --x) { auto prev = x-1; *x = *prev; } *where = tmp; print_values(values); } }

that are insertion sort, would print it only when it actually changed, i.e.:

Your Output (stdout) 1 4 3 5 6 2 1 3 4 5 6 2 1 2 3 4 5 6

- LN
BALYAM_muralidh2 + 0 comments static void insertionSort2(int n, int[] arr) { // Complete this function for(int k=0;k<arr.length-1;k++){ for(int i=0;i<arr.length-1;i++){ int key = arr[k+1]; if(i==k+1) break; if(arr[i]>key){ arr[k+1]=arr[i]; arr[i]=key; } } for(int i=0;i<arr.length;i++) { System.out.print(arr[i]+" "); } System.out.println(); } }

- A
atript + 0 comments i think the idea is that they can check whether you have implemented the algorithm right. that is more accurately tested when all iterations and exchanges are recorded.This is not about efficiency, its about learning.

facitoo + 0 comments dude! thats heck of a complex solution!

- AA
Octowl + 5 comments For those trying this in javaScript, remember that the input is an array of strings.

You need to map the elements to integers using:

`arr.map(function(x) { return parseInt(x, 10); });`

mohhasbias + 0 comments Thank you. that's exactly what i need to fix my submission. my solution was string based sorting.

hdennen + 0 comments arr.map(Number) works just as well. Still, this was my bug so good spot.

dtudury + 0 comments exactly this, saved me some frustration, thank you!

`arr.map(Number)`

or`arr.map(x => +x)`

are cuter though :)Drakontium + 0 comments [deleted]gksander93 + 0 comments Life saver.

vshantam + 6 comments Python 3 b=int(input()) a=[int(x) for x in input().strip().split(' ')] for i in range(1,len(a)): key=a[i] j=i-1 while j>=0 and a[j]>key: a[j+1]=a[j] j=j-1 a[j+1]=key print(*a)

Do let me know if there is more finer solution in python.

runcy + 1 comment loved the usage of *a. Learnt something new instead of using join()

SebastianNielsen + 2 comments You can't use join, the list doesn't contain strings but integers.

- MV
15533_mohanvamsi + 1 comment you can use join...

print(' '.join(str(i) for i in array))

- DB
davebrophy + 0 comments or

print(' '.join(map(str,array)))

vshantam + 0 comments it can be used because python provides str() functions which can convert interger to strings

vshantam + 1 comment I am glad you learned something new..Do let me know if i can help you with something.

runcy + 1 comment Awesome! and thanks for the help offered. What would be in your opinion are good resources to learn advanced python concepts and also get better at Data Structures and Algorithms?

vshantam + 1 comment In case of Algorithms and Data structures I would reccomend you to learn from "CLRS" and even i do the same its a very good book. In case of Advanced Python i suggest you to join online courses because it's a language the more you do the more you learn.

runcy + 0 comments Cool. Thanks! I seem to be on the right path then

- [U
[deleted] + 0 comments Insertion swapping

- MW
GeoMatt22 + 1 comment I did about the same, but using a sentinel at the front of the array:

n, amin = int(input()), -10**4 A = [2*amin] + list(map(int, input().split())) for j in range(2, n+1): i, a = j, A[j] while a < A[i-1]: A[i] = A[i-1] i -= 1 A[i] = a print(*A[1:])

vshantam + 0 comments Thanks,learned something new.

- LP
lan956 + 1 comment def insertion_sort(ar):

`for i in range(1, len(ar)): for j in range(i): if (ar[i]<ar[j]): k = ar[i] ar[i] = ar[j] ar[j] = k print(*ar)`

- SB
ace_dexter + 0 comments I think its bubble sort!

- LP
lan956 + 0 comments [deleted]

briancmpbll + 2 comments In the C++ code, why switch from vectors in Part 1 to C arrays in Part 2??

peterkirby + 1 comment [deleted]- PK
foxeed + 1 comment You missed the point of these challenges with this cheesy std::sort(). >:(

peterkirby + 0 comments That wasn't my intention at all. I was offering a possible explanation for the switch to C arrays, which was the question. Apparently I was misunderstood (practically in the opposite sense - I was suggesting we were to avoid using conveniences of the STL), so I removed it.

NiceBuddy + 0 comments @briancmpbll did you get the answer for this?

rshaghoulian + 3 comments ### Java solution - passes 100% of test cases

public static void insertionSortPart2(int[] array) { for (int i = 1; i < array.length; i++) { int j = i; int value = array[i]; while (j >= 1 && array[j-1] > value) { array[j] = array[j-1]; j--; } array[j] = value; printArray(array); } }

Full solution available in my HackerRank solutions.

Let me know if you have any questions.

adamchenwei + 1 comment Hey, converted your answer to JS, but it will only pass first 2 test, thought?

for (var i = 1; i < array.length; i++) { var j = i; var value = array[i]; while (j >= 1 && (array[j-1] > value)) { array[j] = array[j-1]; j--; } array[j] = value; console.log(array.join(' ')); }

rshaghoulian + 1 comment Looks identical. My full solution also prints a newline after each array. My best guess is to make sure the output looks like the expected output in the testcase.

- MB
tawriffic + 1 comment It might be sorting the numbers 'alphabetically' instead of 'numerically'....my JS code only passed the first two tests until I realised this. Need the array contents to be integers not string characters. So my array was looking like 2,20,23,26,3,4,5,52, 6 etc

rshaghoulian + 0 comments Nice find!

Vasu1819 + 1 comment Hi, I've written a similar code but it failed 3/5 test cases reason being error with ArrayOutOfBound exception. Can you please tell me what wrong did I do? Thanks.

for(int j=1;j<ar.length;j++){ int temp=ar[j]; int k = j-1; while(ar[k]>temp&&k>=0) { ar[k+1]=ar[k]; k--; } ar[k+1]=temp; printArray(ar); }

rshaghoulian + 1 comment What's the input of the test case that's failing?

Vasu1819 + 1 comment Test cases 1,2and4. Input of test case 1 being: 9 9 8 6 7 3 5 4 1 2

rshaghoulian + 1 comment Hi. The problem is with this line of your code:

while(ar[k]>temp&&k>=0)

It evaluates the expression inside the () from left to right. So it first tries to do ar[k], where k is -1 and it gets an Index Out of Bounds Exception. To fix it, you can change it to

while(k >= 0 && ar[k] > temp)

Now, it will check for k >= 0 first. If it's not greater than 0, the next expression (to the right of &&) will not evaluate.

This is called short circuit evaluation

Vasu1819 + 0 comments Man you are awesome. You made my day. I didn't know about this, thank you. Thank you so much :-)

- SM
RA1511003010711 + 1 comment is there any need to use "value"..? Can't we simply write array[j-1]>array[i] ..?

rshaghoulian + 0 comments You need to save array[i], since the while loop will be overwriting it.

- JW
rabbitfighter + 1 comment The JavaScript solutions are wrong, again. This is the third one I've found where the test cases are wrong. :(

ggorlen + 0 comments They seem to be working now.

function processData(input) { let arr = input.split("\n")[1].split(' ').map(Number); for (let i = 1, j = i; i < arr.length; j = ++i) { while (arr[j] < arr[j-1] && j) { let temp = arr[j-1]; arr[j-1] = arr[j]; arr[j--] = temp; } console.log(arr.join(' ')); } } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); });

- GS
gursimran16 + 1 comment #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n, x; cin >> n; vector <int> a; for(int i = 0; i < n; i++){ cin >> x; a.push_back(x); } for(int i = 1; i < n; i++){ int j = i - 1; while(a[j] > a[j+1]){ int temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; j--; } for(int i = 0; i < n; i++){ cout << a[i] << " "; } cout << endl; } return 0; }

b0kater + 0 comments No, you are not supposed to put the element into the sorted array until you find its final position.

Originally linked by someone else: https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif

marcos_sb + 4 comments Do not

*printf*in Java 8 or you will timeout...evancrutcher + 0 comments Thanks for this tip! Fixed my timeouts.

off99555 + 0 comments Try using BufferedWriter.

- KL
kangkanlahkar1 + 1 comment One can try this to print the entire array in a single line code.....

**System.out.println(Arrays.toString(ar).replace("[","").replace("]","").replace(",",""));**Balwinder1012 + 0 comments Thanks for tip

pranjalgururani + 1 comment import java.io.

*; import java.util.*;public class Solution {

`public static void insertionSortPart2(int[] ar) { for( int i = 1; i<ar.length; i++) { int unsorted = ar[i]; for( int j = i-1;j>=0; j-- ) { if(unsorted< ar[j]) ar[j+1] = ar[j]; else if (ar[j] <= unsorted) { ar[j+1] = unsorted; break; } if( j == 0 && unsorted<ar[0]) ar[0] = unsorted; } printArray(ar); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); int[] ar = new int[s]; for(int i=0;i<s;i++){ ar[i]=in.nextInt(); } insertionSortPart2(ar); } private static void printArray(int[] ar) { for(int n: ar){ System.out.print(n+" "); } System.out.println("");`

} }

- KD
Kipdixit + 0 comments Thanks man!

deepak_yati_IITD + 0 comments please tell me what's the problem with this solution, only 2 cases are running

public static void insertionSortPart2(int[] ar) {

int i; for(i=1;ikey && j>=0){ ar[j+1]=ar[j]; j=j-1; } ar[j+1]=key; printArray(ar); } // The code for Input/Output is already provided }

Sort 236 Discussions, By:

Please Login in order to post a comment