GIF introduces sorting algorithm selection sorting

This is the fourth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

concept

First, take a look at wikipedia’s definition of selection sorting:

Selection sort is a simple and intuitive sorting algorithm. It works as follows: first, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, the search continues for the smallest (large) element from the remaining unsorted elements and places it at the end of the sorted sequence. And so on until all the elements are sorted.

In summary, a sorting process of sorting selection is as follows: there are two sequences, sorted and unsorted, and the smallest element (arr[I]) found in the unsorted sequence is exchanged with the element arr[j] corresponding to the index value of the length of the sorted sequence (j).

A picture is worth a thousand words! Next, the author will use a GIF to describe the sorting process of selection sorting, assuming that the array to be sorted is arr = [24,8,3,15,36].

First order

• Sorted sequence:[]
• Unsorted sequence:,8,3,15,36 [24]
• The smallest element 3 (index 2) is found in the uncollated sequence, and the collated sequence has a length of 0arr[2] 和 arr[0]If I switch positions, I get,8,24,15,36 [3]

Second order

• Sorted sequence:[3]
• Unsorted sequence:,24,15,36 [8]
• The smallest element 8 (index value 1) is found in the uncollated sequence. The collated sequence is of length 1, the index value is the same, and no exchange is required,8,24,15,36 [3]

Third order

• Sorted sequence:[3]
• Unsorted sequence:,15,36 [24]
• The minimum element 15 (index 3) is found in the unsorted sequence, and the sorted sequence has length 2,arr[3] 和 arr[2]If I swap, I get zero,8,15,24,36 [3]

Fourth order

• Sorted sequence:,8,15 [3]
• Unsorted sequence:4 [24]
• The remaining two elements are already ordered, so there is no need to switch positions, and the final result is,8,15,24,36 [3]

JavaScript code implementation

function selectionSort(arr) {
    const len = arr.length;
    // Save the index of the lowest value in a sort
    let minIndex;
    let temp;
    for (const i = 0; i < len - 1; i++) {
        minIndex = i;
        for (const j = i + 1; j < len; j++) {
            // Find the index with the smallest number
            if(arr[j] < arr[minIndex]) { minIndex = j; }}// Switch positions
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
Copy the code

Complexity and stability

The time complexity is the number of times the inner loop is executed, which is (n-1)+(n-2)+… Plus 1=n times n minus 1 over 2, so the time is O(n).

Select sort is an unstable sort. Suppose that the sequence to be sorted is ARR = [5,8,5,2,9]. In the first order of sorting arr[0] and ARR [3] are exchanged, then the relative order of the two 5’s in the original sequence is destroyed.

conclusion

Selection sort is a relatively simple and intuitive sorting algorithm, is also the author sorting algorithm in the second chapter, the follow-up will continue to update quick sort, heap sort, merge sort algorithm, please look forward to ~

Other sorting algorithms

• GIF introduces the sorting algorithm bubble sort