Insertion vs Selection Sort (1 Viewer)

[Jchips01]

Hi! Why does insertion push elements rather than swap each and why does selection swap elements rather than push. Or why don't they both push / swap? Is there a difference in pushing/swapping values

 

[dav53521]

Hi! Why does insertion push elements rather than swap each and why does selection swap elements rather than push. Or why don't they both push / swap? Is there a difference in pushing/swapping values

From what I understand the insertion sort does use swapping however, unlike selection sort, it does the swaps by "shuffling" the element into the correct position which means it basically does a comparison with the element next to it and if it's smaller or greater than the element next to it the two elements swap and this will repeat until the element is in the correct position.

Also I'm not too sure what you mean by push as typically you don't push values while sorting as it's used to add a value to a collection.

 

[brent012]

The selection sort grows a sorted portion of the array by finding the next smallest/largest element and swapping it with the first/last unsorted element. We don't need to touch the sorted portion of the array, just grow it by swapping out the element that's in the spot we want to use. This means we are iterating over the unsorted (shrinking) subset of the array.

The insertion sort instead grows the sorted portion of the array by finding a spot for the next unsorted element. This element may belong in the middle of the already sorted array, so it has to be inserted in the array and other elements will have to move up a position one by one to make space which is kind of inefficient. This means we are iterating over the sorted (growing) subset of the array, and may have to shift those elements around in each iteration.

The difference in approaches lends itself to the swapping and insertion respectively, you cant replace the mechanism without making the sort something entirely different really. You could insert for a selection sort, but it would be more expensive than the swapping. You can't swap for the insertion sort, as it would involve moving a sorted element back into the unsorted part of the array which undoes some of the existing progress.

it basically does a comparison with the element next to it and if it's smaller or greater than the element next to it the two elements swap and this will repeat until the element is in the correct position.

This sounds a bit more like bubble sort to me?

 

[dav53521]

This sounds a bit more like bubble sort to me?

It is, my brain decided to forget about the unsorted/sorted part of insertion sort .

 

[liamkk112]

Hi! Why does insertion push elements rather than swap each and why does selection swap elements rather than push. Or why don't they both push / swap? Is there a difference in pushing/swapping values

well selection just finds the min/max and swaps, then finds the second min/max and swaps etc. whereas insertion creates a sorted subarray inside the array, and then from here pretty much acts like a bubble sort that only sorts the element adjacent to the sorted subarray to grow the sorted subarray by one element each iteration. i've never heard the word "push" used to describe either, both involve swapping. they're just different approaches to sorting, theres no one way to do it, if they both pushed/swapped or wtv then might as well write the same algorithm again and again lol

 

[Jchips01]

Sorry, this is what I meant by pushing. I think it 'pushes' by incrementing/decrementating the index value of each unsorted element. Thank you for the answers

 

[brent012]

whereas insertion creates a sorted subarray inside the array, and then from here pretty much acts like a bubble sort that only sorts the element adjacent to the sorted subarray to grow the sorted subarray by one element each iteration.

My understanding was that it does not bubble up when moving the min/max, but instead shifts all elements to make room. But online there are resources showing both. So i'd probably go with whatever the HSC textbooks say and your teacher shows you, jchips' resource shows the shifting version.

Bubbling is a very distinctive part of bubble sort (just as selecting the min/max is a distinctive part of selection sort), so I'd be worried about using an explanation of insertion sort that involved bubbling tbh. But definitely the important part is that the insertion sort is moving the next unsorted element into the sorted subarray.

I think it 'pushes' by incrementing/decrementating the index value of each unsorted element.

In CompSci, push can have a very specific meaning for putting an element at the start of a stack or back of a queue. Insert is a bit more accurate here.

 

[liamkk112]

My understanding was that it does not bubble up when moving the min/max, but instead shifts all elements to make room. But online there are resources showing both. So i'd probably go with whatever the HSC textbooks say and your teacher shows you, jchips' resource shows the shifting version.

Bubbling is a very distinctive part of bubble sort (just as selecting the min/max is a distinctive part of selection sort), so I'd be worried about using an explanation of insertion sort that involved bubbling tbh. But definitely the important part is that the insertion sort is moving the next unsorted element into the sorted subarray.

yes it’s not exactly a bubble, however from memory i believe some resources used a bubble sort to add a new element to the sorted subarray by swapping all the elements, whereas in reality you should really be finding the correct index then inserting the new element there hence the name. the hsc course specs actually show the insertion pseudo code correctly however i don’t think i was marked down by just swapping the elements instead of inserting in papers, as long as u grow the sorted sub array one by one.