3. 算法笔记-对数器

对数器是一个非常重要的自我验证技巧，其实现步骤如下：

(1) 方法 A

(2) 方法 B

(3) 随机样本产生器

(4) 用相同的样本验证方法 A 和方法 B，比对结果是否一致。

(5) 若出现样本，使得结果不一致，查找原因，进行改进。

(6) 否则，方法验证成功。

#include <vector>
#include <cstdio>
#include <ctime>
#include <cstdlib>                                                                                                             

class Sort{
private: 
    void swap(std::vector<int> &vec, int index_1, int index_2){
        int tmp = vec[index_1];
        vec[index_1] = vec[index_2];
        vec[index_2] = tmp;
        return;
    }

public:
    void select_sort(std::vector<int> &vec){
        int vec_size = vec.size();
        if(vec_size < 2)
            return; 
        for(int i = 0; i < vec_size - 1; ++i){
            int min_index = i; 
            for(int j = i + 1; j < vec_size; ++j){
                if(vec[j] < vec[min_index])
                    min_index = j;
            }
            this->swap(vec, i, min_index);
        }
        return;
    }

    void bubble_sort(std::vector<int> &vec){
        int vec_size = vec.size();
        if(vec_size < 2)
            return; 
        for(int i = vec_size - 1; i > 0; --i){
            for(int j = 0; j < i; ++j){
                if(vec[j] > vec[j+1])
                    this->swap(vec, j, j+1);
            }
        }
        return;
    }
    
    void insert_sort(std::vector<int> &vec){
        int vec_size = vec.size();
        if(vec_size < 2)
            return; 
        for(int i = 1; i < vec_size; ++i){
            for(int j = i - 1; j >= 0 && vec[j] > vec[j+1]; --j){
                this->swap(vec, j, j+1);
            }
        }
        return;
    }

    void check(int min, int max, int vec_size = 7, int time = 1000){                                                           
        std::srand((unsigned)std::time(NULL));
        for(int i  = 0; i < time; ++i){
            std::vector<int> vec;
            for(int i = 0; i < vec_size; ++i){
                int random_number = (rand() % (max - min + 1)) + min;
                vec.push_back(random_number);
            }
            std::vector<int> vec_1 = vec;
            std::vector<int> vec_2 = vec;
            std::vector<int> vec_3 = vec;
            
            this->select_sort(vec_1);
            this->bubble_sort(vec_2);
            this->insert_sort(vec_3);
            if(vec_1 != vec_2 || vec_1 != vec_3){
                printf("error ! sample vector is ");
                printf("{");
                for (auto value : vec){
                    printf(" %d ", value);
                }
                printf("}\n");
                return;
            }
        }
        printf("Successful.\n");
        return;
    }
};

int main(void){
    Sort sort;
    sort.check(-7, 7);
    return 0;
}