Передача свопов и сравнений в функцию быстрой сортировки - PullRequest
Новая
       38

Передача свопов и сравнений в функцию быстрой сортировки

0 голосов
/ 30 октября 2018

Я делаю эту программу, в которой мне нужно подсчитать количество свопов и сравнить функцию быстрой сортировки, и мы должны передать свопы и компы в функцию. Я не слишком уверен, как это сделать. У меня есть, так что это можно сделать, ничего не передавая, как показано ниже. 

#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <math.h>

using namespace std;

struct SwapandComp {
    int swaps;
    int comps;
};

const long ARRAY_SIZE = 5000;
int totalSwaps = 0;
int totalComps = 0;

int partition(int[], int, int) //add parameters int& swap and int& comp
SwapandComp quickSort(int[], int, int) //also add parameters for int& swap and int& comp

int main() {

SwapandComp qui;
long masterAry[ARRAY_SIZE] = {0};
int quickAry[ARRAY_SIZE] = {0};
int start = 0;
int end = 0;
double difference = 0;
int size = ARRAY_SIZE;

srand(time(NULL));

for (int i = 0; i < ARRAY_SIZE; i++) {
masterAry[i] = rand();
}

for (int a = 0; a < ARRAY_SIZE; a++) {
quickAry[a] = masterAry[a];
}

start = clock();
qui = quickSort(quickAry, 0, ARRAY_SIZE - 1);
    end = clock();
    difference = end - start;
    double f = difference / CLOCKS_PER_SEC;

    cout << "Quick: " << f << " " << qui.swaps << " " << qui.comps << endl;
}

Это главное. Здесь значения присваиваются массиву для сортировки с помощью функции быстрой сортировки, которая будет определена ниже. 

int partition(int numbers[], int i, int k) { //add parameters int& swap and int& comp
    int l = 0;
    int h = 0;
    int midpoint = 0;
    int pivot = 0;
    int temp = 0;
    bool done = false;

    // Pick middle element as pivot
    midpoint = i + (k - i) / 2;
    pivot = numbers[midpoint];

    l = i;
    h = k;

    while (!done) {

        // Increment l while numbers[l] < pivot
        while (numbers[l] < pivot) {
            ++l;
            totalComps++;
        }

        // Decrement h while pivot < numbers[h]
        while (pivot < numbers[h]) {
            --h;
            totalComps++;
        }

        // If there are zero or one elements remaining,
        // all numbers are partitioned. Return h
        if (l >= h) {
            totalComps++;
            done = true;
        }
        else {
            // Swap numbers[l] and numbers[h],
            // update l and h
            temp = numbers[l];
            numbers[l] = numbers[h];
            numbers[h] = temp;
            totalSwaps++;

            ++l;
            --h;
        }
    }

    //cout << totalSwaps << " " << totalComps << endl;
    return h;
}

Это функция разбиения, чтобы найти, где найти следующую точку разбиения 

SwapandComp quickSort(int numbers[], int i, int k) { //add parameters int& swap and int& comp
    SwapandComp quick = { 0 };
    //quick.swaps = quick.comps = 0;
    int j = 0;
    int z = 0;


    // Base case: If there are 1 or zero elements to sort,
    // partition is already sorted
    if (i >= k) {
        return quick;
    }

    // Partition the data within the array. Value j returned
    // from partitioning is location of last element in low partition.
    j = partition(numbers, i, k);

    // Recursively sort low partition (i to j) and
    // high partition (j + 1 to k)
    quickSort(numbers, i, j);
    quickSort(numbers, j + 1, k);

    quick.swaps = totalSwaps;
    quick.comps = totalComps;



    //totalSwaps = 0;
    //totalComps = 0;

    return quick;
}

И, наконец, вот функция быстрой сортировки, где все свопы и комп будут добавлены вместе и помещены в структуру. Опять же, я не слишком уверен, как добавить в проход по ссылочным переменным для swap и comp. Любая помощь приветствуется! (Также извините за форматирование кода, на моем экране это стало сумасшествием.)

...