Clever Geek Handbook

Selection sort

Hello. I wrote this article specifically for the launch of the course "Algorithms and Data Structures" from OTUS.







Introduction



Sorting an array is one of the first serious problems studied in the classic course "Algorithms and Data Structures" of the computer science discipline. In this regard, the tasks of writing sorts and the corresponding questions are often encountered in interviews as an intern or junior developer.



Formulation of the problem



Traditionally, it is worth starting the presentation of solutions to the problem with its statement. Usually the sorting task involves ordering some array of integers in ascending order. But in fact, this is somewhat oversimplification. The algorithms described in this section can be used to order an array of any objects between which an ordering relationship is established (that is, for 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 in ascending and descending order. We'll use the standard simplification.



Selection sort



One of the simplest sorts is selection sort.



Algorithm Description



Sorting an array by selection is carried out as follows: the array is divided into two parts. One part is called sorted and the other unsorted. The algorithm assumes traversing 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 C: 



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 takes O (1), that is, it does not depend on the size of the array being sorted. This means that to understand the asymptotics of the algorithm, it is necessary to count how many times this body is executed. At the first iteration of the outer loop, there are (n - 1) iterations of the inner loop. On the second iteration of the outer loop - (n - 2) iterations of the inner loop. Continuing this reasoning 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(n2)





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



For order, it is also necessary to estimate the additional memory that is required to execute the algorithm. Everything is much simpler here: we allocated memory only for the loop counters and a variable - a buffer, which allows swapping 2 array elements. 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 belongs to the class of quadratic sorts . The result of the analysis does not depend on the content of the array: it is correct at best, worst, and on average.



It is also important to note that selection sorting is robust in this implementation . Let me remind you that sorting is called stable.if the order of the equal elements does not change during its execution. This property is not very important for such an educational task as sorting an array of numbers, but if we were sorting some more complex objects with an established ordering relation, it might be important. We can consider a similar example sometime the next time we talk about radix sorting.



Two-sided selection sort



Optimization of the algorithm implemented above may be of some interest: while walking through the unsorted part of the array, you can search for the maximum in parallel with the minimum element. Thus, after iteration, you can decrease the unsorted part of the array not by one, but by two. The algorithm does not improve asymptotically, but nevertheless, the speed of its execution may slightly increase, the number of comparisons also doubles.



Recursive selection sort



As an exercise, you can try to write an algorithm not using a loop, but using recursion. In java it 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 looked at one of the quadratic sorts: selection sort, looked at a stable implementation using a loop, recursion, discussed algorithm optimization by two-way reduction of the unsorted part of the array. Sorting is purely educational and has not found wide application in practice.





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





More articles:


All Articles