Page 221 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Disadvantages of Insertion Sort are:
not effective for large numbers of sorting elements;
needs a large number of element shifts;

as the number of elements increases the performance of the program would be slow.
Self Assessment

State whether the following statements are true or false:

1. The insertion sort maintains the two sub-arrays within the same array.
2. Insertion sort is not efficient for small data sets.

13.2 Selection Sort

Selection sort, also called naive (selection) sort, is an in-place comparison sort. It may look
pretty similar to insertion sort, but it performs worse. It is a quite simple sorting algorithm, and
may perform better than more complicated algorithms in particular cases, for example in the
ones where the auxiliary memory is limited.
Like insertion sort, all the keys in the list for a selection sort are assumed to be in random order
before sorting, and there are two sublists of sorted and unsorted keys during the sorting process.
This is different from the insertion sort in that no extra variable is required to aid the comparisons,
and the movement of data is limited to one-to-one exchange.
Selection sort first finds the smallest number in the array and exchanges it with the element
from the first position, then it finds the second smallest number and exchanges it with the
element from the second position, and so on until the entire list is sorted.

The selection sort is demonstrated by sorting a list of integers in ascending order as in the
following figure.
Figure 13.2: Selection Sort

Source: http://ee.sjtu.edu.cn/po/Class-web/data-stucture/csc120ch9.pdf

214 LOVELY PROFESSIONAL UNIVERSITY