The selection algorithm

From my views, I think the best way to implement the selection algorithm is to think the procedures to execute the steps of the selection algorithm.

The description of the selection algorithm

Suppose there is a unsorted array with integers. The intuition for this algorithm recrusively pick out the minimum value from the decreasing size of the array and put it on the first position of the array. The concrete steps are as follows.

1. From the A[0, n-1], pick out the minimum entry from the array and put it in the position indexed by 0；
2. From the A[1, n-1], pick out the minimum entry from the array and put it in the position indexed by 1；
3. From the A[2, n-1], pick out the minimum entry from the array and put it in the position indexed by 2；
4. $\cdots$
5. From the A[n-1, n-1], pick out the minimum entry from the array and put it in the position indexed by n-1

The key points to implement it

Variable 1：x:conrol starting point
variable 2:y:control traverse

key technique: log minimum value by its index not value

The corresponding codes for this

#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // select sort
        vector<int> res(nums);
        int n = res.size();
        for (int i = 0; i < n; i++) {
            int min_index = i;
            for (int j = i+1; j < n; j++) {
                if (res[j] < res[min_index]) min_index = j;
            }
            swap(res[i], res[min_index]);
        }
        return res;
    }
};
int main() {
    srand(time(NULL));
    vector<int> nums;
    // initialize nums 100 random numbers
    for (int i = 0; i < 100; ++i) {
        nums.push_back(rand() % 1000);
    }
    Solution s;
    vector<int> res = s.sortArray(nums);
    for (auto i : res) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

The bubble sort

The intuition for this algorithm

the intutition: the opposite of the selection
primay technique: swap

The corresponding codes for this

#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> res(nums);
        int n = res.size();
        /* bubble sort */
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j > 0; j--) {
                if (res[j] < res[j-1]) swap(res[j], res[j-1]);
            }
        }
        return res;
        /*solution2*/
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n - i - 1; j++) {
        //         if (res[j] > res[j + 1]) {
        //             swap(res[j], res[j + 1]);
        //         }
        //     }
        // }
        // return res;
    }
};
int main() {
    srand(time(NULL));
    vector<int> nums;
    // initialize nums 100 random numbers
    for (int i = 0; i < 100; ++i) {
        nums.push_back(rand() % 1000);
    }
    Solution s;
    vector<int> res = s.sortArray(nums);
    for (auto i : res) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

The insertion algorithm

#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> res(nums);
        int n = res.size();
        /* insertion sort */
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (res[j] < res[j-1]) {
                    swap(res[j], res[j-1]);
                }
            }
        }
        return res;
        for (int i = 1; i < n; i++) {
        //     int j = i;
        //     while (j > 0 && res[j] < res[j - 1]) {
        //         swap(res[j], res[j - 1]);
        //         j--;
        //     }
        // }
        // return res;
    }
};
int main() {
    srand(time(NULL));
    vector<int> nums;
    // initialize nums 100 random numbers
    for (int i = 0; i < 100; ++i) {
        nums.push_back(rand() % 1000);
    }
    Solution s;
    vector<int> res = s.sortArray(nums);
    for (auto i : res) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

The corresponding results

5 31 43 58 59 79 89 111 123 129 154 158 160 173 182 190 201 203 208 209 209 210 227 228 243 249 250 254 255 267 270 270 303 312 332 345 363 387 395 400 426 443 444 446 451 481 482 488 489 493 505 507 534 544 586 587 596 598 609 610 614 619 639 642 676 691 693 716 718 727 732 746 754 756 776 810 814 814 815 839 848 857 880 881 899 924 933 942 945 951 954 955 957 966 969 976 990 991 992 994 
1