0

这是作业的一部分，我们必须在其中比较不同的排序算法。为了进行公正的测试，我应用了一些基本的统计概念。我没有运行单个测试，而是执行了具有不同数组大小的测试样本。样本量是固定的，100，每轮的元素数量不等：一千、一万、十万、一百万和一千万个元素，数组是随机填充的。

由于插入排序的限制，十万个元素后没有测试。还记录了每个算法执行的比较次数和数组访问次数。

在报告的最后，shell 排序优于堆排序。我不清楚原因。可能与填充数组的方式（使用随机数）有关吗？

包含 1000 万个元素的数组的平均运行时间

这是用于两种算法的代码：

// source: Data Structures and Problem Solving Using C++ 2nd Edition
// page 329
void sortingAlgs::shellSort(std::vector<int>& array, int n) {
    for (int gap{static_cast<int>(n/2)}; gap > 0;
         gap = gap == 2 ? 1 : static_cast<int>(gap / 2.2)) { // floor
        for (int i{gap}; i < n; i++) {
            int temp = array[i];
            int j = i;

            for (; j >= gap && temp < array[j-gap]; j -= gap) {
                array[j] = array[j-gap];
            }
            array[j] = temp;
        }
}
}


// source: http://quiz.geeksforgeeks.org/heap-sort/
// source: Introduction to Algorithms page 154
    void sortingAlgs::max_heapify(std::vector<int>& array, int n, int i) {
    int largest = i;      // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2

    // If left child is larger than root
    if (l < n && array[l] > array[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && array[r] > array[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        std::swap(array[i], array[largest]);
        // Recursively heapify the affected sub-tree
        max_heapify(array, n, largest);
    }
}

// source: http://quiz.geeksforgeeks.org/heap-sort/
// source: Introduction to Algorithms page 160
void sortingAlgs::heapSort(std::vector<int>& array, int n) {
    // Build heap (re-arrange array)
    for (int i = (n / 2) - 1; i >= 0; i--) {
        max_heapify(array, n, i);
    }

    // One by one extract an element from heap
    for (int i = n-1; i >= 0; i--)
    {
        // Move current root to end
        std::swap(array[0], array[i]);
        // call max heapify on the reduced heap
        max_heapify(array, i, 0);
    }
}
4

0 回答 0