Differences between Selection and Insertion Sorts (1 Viewer)

[Scanorama]

G'Day everyone, Im confused with the differences between insertion and seleciton sorts, they look like idential to me, someone please explain to me what the differences between them, thanks in advance

 

[Beaky]

Ok I'll try my best to expliain each sort

SELECTION: Ok first get into your head there is a "sorted" part of the array.

Selections finds the lowest (or highest) value and puts it into the "sorted" part of the array (carried out by a linear search). Then it keeps doing this until the "sorted" part is = to the number of cells in the array

INSERTION: Basically does what the name says... Inserts values into different cells. It starts with a sorted part then finds the next value that needs to be there (with a linear search) and swaps it with the current value. So

4 9 1 8
4 9 8 1
9 8 4 1
9 8 4 1
9 8 4 1

SOrry this is confusing explination, i havnt studied this topic for a year, so its a bit dusty... SamD might be able to help

 

[fatmuscle]

for both sorts, there are 2 halves

a sorted half and an unsorted half

I think it's insertion sort that starts with 1 number in the sorted half, where as the selection sort starts with no numbers in the sorted half

by all means, corect me if i'm wrong

 

[SamD]

When performing both selection and insertion sorts within a single array, part of the array (commonly the LHS) holds the elements already sorted. The rest (usually the RHS) holds the items waiting to be sorted.

Selection sort (ascending):
1. Initially the sorted part is empty.
2. Perform a linear search for the smallest element in the unsorted part.
3. Swap this element with the first element in the unsorted part.
4. Increase the length of the sorted part by one. This causes the element just swapped in 3 to be part of the sorted part.
5. Repeat steps 2-5 until only a single element remains in the unsorted part. For our ascending example this element must be the largest, so we're finished.

Insertion sort (ascending):
1. Initially the sorted part is just the first element. Everything else is the unsorted part.
2. Grap a copy of the first element in the unsorted part. ie. hold it in a temp variable, as it will probably be overwritten during the shuffle.
3. Use a search strategy of the sorted part to determine its correct position. (Usually a linear search is used but as the data is sorted it's possible to use a binary search strategy)
4. Shuffle elements up to make a space for this element and shove it in this space.
5. Increase the length of the sorted part by one. NB. the shuffle in 4 will have made the sorted part one element longer than it was.
6. Repeat steps 2-5 until the unsorted part is empty.

IMHO when you look at algorithms for either of these sorts try to identify the bits that perform each of these steps. There's heaps of different ways to write the algorithms, but they all should somehow include the above steps.

Furthermore, you can easily modify the above steps to perform descending sorts or to use the RHS of the array as the sorted part. In fact, it's a worthwhile exercise to do this.

HTH
Sam

 

[Scanorama]

Thanks for the replies everyone, im still totally confused, lets talk about selection sort. I understand that one of the feature of selection sort is to find out the lowest value of the array and swap it with the first element of the unsorted part. However I can't find any part of the algorithm, can someone please point that out. Also after the first swap, I dont know how the algorithm contiune on to find the 2nd lowest value, I have read though all availiable texts I got, but still very very confused :S Can someone please answer my question, I will appreciate it.
Below is the algorithm:

BEGIN SelectionSort
Pass = 1
WHILE Pass < Number of Items
Count = Pass + 1
Minimum = Pass
WHILE Count <= Number of Items
IF Item(Count) < Item(Minimum) THEN
Minimum = Count
ENDIF
Count = Count + 1
ENDWHILE
Swap Item(Minimum) with Item(Pass)
Pass = Pass + 1
ENDWHILE
END SelectionSort

As i said before, i can't identify the bit which find the lowest value, as well as after it finds the 1st lowest value, how does it continue to find the 2nd value and so on. Thanks in advance

 

[SamD]

BEGIN SelectionSort

Pass = 1
(Initialise Pass, we use Pass to track the number of items we have correctly sorted; we're just about to sort the first item. Also Pass identifies the first item in the unsorted part of the array. In this algorithm the array is indexed from 1, so Pass is initailly set to one)

WHILE Pass < Number of Items
(Notice the condition is less than, so we loop 1 less than the number of items in the array, as the last item will be the largest)

Count = Pass + 1
Minimum = Pass
(These statements prepare Count and Minimum in preparation for the linear search. Minimum is intialised to the first index in the unsorted part, hence our search commences with the next item; the one with index Pass+1).

WHILE Count <= Number of Items
(Start the loop for the linear search)

IF Item(Count) < Item(Minimum) THEN
Minimum = Count
ENDIF
(See if the current item is less than the current smallest item, if it is then store its index in Minimum)

Count = Count + 1
ENDWHILE
(Increment the counter and complete the linear search loop. When the loop ends Minimum holds the index of the smallest item in the unsorted part of the arrray).

Swap Item(Minimum) with Item(Pass)
(Do the swap. Pass being the index of the first item in the unsorted part)

Pass = Pass + 1
(Increase the length of the sorted part by one. In this algorithm the sorted part is indexed from 1 to Pass-1, and the unsorted part is indexed from Pass to the number of items).

ENDWHILE
END SelectionSort

HTH
Sam

 

[Scanorama]

Thanks Sam, i finally understand it