cdima Pretty badly described algorithm, needs a better description of the steps.
lk00100100 [deleted]lk00100100 You can sort of follow this GIFFY
https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif
krishna3317 Thanks it helped me
surya_palla1 thank u , it helped me.
dlgustlr45 Thank you very much!!
Lundii Thanks. Very helpful.
mohansai01234 thanks bro. it helped me a lot
wqian Thank you! It helped me!
arpit_vaish89 Thank you , helped a lot!
adamxtokyo Thanks, that helped a lot. Here's my Javascript implementation of that gif lol =P
function insertionSort2 (n, arr) { let storage for (let i = 1; i < n; i++) { storage = arr.splice(i, 1)[0] for (let j = i; j >= 0; j--) { if (storage > arr[j-1] || j === 0) { arr.splice(j, 0, storage) break } } console.log(arr.join(' ')) } }
yaroverg The GIFY was great
yashdeepagarwal Thank you. Helped alot!
sshivasurya https://github.com/shivasurya/cc150/blob/master/sorting/insertions%20sort/C%20lang/insertion.c
check this with algorithm description
wqian Wow, thank you for sharing! It helped me!
duniya_ke_neta [deleted]alison_thaung 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))
kerryjones21 Using an in-built sort function defeats the purpose of learning sorting algorithms...
formiaczek 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
BALYAM_muralidh2 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(); } }
pheonixevolution thanks it helped me !
atript 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 dude! thats heck of a complex solution!
billchenxi I agreed, why do we have to print out in that weird way???
darmuneeb322 The problem seems to be designed in a very bad way.But after finally solving it you kindof get the idea what insertion sort does at every step.
Octowl 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 Thank you. that's exactly what i need to fix my submission. my solution was string based sorting.
hdennen arr.map(Number) works just as well. Still, this was my bug so good spot.
dtudury exactly this, saved me some frustration, thank you!
arr.map(Number)orarr.map(x => +x)are cuter though :)
Drakontium [deleted]
gksander93 Life saver.
vshantam 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 loved the usage of *a. Learnt something new instead of using join()
SebastianNielsen You can't use join, the list doesn't contain strings but integers.
15533_mohanvamsi you can use join...
print(' '.join(str(i) for i in array))
davebrophy or
print(' '.join(map(str,array)))
vshantam it can be used because python provides str() functions which can convert interger to strings
vshantam I am glad you learned something new..Do let me know if i can help you with something.
runcy 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 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 Cool. Thanks! I seem to be on the right path then
[deleted] Insertion swapping
lan956 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)ace_dexter I think its bubble sort!
lan956 [deleted]Ramya_Vadigineni [deleted]
briancmpbll In the C++ code, why switch from vectors in Part 1 to C arrays in Part 2??
peterkirby [deleted]foxeed You missed the point of these challenges with this cheesy std::sort(). >:(
peterkirby 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 @briancmpbll did you get the answer for this?
RodneyShag 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 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(' ')); }
RodneyShag 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.
tawriffic 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
RodneyShag Nice find!
Vasu1819 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); }
RodneyShag What's the input of the test case that's failing?
Vasu1819 Test cases 1,2and4. Input of test case 1 being: 9 9 8 6 7 3 5 4 1 2
RodneyShag 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 Man you are awesome. You made my day. I didn't know about this, thank you. Thank you so much :-)
tripathi_shubha1 thanku so much !!
RA1511003010711 is there any need to use "value"..? Can't we simply write array[j-1]>array[i] ..?
RodneyShag You need to save array[i], since the while loop will be overwriting it.
rabbitfighter The JavaScript solutions are wrong, again. This is the third one I've found where the test cases are wrong. :(
ggorlen 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); });
gursimran16 #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 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 Do not printf in Java 8 or you will timeout...
evancrutcher Thanks for this tip! Fixed my timeouts.
off99555 Try using BufferedWriter.
kangkanlahkar1 One can try this to print the entire array in a single line code.....
System.out.println(Arrays.toString(ar).replace("[","").replace("]","").replace(",",""));
Balwinder1012 Thanks for tip
vldvel Simple JavaScript solution
arr.reduce((p,c,i) => { if (i === 0) return p; if (c < p.curr[i - 1]) { p.curr.splice(i, 1); p.curr.splice(p.curr.findIndex((e) => e > c), 0, c); } p.answer.push(p.curr.join(' ')); return p; }, {curr: [...arr], answer: []}).answer.join('\n');
pratheep_my Javascript solution;
for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (arr[j] > arr[i]) { const temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } process.stdout.write(arr.join(' ') + '\n'); }
Sort 258 Discussions, By:
Please Login in order to post a comment