如何简化彼此相似的两个功能

时间:2022-06-30 08:48:05

I'm a student studying computer engineering. today I was learning quick sort using C++. It is so awesome algorithm and I recognized that quick sort needs two function for ascending order and the opposite. Following is my codes!

我是一名学习计算机工程的学生。今天我用C ++学习快速排序。它是如此棒的算法,我认识到快速排序需要两个函数升序和相反。以下是我的代码!

#include <iostream>
#define ASCENDING 0 
#define DESCENDING 1
#define MAX_SIZE 50001

using namespace std;


int numberCnt;
int sortManner;
int list[MAX_SIZE];

void GetInput();
void QuickSort(int* list, int left, int right, int(*partition)(int*, int, int));
int PartitionAscending(int* list, int left, int right);
int PartitionDescending(int* list, int left, int right);
void Swap(int &a, int &b);

int main(){
    GetInput();
    QuickSort(list, 0, numberCnt - 1, sortManner == ASCENDING ? PartitionAscending : PartitionDescending);
    for (int i = 0; i < numberCnt; i++){
        cout << list[i] << endl;
    }

    return 0;
}

void QuickSort(int* list, int left, int right, int (*partition)(int*,int,int)){
    if (left < right){
        int pivot = partition(list, left, right);
        QuickSort(list, left, pivot - 1, partition);
        QuickSort(list, pivot + 1, right, partition);
    }
}
int PartitionAscending(int* list, int left, int right){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (list[low] < pivotVal);
        do{
            high--;
        } while (list[high] > pivotVal);
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

int PartitionDescending(int* list, int left, int right){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (list[low] > pivotVal);
        do{
            high--;
        } while (list[high] < pivotVal);
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void GetInput(){
    cin >> numberCnt >> sortManner;
    for (int i = 0; i < numberCnt; i++)
        cin >> list[i];
}

You know the functions is very similar with each other! It seems that wasteful to me!

你知道它们的功能非常相似!这对我来说似乎很浪费!

How to simplify the functions?

如何简化功能?

If you don't understand my pool English Plz, don't hesitate to let me know :)

如果你不懂我的泳池英语Plz,请不要犹豫,让我知道:)

2 个解决方案

#1


Your partition can take a comparison functor, something like:

您的分区可以采用比较仿函数,例如:

template <typename Comp>
int Partition(int* list, int left, int right, Comp comp){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (comp(list[low], pivotVal));
        do{
            high--;
        } while (!comp(list[high], pivotVal));
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

int PartitionAscending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l < r; });
    // or return Partition(list, left, right, std::less<int>());
}

int PartitionDescending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l > r; });
    // or return Partition(list, left, right, std::greater<int>());
}

#2


Add an other argument to your function that would specify if you need a ascending or descending call, a boolean ascending can do that, and calculate the loop condition like this :

在函数中添加另一个参数,指定是否需要升序或降序调用,布尔升序可以这样做,并计算循环条件,如下所示:

do{
   low++;
} while ( ascending ? (list[low] < pivotVal) : (list[low] > pivotVal));

#1


Your partition can take a comparison functor, something like:

您的分区可以采用比较仿函数,例如:

template <typename Comp>
int Partition(int* list, int left, int right, Comp comp){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (comp(list[low], pivotVal));
        do{
            high--;
        } while (!comp(list[high], pivotVal));
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

int PartitionAscending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l < r; });
    // or return Partition(list, left, right, std::less<int>());
}

int PartitionDescending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l > r; });
    // or return Partition(list, left, right, std::greater<int>());
}

#2


Add an other argument to your function that would specify if you need a ascending or descending call, a boolean ascending can do that, and calculate the loop condition like this :

在函数中添加另一个参数,指定是否需要升序或降序调用,布尔升序可以这样做,并计算循环条件,如下所示:

do{
   low++;
} while ( ascending ? (list[low] < pivotVal) : (list[low] > pivotVal));