Sort by selection

3 min


Hello. I wrote this article specifically to launch the course. “Algorithms and data structures” from OTUS.


Introduction

Array sorting is one of the first serious tasks studied in the classic course “Algorithms and Data Structures” of the discipline computer science. In this regard, tasks for writing sortings and related questions are often encountered in interviews as trainees or junior developers.

Formulation of the problem

Traditionally, it is worth starting the presentation of solutions to the problem with its formulation. Typically, the sorting task involves sorting an array of integers in ascending order. But in fact, this is some simplification. The algorithms described in this section can be used to order an array of any objects between which an order relationship is established (that is, about any two elements we can say: the first is greater than the second, the second is greater than the first, or they are equal). You can sort both ascending and descending. We will use the standard simplification.

Sort by selection

One of the simplest sortings is sorting by choice.

Algorithm description

Sorting the array by selection is as follows: the array is divided into two parts. One of the parts is called sorted, and the other is unsorted. The algorithm involves passing through the entire array so that the length of the sorted part becomes equal to the length of the entire array. Within each iteration, we find the minimum in the unsorted part of the array and swap this minimum with the first element of the unsorted part of the array. Then we increase the length of the sorted part of the array by one. An example of one iteration is presented below:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

Implementation

I suggest looking at the implementation of this algorithm in the C language:

void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        //ищем минимум
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}

Analysis

I propose to analyze this algorithm. The body of the inner loop itself is executed in O (1), that is, it does not depend on the size of the sorted array. This means that in order to understand the asymptotic behavior of the algorithm, it is necessary to calculate how many times this body is executed. At the first iteration of the outer loop, (n - 1) iterations of the inner loop take place. At the second iteration of the outer loop - (n - 2) iterations of the inner loop. Continuing this argument further, we come to the following:

$ T (n) = (n - 1) * O (1) + (n - 2) * O (1) + ... + O (1) = O ((n - 1) + (n - 2) + ... + 1) = O ((n - 1) * n / 2) = O (n ^ 2) $

In the process of computing, we first used the properties of O - notation, and then the formula to calculate the sum of the arithmetic progression.

For order, it is also necessary to evaluate the additional memory that is required to execute the algorithm. Everything is much simpler here: we allocated memory only for loop and variable counters - a buffer, which allows exchanging 2 elements of the array in places. Therefore:

$ M (n) = O (1) $

As a result of the analysis, we came to the conclusion that the time complexity of the algorithm depends on the size of the input array quadratically. Therefore, this sorting is classified as quadratic sortings. The result of the analysis does not depend on the content of the array: it is true in the best, worst and average cases.

It is also important to note that sorting by choice in such an implementation is sustainable. Let me remind you that sorting is called sustainableif during its execution the sequence of equal elements does not change. This property is not very important for such an educational task as sorting an array of numbers, but if we sorted out some more complex objects with an established order relation this could be important. We can consider a similar example sometime next time when we talk about bitwise sorting.

Two-sided selection sorting

Optimization of the algorithm implemented above may be of some interest: while passing through the unsorted part of the array, you can search for the maximum one along with the minimum element. Thus, after iteration, it is possible to reduce the unsorted part of the array not by one, but by two. Asymptotic improvement of the algorithm does not occur, but nevertheless, the speed of its execution can slightly increase, the number of comparisons also doubles.

Recursive sort by selection

As an exercise, you can try to write an algorithm not using a loop, but using recursion. In java, this might look like this:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

Summary

We examined one of the quadratic sortings: sorting by choice, looked at a stable implementation using a loop, recursion, and discussed the optimization of the algorithm using two-sided reduction of the unsorted part of the array. Sorting is exclusively educational and has not been widely used in practice.


If you want to learn more about the course, I invite everyone to free webinar, which will be held on July 10.



0 Comments

Leave a Reply