Rust Data Structure — Sorting Algorithm (PART 1)

This is the 7th day of my participation in the August Text Challenge.More challenges in August

0x01 Common sorting algorithms

Sorting algorithm is a very common algorithm in data structure. If you know about data structures, what are the common sorting algorithms? I don’t even want to answer that question. So let me just list them.

  • Selection sort
  • Insertion sort
  • Hill sorting
  • Bubble sort
  • Quick sort
  • Radix sort
  • Heap sort
  • Merge sort and so on

There are so many sorting algorithms out there that today we will use Rust to implement several relatively simple sorting algorithms.

0x02 Select sort

Selection sort is a simple and intuitive sorting algorithm, whatever data goes in is O(n²) time complexity. So when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory.

Algorithm steps

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 the second step until all elements are sorted.

Algorithm implementation
fn select_sort(vec: &mut Vec<i32>) { for i in 0.. vec.len() - 1 { let mut mix_index = i; for j in i + 1.. vec.len() { if vec[mix_index] > vec[j] { mix_index = j; }} // If a value smaller than the current value is found // swap if mix_index! = i { let temp = vec[i]; vec[i] = vec[mix_index]; vec[mix_index] = temp; }}}Copy the code

0x03 Insert Sort

The basic idea of insert sort is to insert a record into an already ordered table, thus creating a new ordered table with the number of records increased by one. The average time complexity of insertion sort is also O(n^2), and the space complexity is O(1) of constant order. The specific time complexity is also related to the order of array.

Algorithm steps

In the process of its implementation, the use of a double-layer loop, the outer loop to all elements except the first element, the inner loop to the ordered list in front of the current element to be inserted position search, and move.

Algorithm implementation
fn insert_sort(vec: &mut Vec<i32>) { for i in 0.. vec.len() { let mut j = i; While j > 0 {vec[j] < vec[j-1] {// Let temp = vec[j]; vec[j] = vec[j - 1]; vec[j - 1] = temp; } j -= 1; }}}Copy the code

0x04 Hill sort

Shell Sort is a kind of insert Sort. It is an improvement of direct insert Sort algorithm. Hill sort, also known as reduced incremental sort, was proposed by DL.Shell in 1959. It does this by comparing elements spaced a certain distance apart, and the distance used for each run of comparison decreases as the algorithm progresses, until only the last order of adjacent elements is compared. Hill sort time complexity is O(n^(1.3-2)) and space complexity is constant order O(1).

Algorithm steps

The purpose of Hill sort is to improve the speed of insertion sort, swap non-adjacent elements to sort parts of an array, and finally use insertion sort to sort locally ordered arrays. Here we select the increment gap=length/2 and narrow the increment by gap= gap/2 with the sequence {n/2,(n/2)/2… 1}. In the process of implementing the code, it is recommended to write an insert sort first, and then divide it into gaps.

Algorithm implementation
pub fn shell_sort(vec: &mut Vec<i32>) { let mut gap = vec.len() / 2; While gap > 0 {// Insert sort for I in gap.. vec.len() { let mut j = i; While j > 0 &&j >= gap {// Switch if vec[j-gap] > vec[j] {vec[j-gap] = vec[j-gap] ^ vec[J]; vec[j] = vec[j - gap] ^ vec[j]; vec[j - gap] = vec[j - gap] ^ vec[j]; } j -= gap; } } gap /= 2; }}Copy the code

0x05 Bubble sort

Bubble sort is also a simple and intuitive sorting algorithm. Its time complexity: O(n^2) space complexity: O(1).

Algorithm steps

It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.

Algorithm implementation
fn bubble_sort(vec: &mut Vec<i32>) { for i in 0.. vec.len() { for j in 0.. Vec. Len () - 1 - I {/ / switching if vec [j] > vec [m + 1] {vec [j] = vec [j] ^ vec [j + 1); vec[j + 1] = vec[j] ^ vec[j + 1]; vec[j] = vec[j] ^ vec[j + 1]; }}}}Copy the code

summary

This tutorial looks at some simple sorting algorithms implemented using Rust. It’s almost the same as any other language. When I have time, I will also write the algorithm behind