6.2 Sorting by direct selection

This technique is based on the following principles:

1. The element with the smallest key is selected.

2. It changes places with the first element a ₁ .

3. Then this process is repeated with the remaining n-1 elements, n-2 elements, etc. until one, the “biggest” element remains.

The algorithm is formulated as follows:

for i = 1 to n - 1 x = a (i) k = i for j = i + 1 to n if a (j) k = j x = a (k) endif next j a (k) = a (i) a (i) = x next i return

for i: = 1 to n - 1 do begin x: = a [i]; k: = i; for j: = i + 1 to n do if a [j] begin k: = j; x: = a [k]; end; a [k]: = a [i]; a [i]: = x; end;

Algorithm efficiency:

The number of comparisons of keys C obviously does not depend on the initial order of the keys. It can be said that in this sense the behavior of this method is less natural than the behavior of live inclusion. For C with any arrangement of keys, we have:

C = n (n-1) / 2

The order of the number of comparisons, therefore, O (n ² )

The number of permutations is minimal M _min = 3 (n - 1) in the case of initially ordered keys and maximally M _max = 3 (n - 1) + С, i.e. O (n ² ) order, if the keys were originally arranged in the reverse order.

In the worst case, sorting by direct choice gives the order of n ² , both for the number of comparisons and for the number of displacements.

When sorting by selecting [1] , the element with the smallest value is selected from the array and it is exchanged with the first element. Then, from the remaining n - 1 elements, the element with the smallest key is again selected and exchanged with the second element, and so on. These exchanges continue to the last two elements. For example, if you apply a selection method to the dcab array, each pass will look like the one below:

  Start dcab
 Pass 1 acdb
 Pass 2 abdc
 Pass 3 abcd

The following code demonstrates the simplest sorting by selection:

  / * Sort by selection.  * /
 void select (char * items, int count)
 {
   register int a, b, c;
   int exchange;
   char t;

   for (a = 0; a 

Unfortunately, as in bubble sorting, the outer loop is executed n - 1 times, and the inner loop - on average n / 2 times. Therefore, sorting by choice requires

1/2 ( n 2 - n )

comparisons. Thus, this is an algorithm of order n 2 , which is why it is considered too slow to sort a large number of elements. Despite the fact that the number of comparisons in bubble sorting and sorting through selection is the same, in the latter the number of exchanges is, on average, much smaller than in bubble sorting.

[1] It is also called sorting by selection and sorting by samples .