时间戳

首页 > 解决方案 > 实施 Hoare 算法以获得更好的快速排序性能并读取比较和交换的数量

c++ - 实施 Hoare 算法以获得更好的快速排序性能并读取比较和交换的数量

问题描述

我在下面有以下关于排序算法的 C++ 代码。我正在改进应用 Hoare 方案的 Quicksort。作为算法的一部分，我想看看进行了多少比较和交换，我目前正在努力让这个算法正常工作。当算法设置为快速排序并使用随机或反向作为元素为 100 000 的数据集时，我得到的输出是“糟糕”。是否有可能解释为什么会发生这种情况以及我可以在哪里进行调整/改进？

#include <cstdlib>
#include <getopt.h>
#include <iostream>
#include <string>

using namespace std;

static long comparisons = 0;
static long swaps = 0;

void swap(int* a, int* b) {

    swaps++;
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int* first, int* last) {

    int n = last - first;
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (first [j] < first [min_index]) {
                min_index = j;
            }
        }
        comparisons++;
        if (min_index != i) {
            swap(first + i, first + min_index);
        }
    }
}

void insertionSort(int* first, int* last) {

    int n = last - first;
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (first[j] < first [min_index]) {
                min_index = j;
            }
        }
        comparisons++;
        if (min_index != i) {
            swap(first + i, first + min_index);
        }
    }
}

int partition(int low, int high) {

    int pivot = low;
    int i = low - 1;
    int j = high + 1;
    while (true) {

        do {
            i++;
            comparisons++;
        }
        while (i < pivot);

        do {
            j--;
            comparisons++;
        }
        while (j > pivot);

        if (i >= j) {
            return j;
        }

        int temp = i;
        i = j;
        j = temp;
        swaps++;

        swap(i, j);
    }
}

void quickSort(int low, int high) {

    if (low >= high) {
        return;
    }

    int pivot = partition(low, high);
    quickSort(low, pivot);
    quickSort(pivot + 1, high);
}

int main(int argc, char** argv) {

    string algorithm = "quicksort";
    string dataset = "reverse";

    for (int c; (c = getopt(argc, argv, "ravgsin")) != -1;) {
        switch (c) {
        case 'r':
            dataset = "random";
            break;
        case 'a':
            dataset = "sorted";
            break;
        case 'v':
            dataset = "reverse";
            break;
        case 'q':
            algorithm = "quicksort";
            break;
        case 's':
            algorithm = "selection";
            break;
        case 'i':
            algorithm = "insertion";
            break;
        case 'n':
            algorithm = "none";
            break;
        }
    }
    argc -= optind;
    argv += optind;

    const int size = argc > 0 ? atoi(argv[0]) : 100000;
    int* data = new int[size];

    if (dataset == "sorted") {
        for (int i = 0; i < size; ++i) {
            data[i] = i;
        }
    }
    else if (dataset == "reverse") {
        for (int i = 0; i < size; ++i) {
            data[i] = size - i - 1;
        }
    }
    else if (dataset == "random") {
        for (int i = 0; i < size; ++i) {
            data[i] = rand() % size;
        }
    }
    if (algorithm == "quicksort") {
        quickSort(*data, *(data + size));
    }
    else if (algorithm == "selection") {
        selectionSort(data, data + size);
    }
    else if (algorithm == "insertion") {
        insertionSort(data, data + size);
    }

    for (int i = 1; i < size; i++) {
        if (data[i] < data[i - 1]) {
            cout << "Oops!" << '\n';
            exit(1);
        }
    }

cout << "OK" << '\n';
cout << "Algorithm:   " << algorithm << '\n';
cout << "Data set:    " << dataset << '\n';
cout << "Size:        " << size << '\n';
    //Uncomment for level 3 and 4
    cout << "Comparisons: " << comparisons << '\n';
    cout << "Swaps:       " << swaps << '\n';

    delete[] data;
    return 0;
}

标签： c++algorithmquicksort

解决方案

您对快速排序的调用传递的是数据值，而不是索引。它相当于

quicksort(data[0], data[size]);

其中，由于数据具有size分配给它的元素，因此是越界访问。

对快速排序的调用需要包含要排序的数据和要排序的数组中的索引值。

quicksort(data, 0, size - 1);

需要对您的快速排序功能进行适当的更改（目前，该功能没有任何用处）。

推荐阅读