insertion vs selection sort (1 Viewer)

[SadCeliac]

how do I imagine them / what are their differences in how they function???

selection 'selects' the next largest value and swaps it with the item in it's correct position
insertion 'inserts' the next largest value by shuffling every other item over by one????

i need a visual explanation maybe lol please help

 

[SASH_06_X]

how do I imagine them / what are their differences in how they function???

selection 'selects' the next largest value and swaps it with the item in it's correct position
insertion 'inserts' the next largest value by shuffling every other item over by one????

i need a visual explanation maybe lol please help

bro theres literally less than 12 hours to paper 2 and here u are asking abt selection and insertion sorts-

 

[SASH_06_X]

anyway wait lemme try to explain since im sick of memoing quotes at the moment one sec

 

[SadCeliac]

anyway wait lemme try to explain since im sick of memoing quotes at the moment one sec

good stuff

bro theres literally less than 12 hours to paper 2 and here u are asking abt selection and insertion sorts-

no I just thought of it and saw @dav53521 was online lmaoo

 

[Sam14113]

how do I imagine them / what are their differences in how they function???

selection 'selects' the next largest value and swaps it with the item in it's correct position
insertion 'inserts' the next largest value by shuffling every other item over by one????

i need a visual explanation maybe lol please help

If a visualisation is what you need you're spoiled for choice on the internet.

From a brief amount of googling I think this is the best I've got for insertion and selection sort: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Note: The way NESA implements insertion sort is a little different (it 'shuffles' as you said rather than 'swaps') but the general idea is still very much the same and it should help you get a grasp of the main idea. To get a better understanding of NESA's implementation, I suggest you actually go through the code and sort 5 playing cards.

Also for advantages/disadvantages of each sort method this one is pretty good: https://www.toptal.com/developers/sorting-algorithms. However, start with the usfca one because you can much more easily see the workings of the sort.

This is what my favourite topic so happy to answer any more questions ... but preferably after English

 

[dav53521]

Well I have been summoned.
Anyway a selection sort grabs the largest element in the unsorted part of the array and places at the end of unsorted which is then turned into the beginning of sorted. For an insertion sort it grabs the last element of the unsorted part of the array and then shuffles it into the correct position within the sorted section so insertion doesn't grab the next largest element.

 

[SASH_06_X]

SELECTION SORT
- is a sorting algorithm that works by repeatedly selecting the smallest or largest element from the unsorted portion of the list to move it to the sorted portion of the list.

So basically in a selection sort, the input array is divided into two parts: sorted and unsorted part.
Then the algorithm repeatedly finds the minimum element in the unsorted part and swaps it with the leftmost element of the unsorted part, expanding the sorted part by one element.

For example if u look at this array: arr{} = {64, 25, 12, 22 and 11}
For the first position in the sorted array the while array has the index 0-4 sequentially. It is clear 11 is the lowest value, so replace 64 with 11. After one iteration 11 appears in the first position of the sorted list.

INSERTION SORT
is a sorting algorithm where the array is split into a sorted and unsorted part. Values from the unsorted part are placed at the correct position in the sorted part.

Example
arr{} = {12, 12, 13, 5, 6}
First pass
The first two elements are compared in the insertion sort.
12 is greater than 11 so 12 is not in the correct position. So swap 11 and 12.
So 11 is stored in a sorted sub array.

And so on.

The main difference between the two are that selection sort scans unsorted part to find Min element, while insertion scans sorted part to find the correct position to place the element. Selection sort requires fewer swaps than insertion but more comparisons.

Hope that clarified your question!!

Edit: OK ima head off to bed BTW @SadCeliac gl on paper 2 tomorrow!!!! That done and we'll be finished with English for good

 

[SadCeliac]

If a visualisation is what you need you're spoiled for choice on the internet.

From a brief amount of googling I think this is the best I've got for insertion and selection sort: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Note: The way NESA implements insertion sort is a little different (it 'shuffles' as you said rather than 'swaps') but the general idea is still very much the same and it should help you get a grasp of the main idea. To get a better understanding of NESA's implementation, I suggest you actually go through the code and sort 5 playing cards.

Also for advantages/disadvantages of each sort method this one is pretty good: https://www.toptal.com/developers/sorting-algorithms. However, start with the usfca one because you can much more easily see the workings of the sort.

This is what my favourite topic so happy to answer any more questions ... but preferably after English

THANK YOU! I'll have a more detailed look tomorrow

 

[Robert21]

I found the following videos quite helpful:

(insertion sort)

(selection)

(both plus some random ones)