Algorithm -- OptimizedSelectionSort

ゝ一纸荒年。 2022-06-02 11:25 136阅读 0赞

SortTestHelper.h

#ifndef SELECTIONSORT_SORTTESTHELPER_H
    #define SELECTIONSORT_SORTTESTHELPER_H
    
    #include <iostream>
    #include <ctime>
    #include <cassert>
    
    using namespace std;
    
    
    namespace SortTestHelper {
    
        // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
        int *generateRandomArray(int n, int rangeL, int rangeR) {
    
            assert(rangeL <= rangeR);
    
            int *arr = new int[n];
    
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
            return arr;
        }
    
        int *generateNearlyOrderedArray(int n, int swapTimes) {
            int *arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = i;
            }
            srand(time(NULL));
            for (int i = 0; i < swapTimes; ++i) {
                int posx = rand() % n;
                int posy = rand() % n;
                swap(arr[posx], arr[posy]);
            }
            return arr;
        }
    
        // 打印arr数组的所有内容
        template<typename T>
        void printArray(T arr[], int n) {
    
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
            cout << endl;
    
            return;
        }
    
        template<typename T>
        bool isSorted(T arr[], int N) {
            for (int i = 0; i < N - 1; ++i) {
                if (arr[i] > arr[i + 1]) {
                    return false;
                }
            }
            return true;
        }
    
        template<typename T>
        void testSort(string sortName, void(*sort)(T[], int), T arr[], int N) {
            clock_t startTime = clock();
            sort(arr, N);
            clock_t endTime = clock();
    
            assert(isSorted(arr, N));
            cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
            return;
        }
    
        int *copyIntArray(int a[], int n) {
            int *arr = new int[n];
            copy(a, a + n, arr);
            return arr;
        }
    };
    #endif //SELECTIONSORT_SORTTESTHELPER_H

main.cpp

#include <iostream>
    
    #include "SortTestHelper.h"
    
    using namespace std;
    
    template<typename T>
    void selectionSort(T arr[], int n){
    
        int left = 0, right = n - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = right;
    
            // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
            if(arr[minIndex] > arr[maxIndex])
                swap(arr[minIndex], arr[maxIndex]);
    
            for(int i = left + 1 ; i < right; i ++)
                if(arr[i] < arr[minIndex])
                    minIndex = i;
                else if(arr[i] > arr[maxIndex])
                    maxIndex = i;
    
            swap(arr[left], arr[minIndex]);
            swap(arr[right], arr[maxIndex]);
    
            left ++;
            right --;
        }
    
        return;
    }
    
    
    int main() {
        int n = 10000;
        /*int *arr = SortTestHelper::generateNearlyOrderedArray(n, 100);*/
        int *arr = SortTestHelper::generateRandomArray(n, 0, n);
        SortTestHelper::testSort("Optimized Selection Sort", selectionSort, arr, n);
    
        delete[] arr;
        return 0;
    }