The writing process of Rust code is slightly different from that of other languages, because its compiler does not allow any unsafe writing methods, so the longest time spent in the code writing process is finding compilation errors. s reason. This also has advantages – after the code is written, the stability is greatly improved!
The following is the sorting definition and animation diagram from the novice tutorial:
Insertion sort (English: Insertion Sort) is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it.
Let’s take a look at it. The main logic of insertion sort is:
- The outer loop first specifies a number, usually the first number
- Then in the inner loop, the outer loop specified number is compared with the number on the left one by one, and according to the comparison result, the outer loop specified number is inserted into the left side of the inner loop number or remains unchanged.
- The left side is the sorted elements, so the comparison in the inner loop is to continuously compare the number specified in the outer loop with the elements on the left.
- When the number specified in the outer loop is less than the left element, the position is swapped, otherwise it does not move
- And so on until the outer loop ends
Now we have a set of elements that need to be sorted:
[7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11]
Specify the first number 7 in the logical outer loop of insertion sort. After selection, the for loop will loop from the element with index 1. The code behaves as:
for i in 1..vectors.len(){}
The first number 7 with index 0 is sorted, then the for loop starts from the second number 1 with index 1 strong>21Start. In the inner loop, compare the number specified by the outer loop with the number on the left [7] one by one. When the number specified by the outer loop is less than the left element, the positions are swapped. Otherwise, it does not move.
At this point, enter the next outer loop and specify the third number 9 with the subscript 2. In the inner loop, compare the number specified by the outer loop with the number on the left [7, 21] one by one. When the number specified by the outer loop is less than the left element 21, the positions are swapped and 7 is encountered. strong> Not moving. Then the element group becomes:
[7, 9, 21, 13, 109, 9, 2, 50, 33, -1, 20, 11]
At this point, enter the next outer loop and specify the fourth number 13 with the subscript 3. In the inner loop, compare the number specified by the outer loop with the number on the left [7, 9, 21] one by one. When the number specified by the outer loop is less than the left element 21, the positions are swapped and 9 is encountered. Stay still. Then the element group becomes:
[7, 9, 13, 21, 109, 9, 2, 50, 33, -1, 20, 11]
So on and so forth …
At this point, enter the Nth outer loop and specify the sixth number 9 with the subscript 5. In the inner loop, compare the number specified in the outer loop with the number on the left [7, 9, 13, 21, 109] one by one:
- When the number specified by the outer loop is less than the left element 109, the position is swapped;
- When the number specified by the outer loop is less than the left element 21, the position is swapped;
- When the number specified by the outer loop is less than the left element 13, the position is swapped;
Encounter9 motionless. Then the element group becomes:
[7, 9, 9, 13, 21, 109, 2, 50, 33, -1, 20, 11]
At this point, enter the Nth outer loop and specify the seventh number 2 with the subscript 6. In the inner loop, compare the specified number in the outer loop with the number on the left [7, 9, 9, 13, 21, 109] one by one:
- When the number specified by the outer loop is less than the left element 109, the position is swapped;
- When the number specified by the outer loop is less than the left element 21, the position is swapped;
- When the number specified by the outer loop is less than the left element 13, the position is swapped;
- When the number specified by the outer loop is less than the left element 9, the position is swapped;
- When the number specified by the outer loop is less than the left element 9, the position is swapped;
- When the number specified by the outer loop is less than the left element 7, the position is swapped;
Traverse to the left end of the element group. At this time, j is not greater than or equal to 0, and the inner loop ends. Then the element group becomes:
[2, 7, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11]
Before that, there are many elements to the left of 2, and it needs to compare and swap positions with these elements one by one. The position change process of number 2 is as follows:
[7, 9, 9, 13, 21, 2, 109, 50, 33, -1, 20, 11] [7, 9, 9, 13, 2, 21, 109, 50, 33, -1, 20, 11] [7, 9, 9, 2, 13, 21, 109, 50, 33, -1, 20, 11] [7, 9, 2, 9, 13, 21, 109, 50, 33, -1, 20, 11] [7, 2, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11] [2, 7, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11]
It can be seen from the process that in each round of the inner loop, the number 2 will move to the left until there is no number larger than 2 in front.
By analogy with this rule, the final result of element sorting is:
[-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109]
Specific code implementation
First define a set of elements and print:
fn main() {
let mut vectors = vec![7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11];
println!("vectors: {:?}", vectors);
}
Then define the sorting method:
fn insert_sort(vectors: & amp;mut Vec<i32>) -> & amp;Vec<i32>{
vectors
}
The outer loop of the sort method is a for loop:
fn insert_sort(vectors: & amp;mut Vec<i32>) -> & amp;Vec<i32>{
for i in 1..vectors.len(){
}
vectors
}
Here, the outer element is assigned to the variable variable current, and the subscript of the element on the left side of the inner loop is set:
fn insert_sort(vectors: & amp;mut Vec<i32>) -> & amp;Vec<i32>{
for i in 1..vectors.len(){
let mut current = vectors[i];
let mut j = i - 1;
}
vectors
}
In the inner loop, the number specified by the outer loop is compared with the number on the left one by one. When the number specified by the outer loop is less than the element on the left, the positions are swapped, otherwise it does not move.
Comparison with the left element is represented by j = i – 1, vectors[j];
Constantly comparing with the left element is represented by while j >= 0, j = j -1;
The comparison is represented by current < vectors[j];
You cannot exchange positions like a, b = b, a in Python. You can only use c = a, a = b, b = c to add a third number. The code is as follows
fn insert_sort(vectors: & amp;mut Vec<i32>) -> & amp;Vec<i32>{
for i in 1..vectors.len(){
let mut current = vectors[i];
let mut j = i - 1;
while j >= 0 & amp; & amp; current < vectors[j]{
let middle = vectors[j + 1];
vectors[j + 1] = vectors[j];
vectors[j] = middle;
j = j - 1;
}
}
vectors
}
However, if written like this, if the number specified in the outer loop is smaller than all the numbers on the left, it will not be compiled. For example, when the outer loop specifies a number of 2, it needs to be compared with all the numbers on the left until j = 0, but the last sentence in the while is j = j – 1, and j = -1 after running here. According to the normal running process, the program will enter the next inner loop of while j >= 0, but since j = -1, it will not enter the while loop body. There is no problem in writing this way in the Python language, but the Rust compiler does not allow it, so you need to add a control statement if j = 0 outside j = j – 1.
Verification of theory
The above theory seems reasonable and convincing, but is it correct?
Is it possible that the analysis is wrong?
Although the program is correct, what if the logic described is wrong?
We can observe the changes in element positions during loop comparison by printing the number current specified in the outer loop during program execution, the first number on the left side of the inner loop, and the element group vectors after each exchange of positions. The code with the print statement added is as follows:
fn insert_sort(vectors: & amp;mut Vec<i32>) -> & amp;Vec<i32>{
for i in 1..vectors.len(){
let mut current = vectors[i];
let mut j = i - 1;
println!("current vectors: {:?}", vectors);
println!("current: {} < vectors[j]: {}", current, vectors[j]);
while j >= 0 & amp; & amp; current < vectors[j]{
let middle = vectors[j + 1];
vectors[j + 1] = vectors[j];
vectors[j] = middle;
if j > 0{
/* rust does not allow decrement by 1 when j = 0 in while j >=0
This dangerous way of writing causes j to be a negative number in while */
j = j - 1; // j decreases, that is, it is constantly compared with the left side
}
println!("after vectors: {:?}", vectors);
}
}
vectors
}
The printed result after running the code is as follows:
vectors: [7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11] current vectors: [7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11] current: 21 < vectors[j]: 7 current vectors: [7, 21, 9, 13, 109, 9, 2, 50, 33, -1, 20, 11] current: 9 < vectors[j]: 21 after vectors: [7, 9, 21, 13, 109, 9, 2, 50, 33, -1, 20, 11] current vectors: [7, 9, 21, 13, 109, 9, 2, 50, 33, -1, 20, 11] current: 13 < vectors[j]: 21 after vectors: [7, 9, 13, 21, 109, 9, 2, 50, 33, -1, 20, 11] current vectors: [7, 9, 13, 21, 109, 9, 2, 50, 33, -1, 20, 11] current: 109 < vectors[j]: 21 current vectors: [7, 9, 13, 21, 109, 9, 2, 50, 33, -1, 20, 11] current: 9 < vectors[j]: 109 after vectors: [7, 9, 13, 21, 9, 109, 2, 50, 33, -1, 20, 11] after vectors: [7, 9, 13, 9, 21, 109, 2, 50, 33, -1, 20, 11] after vectors: [7, 9, 9, 13, 21, 109, 2, 50, 33, -1, 20, 11] current vectors: [7, 9, 9, 13, 21, 109, 2, 50, 33, -1, 20, 11] current: 2 < vectors[j]: 109 after vectors: [7, 9, 9, 13, 21, 2, 109, 50, 33, -1, 20, 11] after vectors: [7, 9, 9, 13, 2, 21, 109, 50, 33, -1, 20, 11] after vectors: [7, 9, 9, 2, 13, 21, 109, 50, 33, -1, 20, 11] after vectors: [7, 9, 2, 9, 13, 21, 109, 50, 33, -1, 20, 11] after vectors: [7, 2, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11] after vectors: [2, 7, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11] current vectors: [2, 7, 9, 9, 13, 21, 109, 50, 33, -1, 20, 11] current: 50 < vectors[j]: 109 after vectors: [2, 7, 9, 9, 13, 21, 50, 109, 33, -1, 20, 11] current vectors: [2, 7, 9, 9, 13, 21, 50, 109, 33, -1, 20, 11] current: 33 < vectors[j]: 109 after vectors: [2, 7, 9, 9, 13, 21, 50, 33, 109, -1, 20, 11] after vectors: [2, 7, 9, 9, 13, 21, 33, 50, 109, -1, 20, 11] current vectors: [2, 7, 9, 9, 13, 21, 33, 50, 109, -1, 20, 11] current: -1 < vectors[j]: 109 after vectors: [2, 7, 9, 9, 13, 21, 33, 50, -1, 109, 20, 11] after vectors: [2, 7, 9, 9, 13, 21, 33, -1, 50, 109, 20, 11] after vectors: [2, 7, 9, 9, 13, 21, -1, 33, 50, 109, 20, 11] after vectors: [2, 7, 9, 9, 13, -1, 21, 33, 50, 109, 20, 11] after vectors: [2, 7, 9, 9, -1, 13, 21, 33, 50, 109, 20, 11] after vectors: [2, 7, 9, -1, 9, 13, 21, 33, 50, 109, 20, 11] after vectors: [2, 7, -1, 9, 9, 13, 21, 33, 50, 109, 20, 11] after vectors: [2, -1, 7, 9, 9, 13, 21, 33, 50, 109, 20, 11] after vectors: [-1, 2, 7, 9, 9, 13, 21, 33, 50, 109, 20, 11] current vectors: [-1, 2, 7, 9, 9, 13, 21, 33, 50, 109, 20, 11] current: 20 < vectors[j]: 109 after vectors: [-1, 2, 7, 9, 9, 13, 21, 33, 50, 20, 109, 11] after vectors: [-1, 2, 7, 9, 9, 13, 21, 33, 20, 50, 109, 11] after vectors: [-1, 2, 7, 9, 9, 13, 21, 20, 33, 50, 109, 11] after vectors: [-1, 2, 7, 9, 9, 13, 20, 21, 33, 50, 109, 11] current vectors: [-1, 2, 7, 9, 9, 13, 20, 21, 33, 50, 109, 11] current: 11 < vectors[j]: 109 after vectors: [-1, 2, 7, 9, 9, 13, 20, 21, 33, 50, 11, 109] after vectors: [-1, 2, 7, 9, 9, 13, 20, 21, 33, 11, 50, 109] after vectors: [-1, 2, 7, 9, 9, 13, 20, 21, 11, 33, 50, 109] after vectors: [-1, 2, 7, 9, 9, 13, 20, 11, 21, 33, 50, 109] after vectors: [-1, 2, 7, 9, 9, 13, 11, 20, 21, 33, 50, 109] after vectors: [-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109] results: [-1, 2, 7, 9, 9, 11, 13, 20, 21, 33, 50, 109]
It can be seen that the description in the theoretical part is correct
The complete Rust insertion sort code is as follows:
Rust algorithm code repository address github.com/asyncins/ac…
Author: Huawei Cloud Enjoyment Expert Wei Shidong
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 53277 people are learning the system