02331 – Data Structures

Original link: https://anran758.github.io/blog/2022/05/18/note-02331/

Make a brief review of the content that needs to be assessed in the self-examination practice.

sort

selection sort

Basic idea: Select the record with the smallest keyword among the records to be sorted each time, and store it at the end of the sorted record sequence until all the sorting is done.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
25
26
27
28
29
30
31
32
33
34

# include <iostream>
using namespace std;

void SelectSort ( int arr[], int n) {
int k;
for ( int i = 0 ; i < n; i++) {
k = i;
for ( int j = i + 1 ; j < n; j++) {
if (arr[j] < arr[k]) {
k = j;
}
}

if (k != i) {
swap (arr[i], arr[k]);
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}

int main () {
int arr[] = { 4 , 3 , 2 , 9 , 8 , 6 , 7 , 1 , 5 , 10 };
int n = sizeof (arr) / sizeof (arr[ 0 ]);
cout << sizeof (arr[ 0 ]) << "\n" ;

SelectSort (arr, n);

for ( int i = 0 ; i < n; i++) {
cout << arr[i] << " " ;
}
}

Insertion sort

Basic idea: Insert a record to be sorted into the appropriate position in the previously sorted file according to the size of its keyword each time until all records are inserted into the position.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 void InsertSort ( int arr[], int n) {
int i, j, tmp;
// Do direct insertion sort to the sequence table
for (i = 1 ; i < n; i++) {
// The current value is smaller than the previous value, then swap positions
if (arr[i] < arr[i - 1 ]) {

tmp = arr[i];
// backward diff the ordered area item by item to find the appropriate insertion position
for (j = i - 1 ; j >= 0 && tmp < arr[j]; j--) {
arr[j + 1 ] = arr[j];
}
arr[j + 1 ] = tmp;
}
}
}

This article is reprinted from: https://anran758.github.io/blog/2022/05/18/note-02331/
This site is for inclusion only, and the copyright belongs to the original author.

Leave a Comment

Your email address will not be published.