Select Sorting Algorithm

In order to sort the sequences with less data in ascending or descending order, we can consider using the selective sorting algorithm, whose corresponding time complexity is O(n2).

The idea of sorting the sequence containing n elements by sorting algorithm is to find the maximum or minimum value from the sequence to be sorted every time, and the search process is repeated n-1 times. For the maximum or minimum values found each time, they are placed in the appropriate position by exchanging the position of elements, and finally the whole sequence becomes an ordered sequence.

For example, we use the selective sorting algorithm to sort {14, 33, 27, 10, 35, 19, 42, 44} in ascending order. We need to go through the following steps:

1. Traverse the entire sequence to be sorted, find the minimum value 10 and exchange the position with the first element 14:

1. The sequence to be sorted becomes {33, 27, 14, 35, 19, 42, 44}, from which the minimum value 14 is found and the position is exchanged with 33:

1. The sequence to be sorted becomes {27, 33, 35, 19, 42, 44}, from which the minimum value 19 is found and the position is exchanged with 27:

1. The sequence to be sorted becomes {33, 35, 27, 42, 44}, from which the minimum value 27 is found and the position is exchanged with 33:

1. The sequence to be sorted becomes {35, 33, 42, 44}, from which the minimum value 33 is found and the position is exchanged with 35:

1. The sequence to be sorted becomes {35, 42, 44}, and the minimum value 35 is found. Its position does not need to be changed:

1. The sequence to be sorted becomes {42, 44}, and the minimum value 42 is found. Its position does not need to be changed:

For the sequence to be sorted containing n elements, only n-1 "minimum values" need to be found in the selection sorting algorithm, and the value of the last remaining elements must be the maximum. Thus, we get an ascending sequence {10, 14, 19, 27, 33, 35, 42, 44}.

The selective sorting algorithm can be regarded as an "improved version" of the bubble sorting algorithm. Compared with the latter, the selective sorting algorithm greatly reduces the operation of exchanging data storage locations.

Implementation of selective sorting algorithm

The following pseudo code describes the selection sorting algorithm:

selection_sort(list): //list is the sequence to be sorted
N < - length (list) / / record the number of elements in the sequence
For I < - 1 to n-1: / / traverse from the first element to the penultimate element
Min < - i / / the minimum initialization value is the ith element
For J < - i+1 to N: / / start traversing the sequence from the i+1 element
If list [J] < list [min]: / / find the minimum value in the sequence to be sorted
min = j
if min != i: / / if the position of the minimum value is not I, exchange the position of the minimum value and the ith element
swap list[min] , list[i]
return list

Combined with the pseudo code, the following is a C language program for realizing ascending sorting of {14, 33, 27, 10, 35, 19, 42, 44} using the selective sorting algorithm:

#include <stdio.h>
#define N 8 / / sets the number of elements in the sequence to be sorted
//list[N] is an array that stores the sequence to be sorted
void selection_sort(int list[N]) {
    int i, j;
    int min,temp;
    //Traverse from the first element to the penultimate element
    for (i = 0; i < N-1; i++) {
        min = i;   //Assume that the minimum value is the ith element in advance
        //Start traversing from the i+1 element to find the real minimum value
        for (j = i + 1; j < N; j++) {
            if (list[j] < list[min]) {
                min = j;
            }
        }
        //If the position of the minimum value is not i, exchange the position of the minimum value and the ith element
        if (min != j) {
            temp = list[min];
            list[min] = list[i];
            list[i] = temp;
        }
    }
}
int main() {
    int i;
    int list[N] = { 14,33,27,10,35,19,42,44 };
    //Select the sort sequence to be sorted
    selection_sort(list);
    //Outputs the elements in the sorted sequence
    for (i = 0; i < N; i++) {
        printf("%d ", list[i]);
    }
}

The following is a Java program that uses the selective sorting algorithm to sort {14, 33, 27, 10, 35, 19, 42, 44} in ascending order:

public class Demo {
    // list[N] is an array that stores the sequence to be sorted
    public static void selection_sort(int[] list) {
        int length = list.length;
        int i, j;
        // Traverse from the first element to the penultimate element
        for (i = 0; i < length - 1; i++) {
            int min = i; // Assume that the minimum value is the ith element in advance
            // Start traversing from the i+1 element to find the real minimum value
            for (j = i + 1; j < length; j++) {
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            // If the position of the minimum value is not i, exchange the position of the minimum value and the ith element
            if (min != j) {
                int temp = list[min];
                list[min] = list[i];
                list[i] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] list = { 14, 33, 27, 10, 35, 19, 42, 44 };
        selection_sort(list);
        // Output ordered sequence
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}

The following is a Python program that uses the selective sorting algorithm to sort {14, 33, 27, 10, 35, 19, 42, 44} in ascending order:

#Sequence to be sorted
list = [14,33,27,10,35,19,42,44]
def selection_sort():
    length = len(list)
    #Traverse from the first element to the penultimate element
    for i in range(length-1):
        min = i  #Assume that the minimum value is the ith element in advance
        #Start traversing from the i+1 element to find the real minimum value
        for j in range(i+1,length):
            if list[j] < list[min]:
                min = j
        #If the position of the minimum value is not i, exchange the position of the minimum value and the ith element
        if min != j:
            list[min],list[i] = list[i],list[min]
selection_sort()
# Output ordered sequence
for i in list:
    print(i,end=" ")

The output results of the above procedures are:

10 14 19 27 33 35 42 44