I hear you guys are getting musty at home. I’d like something fresh. Focus and make the time go by faster!

Here’s the sorting process and gifs from the Rookie tutorial:

First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.

Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.

Repeat until all elements are sorted.

Let’s get this straight. The main logic for selection sort is:

  1. The loop first specifies a number, usually the first number
  2. The inner loop then compares the number specified in the outer loop to the number on the right side one by one, recording the smallest number on the right side
  3. The left is the sorted element, so the comparison in the inner loop is that the specified number in the outer loop is constantly compared to the right element
  4. In the inner loop, every time it finds a number smaller than the specified number in the outer loop, it is recorded, and the number recorded at the end of the loop is the smallest number on the right
  5. After the end of the inner loop, the specified number of the outer loop will be swapped with the minimum number on the right obtained by the inner loop
  6. And so on until the outer loop ends

Now there is a set of elements that need to be sorted:

[7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11]
Copy the code

The first number with subscript 0, 7, is specified by the logical loop that selects the sort, and the for loop starts with the element with subscript 0. The code appears as follows:

for i in0.. vectors.len() {}Copy the code

The for loop starts with the first number with subscript 0, 7. In the inner loop, the specified number in the outer loop is compared with the number on the right [21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11] one by one. When the specified number in the outer loop is less than the element on the left, the minimum value is recorded. At the end of the inner loop, vectors[I] and Vectors [j] swap places. The minimum number of epicycle is -1, so the element group becomes:

[-1, 21, 9, 13, 109, 9, 2, 50, 33, 7, 20, 11]

Enter the next outer loop and specify the second number 21 with subscript 1. The inner loop compares the outer number one by one with the right [9, 13, 109, 9, 2, 50, 33, -1, 20, 11]. When the inner loop is complete, the vectors[I] and [j] switch places. The minimum number of epicycle is 2, so the element group becomes:

[-1, 2, 21, 13, 109, 9, 9, 50, 33, 7, 20, 11]

By analogy, the final result of ordering elements is:

[-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109]
Copy the code

Concrete code implementation

First define a set of elements and print:

fn main() {
    letmut vectors = vec! [7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11]; println! ("vectors: {:? }", vectors);
}
Copy the code

Then define the sort method:

fn insert_sort(vectors: &mut Vec<i32>) -> &Vec<i32>{
		vectors
}
Copy the code

The outer loop of the sorting method is the for loop:

fn insert_sort(vectors: &mut Vec<i32>) -> &Vec<i32>{
		for i in0.. vectors.len(){
        
    }
		vectors
}
Copy the code

Here index represents the subscript of the minimum value:

fn insert_sort(vectors: &mut Vec<i32>) -> &Vec<i32>{
		for i in0.. vectors.len() {let mut index = i;
    }
		vectors
}
Copy the code

In the inner loop, the specified number in the outer loop is compared with the number on the right side one by one. When the specified number in the outer loop is less than the right element, the subscript of the right element is recorded, otherwise it does not move.

For j in I +1.. Vectors.len() and Vectors [j] < vectors[index] indicate;

The index can be swapped, so that when the inner for loop ends, index must be the index of the small element on the right;

C = a, a = b, b = c, c = a, a = b, b = c The code is as follows

fn selection_sort(vectors: &mut Vec<i32>) -> &Vec<i32>{
    for i in0.. vectors.len(){// Find the smallest element in the unsorted element, that is, the smallest element in [I, n)let mut index = i;
        for j ini+1.. vectors.len() {ifvectors[j] < vectors[index]{ index = j; }}let middle = vectors[index];
        vectors[index] = vectors[i];
        vectors[i] = middle;
    }
    vectors
}
Copy the code

Test of theory

The above theory seems reasonable and convincing, but is it true?

We can print the number of rounds, the minimum, and the current group of elements for each round of program execution. Add the following code to the print statement:

fn selection_sort(vectors: &mut Vec<i32>) -> &Vec<i32>{
    for i in0.. vectors.len(){// Find the smallest element in the unsorted element, that is, the smallest element in [I, n)let mut index = i;
        for j ini+1.. vectors.len() {ifvectors[j] < vectors[index]{ index = j; } } println! ("Now for round {}, min: {}, vectors: {:? }", i, vectors[index], vectors);
        let middle = vectors[index];
        vectors[index] = vectors[i];
        vectors[i] = middle;
    }
    vectors
}
Copy the code

After the code is run, the printed result is as follows:

Vectors: [7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11] [-1, 21, 9, 13, 109, 9, 2, 50, 33, 7, 20, 11] Now for round 2, min: 7, Vectors: [-1, 2, 9, 13, 109, 9, 21, 50, 33, 7, 20, 11] Now for round 3, min: 9, Vectors: [-1, 2, 7, 13, 109, 9, 21, 50, 33, 9, 20, 11] Now for round 4, min: 9, Vectors: [-1, 2, 7, 9, 109, 13, 21, 50, 33, 9, 20, 11] Now for round 5, min: 11, Vectors: [-1, 2, 7, 9, 9, 13, 21, 50, 33, 109, 20, 11] Now for round 6, min: 13, Vectors: [-1, 2, 7, 9, 9, 11, 21, 50, 33, 109, 20, 13] Now for round 7, min: 20, Vectors: [-1, 2, 7, 9, 9, 11, 13, 50, 33, 109, 20, 21] Now for round 8, min: 21, Vectors: [-1, 2, 7, 9, 9, 11, 13, 20, 33, 109, 50, 21] Now for round 9, min: 33, Vectors: [-1, 2, 7, 9, 9, 11, 13, 20, 21, 109, 50, 33] Now for round 10, min: 50, Vectors: [-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109] Now for round 11, min: 109, Vectors: [-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109]Copy the code

It can be seen that the description in the theoretical part is correct, that is, the minimum value in the right element is exchanged with the position of the element in the current turn in each turn.

The complete Rust selection sort code is as follows:

Rust code repository address github.com/asyncins/ac…