Лекция: Selection Sort

Selection sort is a basic sorting algorithm that works by making iterations, or passes, through the data being sorted. Each pass results in the placement of one element into its correct location. As a result, each subsequent pass has to inspect one fewer item than the previous pass.

Figure 1 An unsorted array

Figure 1 contains an unsorted array. Since this array contains eight elements, a selection sort must make seven passes to sort the data. Each pass places one element into the position that will result in a sorted array. The next two figures represent the first two passes, respectively. In each figure, the filled arrow indicates the position that the pass is seeking to fill. During each pass, the algorithm looks for the smallest remaining element. The pass ends with the algorithm swapping the smallest element into the position under consideration.

Figure 2 The first pass

After the first pass, the lowest element is placed into the first position of the array. The next pass, illustrated by Figure 3, places the second lowest element into the second position of the array.

Figure 3 The second pass

The selection sort algorithm always makes one fewer passes than the number of elements in the array. This is true even if the original array is already sorted. The algorithm has no mechanism to detect when the array is sorted, so it must make all required passes. A C++ implementation of the selection sort appears in Listing 1.