# 02331 – Data Structures

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 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; } } }`