Insertion or Selection Sort? (1 Viewer)

[honky tonk]

Firstly, I hate algorithms.

Secondly, how can you tell if the following is a selection or insertion sort? I understand the difference between the two (slightly), but I can't comprehend the algorithms. Here it is:

----------------------------------------------------------

BEGIN MAINPROGRAM
  INITIALISATION
  set First to first position
  set Last to last position
  set PositionOfNext to Last - 1
  END INITIALISATION
  WHILE PositionOfNext >= First
    set Next to data at PositionOfNext
    set Current to PositionOfNext
&nbsp;&nbsp;&nbsp;&nbsp;WHILE (Current < Last) AND (Next > data at (Current + 1))
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;increment Current
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set data at (Current - 1) to data at Current
&nbsp;&nbsp;&nbsp;&nbsp;ENDWHILE
&nbsp;&nbsp;&nbsp;&nbsp;set data at Current to Next
&nbsp;&nbsp;&nbsp;&nbsp;decrement PositionOfNext
&nbsp;&nbsp;ENDWHILE
END MAINPROGRAM

----------------------------------------------------------

This comes directly from the Excel Software Design and Development textbook, and it's a multiple choice question asking which sort the algorithm represents.

Can anyone help?

 

[SamD]

It's an Insertion sort!

- The outside loop iterates through each item from the second last one to the first one using the backwards counter PositionOfNext. (This doesn't help much as this is pretty much the case for all the three sorts.)

- The inside loop shuffles the data down until the correct position is found for the current data item, which is held in Next. By the way "increment Count" is wrong, it should read "increment Current".

- The shuffling is the give away, in an insertion sort there is no swapping, rather the data is moved down (or up) one postion at a time through the sorted part. In both selection and bubble sorts the line "set data at (Current-1) to data at Current" would be one line in a three line swap.

- The inside loop terminates with Current equal to the index of the position where the new data item should be inserted, hence the line "set data at Current to Next"

HTH
Sam

 

[honky tonk]

Thanks for that, it really had me thinking for a while.

Originally posted by SamD
By the way "increment Count" is wrong, it should read "increment Current".

Edited. Thanks again.

 

[TrickmA]

WHILE (Current < Last) AND (Next > data at (Current + 1))
increment Current [insertion]