ilmash by far worst problem in terms of requirements. seriously, it's so counterintuitive to do it 'the wrong way' instead of just implementing plain insert sort with printout each time values are swapped
shashank21jHackerRank Admin @ilmash it's a great problem as it explains the essence of insertion sort.
In insertion sort you assume the array upto some i is sorted and then insert the ith element.Here's from wikipedia
for i = 1 to length(A) - 1 x = A[i] j = i while j > 0 and A[j-1] > x A[j] = A[j-1] j = j - 1 A[j] = xIn this challenge you are only performing the final iteration of i = n-1
Given a sorted list with an unsorted number V in the right-most cell, can you write some simple code to insert V into the array so it remains sorted?
And by printing each time you ensure that you have understood the swap properly :)
Good luck
ilmash @shashank21j I did this after I was back from work, but what I meant in my original comment was that the way it was worded was really confusing. Tried few approaches for this one final iteration and failed and only implementing standard insertion which I remembered from school did proper job. My idea is to deal with this that way: "Here, implement insert sort, print only when you insert an element", done, no confusion about it ;)
But again, maybe it's just me :D
murphyl337 No, it's not just you...(maybe it's just people who already knew the algorithm or who can implement pseudocode). This problem is an odd half-step in the right direction and could be easily fixed if there weren't such strange constraints on output and implementation (like most of the problems I've seen on this site).
marioluan Could not agree more with you =/.
adamjc No, it's a terrible problem as it is requiring you to solve the code in a particular (and to top it off, really bad!) way, which is annoying.
For example in JavaScript you would solve this really simply with Array.slice, but because this solution doesn't involve "shifting" elements around like it's the 1960s, it won't work.
Terrible problem, rethink it.
wanbo @adamjc, sorry for the trouble, this is just the tutorial, we just want people who are not familiar with insertion sort to be familiar with this algorithm. :) So please understand us, we do not just need people to sort the array. Learning is our goal, right?
Son_Of_Nun Yes, learning is good. But I think it would be much better to make the test requirements focus on the start and end states and then describe a possible solution in the problem description rather than forcing a certain (less than ideal) implementation via the test criteria.
ki_lemons I agree with @adamjc that it's not a good introductory insert sort problem just because of the counter intuitiveness.
For my language, javascript, it's just kind of silly and i think doesn't set up less experienced js devs for success in algorithms on this... thing you call hackerrank I don't want to call it something it is not.
sheep0x Calm down, bud. This is a practice problem, you know. It's not meant to be an open-ended challenge. In other words, we are trying to implement insertion sort using “the” insertion algorithm, or, at the very least, an algorithm that has the same performance.
In js, shifting requires a bunch of in-place modifications within one iteration, while
Array.slicerequires scanning/bsearching for the right index and creating two tmp arrays and concatenating them. I wouldn't call that efficient. Depending on your memory allocator, your algorithm might even run asymptotically slower than the already slow insertion sort.And it doesn't even make your code shorter... So why use it anyways?
I'm sorry but I have to downvote...
Omnikron13 I think part of the problem people are having is how strict the output requirements are. For example, when sorting '2 3 4 5 1', my first draft would output '2 3 4 1 5' rather than the expected '2 3 4 5 5', because my first thoughts on implementing the algorithm was to breaking it down into atomic steps of -swapping- values.
I had to pretty much entirely rewrite it so it would conform to your expected out, despite the fact that it performed perfectly.
earthbasetwo [deleted]
jjlearman Right, but copying ("shifting") turns out to be more efficient (one store rather than three).
Regardless, nobody these days needs to know how to do a sort; rather, we need to know how to pick the right sort for our purpose. No harm in teaching basic sorting, though!
Raquiba_Sultana [deleted]
ahmdsamir91 hello sir the o/p is correct but i still getting wrong answer
Aish07 there may be some test cases that couls have been left out
Tolani Sample testcases you can try to test if your code works well
- 2 4 6 8 6
- 2 4 6 8 1
- 2 4 6 8 5
- 2 4 6 8 3
You should find what's failing
avadhanimk thanks yeah got it
rollins_jackson I pass all the cases you listed yet I'm not passing in through hackerrank. Hmm..
#Javascript
kkesari1 same with me
inquisitive_ayaz I understood what you are trying to say, but only after looking the solution. I felt, this was very simple and I was trying complicate this whole thing.
ki_lemons Yes in javascript especially I find these algorithms to be a horrible pain, but other than frontend development and node I only know some C scripting and that is so much different in the way you structure these algorithms. I end up confusing myself quite often, (I'm also no genius hacker I'm like a toddler with these algorithms)
that being said I wish hackerrank would do a better job walking people form step 0, to step 0.01, to step 0.02, to step 0.03... and so on rather than skipping whole steps.
Especially for javascript and node with this streams setup I want a 12 page guide to explain what those in hackerrank are thinking behind this process. There is no textbook that tackles javascript algorithms to my knowledge even close to the hackerrank set up and it takes a long time to get comfortable in the system with no lead in.
when to use [], when to use new Array() and should I initialize with new Array(100) ? or a for loop or should I map an int of 100 (in my opinion such a horrible and crude solution.)
similarly to arrays strings in javascript, and hashes need to be explicitly covered I wonder if there is a JS algorithms style guide?
pivots when you don't have explicit memory control and using javascript's scoping is unique to say the least.
There is so much more to the integral parts of solving these algorithms but I think I covered some of the most obvious issues.
sheep0x (I apologize for making this post lengthy.)
To create an array: stick with
new Array(n). You want to spend time thinking about algorithms rather than implementation details, so stick with one way of doing things unless you see an obviously better way.There is no algorithm style guide. Style guides try to tell you to do everything the same way as others do; that's good for software engineering, but not OJs. Style guides restrict you and distract you from problem-solving. In fact, many competitive programmers completely ignore style guides. (I'm not saying style guides are bad, what I'm saying is that they're irrelevant on OJs. Some contestants do have pretty good styles, including a HackerRank user.)
What you really need is: 1. a good grasp of your language's core, and 2. algorithms, which are hardly ever language-specific.
You don't have to know everything about js, just know vars, ints, strs, arrays, objs as dictionaries, conditionals, for-loops, while-loops, functions, I/O, and you are good to go. Very, very few problems require OOP/FP/callback/closure/weird stuffs.
As you can see, none of these requires a style guide or an “Algorithms in Javascript” tutorial. Any js tutorial + any algorithm book should do. If you don't want to buy a book, this repo seems to be a good resource.
Once you get to a certain level, you may start thinking about code templates and implementation details, all kinds of language-specific stuffs, but you will know what to do by then.
-------------------- All technical stuffs are above ---------------------------------------- Everything below is higher level thoughts --------------------While algorithmic awareness may help us optimize our js, we can't deny the fact that scripting languages are not designed for algorithms.
The general principle of scripting languages is: let the programmer do whatever he thinks is comfortable, and the compiler/interpreter shall try to figure out how to make things fast. In case there's nothing they can do about it, we call this a tradeoff: faster coding at the cost of slower execution. Hardwares are constantly improving, and programmers' time is always more valuable than CPU time, so why bother?
But algorithm is an exception. When we study algorithms, all we want is speed (ok, I lied, but let's say 90% of the time we only care about speed). In other words, our goal defeats the purpose of scripting languages.
That said, if you want to practice algorithms without having to learn C/C++/Java/stuffs, I totally understand. I often use Ruby to rush through problemsets, too. Here are some tips I find useful, and I believe they apply to most scripting languages:
- Know how things work. Have an idea how GC, regex, etc work. Understand the magic of join, split, etc.
- Be completely aware of when and where a new object is created. Know how to avoid memory allocation and copying by using in-place modification, pass by reference, etc.
- Find the balance between convenience and performance. You may want to use an enumerator/generator to shorten your code, but the performance overhead could lead to a TLE.
- Try to think in C. While scripting languages tend to have good abstractions, they come at a cost. Are we using a hash when we can use a plain old array? Is it really a good idea to build a suffix array using builtin sort function?
- Try to be lazy. If your language gives you handy stuffs at relatively low overhead, go ahead and use it. E.g. if a C user tells you to use big integers, you might as well use py/rb's builtin bigint instead of hand-writing it.
- Consider investing some time to take a “real” C/C++/Java algorithm course, online or offline.
grublob [deleted]
ohaysama @shashank21j: i know it's been 2 years since you've made that comment but still i couldn't dicipher it. could anyone evaluate the big(0) of below code:
x = arr[n-1] for i in range(n-2): if arr[n-i-2]>x: arr[n-i-1]= arr[n-i-2] print(*arr, sep=' ') else: arr[n-i-1] = x print(*arr, sep=' ') break if arr[1] > x: if arr[0] >x: arr[1] = arr[0] print(*arr, sep=' ') arr[0]=x print(*arr, sep=' ') else: arr[1] = x print(*arr, sep=' ')
Mirrage hi, for i in range(n-2): //this for loop goes til n-2 so big Oh for this statement is O(n) // upperbound BUT you are also calling print(*arr, sep=' ') for every 'for' loop which is O(n) so its O(n2) in total Hope that helps
14341a05d6 i think its O(n)
antfx have to add my vote here for this being a silly problem. the final algo ends up being more complicated than a full insertion sort would have been just to meet the expected output. :(
coreyshort I'm not spending 5 hackos to download the test cases when input constraints are not consistent across different problems. But I have spent far too long trying to debug an algorithm that works to figure out why I broke every test case but number 1 or why test case 3 broke. Frustrating and a terrible use of my programming time.
kostapappas the tests are very good placed. They test the basics in the algorithm like the fridges and how your solution is handle them.
caf77 [deleted]
tanilcagdas When the unsorted item is smallest, you can get index out of bounds exception. Try that in the custom input.
noedadon [deleted]Tolani Sample testcases you can try to test if your code works well
- 2 4 6 8 6
- 2 4 6 8 1
- 2 4 6 8 5
- 2 4 6 8 3
You should find what's failing . Note: this is a self generated test case.
yschandra I must say these are exatly my thoughts, i dont even feel like implementing it!
alegionofgenius Agreed, such a pain in the ass and waste of time.
crackerplace The test case 2 is failing.Not sure what's the issue.Below is the output.Did anyone face the same issue.
2 3 4 5 6 7 8 9 10 10
2 3 4 5 6 7 8 9 9 10
2 3 4 5 6 7 8 8 9 10
2 3 4 5 6 7 7 8 9 10
2 3 4 5 6 6 7 8 9 10
2 3 4 5 5 6 7 8 9 10
2 3 4 4 5 6 7 8 9 10
2 3 3 4 5 6 7 8 9 10
2 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
dheerajHackerRank Admin Looks like you solved the challenge. Congrats.
Michael123 [deleted]lawless_war1ock what's with the test case two
bharath18aug what if your element to be inserted was smaller than your first?
louis_wang Good point. I corrected my condition for first element and passed test case 2. Thanks for you advice.
grishabh I have also same problem dont know what is wrong???? Any suggestion?
crackerplace The output that I posted above was from the test case that I downloaded and it is th eexpected output.I confused it to be my program's output.
The actual output of my program was wrong.You can print the output of your program by the run code option and verify if the same as expected output from the test case results.
wanbo Congrats, you have solved it.
nbsarda Yes, I am also facing same issue.. dont know what's wrong with o/p
wanbo @nbsarda, I have viewed your code carefully, and I also get correct result in my local machine, and then I run online by using custom test cases, I found difference result, so it is probably because of overflow problem. "if(a[i-2]>k)" When i is decrease for n - 1 times, i will be equal to 1, and a[i - 2] will be a[-1], here is the bug.
manikantnigam i am facing the same problem....that is the bug in the output
prashasth1994 yea same problem here
wanbo @prashasth1994, you have the similar overflow problem with "nbsarda". There maybe a bug in the 31th line. When you find your locally result and online result get same answer but get still get WA, run it online, and find if there is a overflow bug.
franzee Same here, having the same out put but the test case is failing
MZhao14 I'm also running into this problem! I used 5 hackos to check why my test case #2 was failing. Here's the input: (10) 2 3 4 5 6 7 8 9 10 1 and here's my output: 2 3 4 5 6 7 8 9 10 10 2 3 4 5 6 7 8 9 9 10 2 3 4 5 6 7 8 8 9 10 2 3 4 5 6 7 7 8 9 10 2 3 4 5 6 6 7 8 9 10 2 3 4 5 5 6 7 8 9 10 2 3 4 4 5 6 7 8 9 10 2 3 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Marcolac Hi, I had the same issue and I figured it out. Your output should be:
2 3 4 5 6 7 8 9 10 10
2 3 4 5 6 7 8 9 9 10
2 3 4 5 6 7 8 8 9 10
2 3 4 5 6 7 7 8 9 10
2 3 4 5 6 6 7 8 9 10
2 3 4 5 5 6 7 8 9 10
2 3 4 4 5 6 7 8 9 10
2 3 3 4 5 6 7 8 9 10
2 2 3 4 5 6 7 8 9 10 # You are missing that line
1 2 3 4 5 6 7 8 9 10Hope it helps !
rjshukla I am not missing that line !! What is problem ?
2 3 4 5 6 7 8 9 10 10
2 3 4 5 6 7 8 9 9 10
2 3 4 5 6 7 8 8 9 10
2 3 4 5 6 7 7 8 9 10
2 3 4 5 6 6 7 8 9 10
2 3 4 5 5 6 7 8 9 10
2 3 4 4 5 6 7 8 9 10
2 3 3 4 5 6 7 8 9 10
2 2 3 4 5 6 7 8 9 10 # here is that line
1 2 3 4 5 6 7 8 9 10smahmood come on guys. simple. if the element at the end is the smallest element, ie has to be shifted all the way left, you have to perform the last check individually outside the loop, something like if (ar[0] > val){ ar[0] = val; printArray(ar); }
souravsachdeva thank you
purus20179 sahiiiiiiiiiiii
RajeshTK Thanks, That solved the problem.
athar_mustafa Thanks, this line was missing, gr8 help
humoyun_ahmad n=int(input()) arr=[int(x) for x in input().split()] def insertion_sort(arr): e=arr[len(arr)-1] ar=arr[0:len(arr)-1] l=len(ar) last=l-1 parr=[] while last>-1: # 2 4 6 8 tmp=ar[last] if tmp<e: break parr=ar[0:last]+[tmp]+ar[last:l] print (" ".join(str(s) for s in parr)) last=last-1 parr[last+1]=e print (" ".join(str(s) for s in parr)) insertion_sort(arr)
gruberator [deleted]
kenskyfish If you examine the output of the test case carefully, you'll find trailing spaces on the first 9 lines of output, but none of the last line. I suspect that's it - the test case itself is flawed.
gastonmancini The same here
rahulkumar15007 why 10 is reapeating again.
RajeshTK I too faced the same issue. Compared the input and output, everything is same, still its failing while submitting.
weihsuanchou I encountered same issue, but it was only because the input test cases.
I solved it by converting the each element to integer
let ary = str.split("\n")[1].split(' ').map(function(item) { return parseInt(item, 10); })
or simply use someArry.map(Number)
Sridhar_CR This occured to me because you gave a condition i > 0;
velraam I know this is too late. But, I faced the same issue. Only the second test case failed i.e., the element to be inserted is less than the first element of the array.
princepatrickan1 I think the problem you are facing would be a runtime error,which occured to me as well,
while**(j>=0 &&temp<ar[j])**{ //Since I had initially checked whether temp<ar[j] I had faced a runtimeerror.**temp<ar[j]&&j>=0)**but upon changing to the above order it got resolved. ar[j+1]=ar[j]; j--; printArray(ar); }
Now the runtime error got resolved
RajShukla I too got stuck in this test case... what is problem
k_kajdanski solving the problem - 5 minutes
printing to output the way author wanted - 55 minutes
shubham_sharma14 perhaps this problem is tough for those who know insertion sort !!!!
;p
SuperGogeta It's a bit of an hassle yes, but I knew insertion sort and could complete it in a few mins. Forget all knowledge that you have and code according to what's asked, think of it as some stupid sort and match the output logic and keep array index within bounds and we are done lol.
alexermashev Stupid problem
svkumar The test case 2 is failing for me as well ? 2 3 4 5 6 7 8 9 10 10 2 3 4 5 6 7 8 9 9 10 2 3 4 5 6 7 8 8 9 10 2 3 4 5 6 7 7 8 9 10 2 3 4 5 6 6 7 8 9 10 2 3 4 5 5 6 7 8 9 10 2 3 4 4 5 6 7 8 9 10 2 3 3 4 5 6 7 8 9 10 2 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
carnid You most likely check for the previous value in the array to check if it's bigger than the sorted value before inserting it where you are. Test case #2 however goes all the way to ar[0], so when you check for ar[0-1], it crashes. I solved it by checking if i==0 || ar[i-1] for insertion.
harvardisawesome i had the excact same problem, but it was not failing or giving an array out of bounds error(i am using java). but i will try your solution.
KManiKumarReddy Exactly same problem I have. It shows the correct output when I download test case and run it. But still, it shows wrong answer!
AlexPP int N = ar.size(); int i,j; int value; for(i=1;i<N;i++) { value=ar[i]; j=i-1; while(j>0 && value<ar[j]) { ar[j+1]=ar[j]; j=j-1; for(int k=0;k<N;k++) { printf("%d",ar[k]); printf(" "); } cout<<endl; } ar[j+1]=value; } for(j=0;j<N;j++) { printf("%d",ar[j]); printf(" "); }
avinash28196 it should be while(j>=0 ...)
billchenxi Test case 2 not working!
A1EKo Python 3:
import sys def insertionSort1(n, arr): target = arr[-1] idx = n-2 while (target < arr[idx]) and (idx >= 0): arr[idx+1] = arr[idx] print(' '.join(map(str, arr))) idx -= 1 arr[idx+1] = target print(' '.join(map(str, arr))) if __name__ == "__main__": n = int(input().strip()) arr = list(map(int, input().strip().split(' '))) insertionSort1(n, arr)
pavankalyan_93 It works perfectly
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; }
phyolintun87 -
-
static void insertionSort1(int n, int[] arr) { // Complete this function boolean isInserted=false; int unsortedval=-1; int unsortedindex=-1; for(int i=arr.length-1;i>0;i--){ if(arr[i]<arr[i-1]){ unsortedval=arr[i]; unsortedindex=i; break; } } for(int i=unsortedindex;i>=0;i--){ if(i>0 && arr[i-1]>=unsortedval){ arr[i]=arr[i-1]; }else{ arr[i]=unsortedval; isInserted=true; } for(int j=0;j<arr.length;j++){ System.out.print(arr[j]+" "); } System.out.print("\n"); if(isInserted) break; } }
alex_fr26 JS solution
function processData(input) { var input = input.split('\n'); var elements = input[1].split(' ') for(i = 0; i < elements.length; i++){ input[i] = +input[i]; } var i = elements.length - 2; var e = elements[elements.length - 1]; while (i >= 0 && e <= elements[i]){ elements[i+1] = elements[i]; console.log(elements.join(' ')); i--; } elements[i+1] = e; console.log(elements.join(' ')); }
kemal_bayer Could you explain this:
for(i = 0; i < elements.length; i++){ input[i] = +input[i]; }
alex_fr26 Thanks, it was useless part of the code. Maybe I was trying to convert String array elements into Number, but then I didn't know about array.map(Number) construction)
chadwalt Why use this?
var i = elements.length - 2;
Sort 431 Discussions, By:
Please Login in order to post a comment