C ++计数快速排序比较< Unsolved> [英] C++ Counting Quicksort Comparisons <Unsolved>

问题描述

我正在做一个项目，要求我们实现不同的排序并添加计数器变量以测量具有不同数组大小的运行时.

I am working on a project that asks us to implement different sorts and add counter variables to measure the runtime with different array sizes.

我的问题是输出与预期输出不同

我已经完成了插入排序并正确计算了比较次数.

I already completed the insertion sort and correctly counts the number of comparisons.

我可以使用参考参数.

任何反馈都值得赞赏.

输出:[从答案更新]

Output:[Updated from Answer]

Quick sort           16          384         6401        74378

预期输出:

Array Size:          10         100         1000         10000
--------------------------------------------------------------------
Quick Sort           35         630         10292        132882 

对于数组大小为10的数组内容内部是什么:

Whats inside the contents of the array for array size 10:

内容随使用的种子保持不变.

The contents stay Constant with the used seed.

Insertion sort

[ 935, 942, 697, 299, 382, 579, 408, 181, 366, 505 ] //unsorted
[ 181, 299, 366, 382, 408, 505, 579, 697, 935, 942 ] //sorted

程序:[从答案更新]

Program: [Updated From Answer]

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
      /******************************/
      /* Start of Quick Sort Algorithm */
      /******************************/



static const int MIN_SIZE  = 10; // Smallest size of an array that quicksort will sort

/**
 * Sorts the items in an array into ascending order.
 */
template<class ItemType>
int insertionSort(ItemType theArray[], int first, int last) {
  int count = 0;
    for (int unsorted = first + 1; unsorted <= last; unsorted++) {
        ItemType nextItem = theArray[unsorted];
        int loc = unsorted;
        while ((loc > first) && (count++,theArray[loc - 1] > nextItem)) {
            theArray[loc] = theArray[loc - 1];
            loc--;
        }
        theArray[loc] = nextItem;
    }
    return count;
}

/**
 * Arranges two specified array entries into sorted order by
 * exchanging them, if necessary.
 * */
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
    if (theArray[i] > theArray[j]) {
        std::swap(theArray[i], theArray[j]);
    }
}

/**
 * Arranges the first, middle, and last entry in an array in sorted order.
 */
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
    int mid = first + (last - first) / 2;
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
    order(theArray, mid, last);  // Make theArray[mid] <= theArray[last]
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]

    return mid;
}

/**
 * Partitions the entries in an array about a pivot entry for quicksort.
 */
template<class ItemType>
int partition(ItemType theArray[], int first, int last,int &counter) {
    // Choose pivot using median-of-three selection
    int pivotIndex = sortFirstMiddleLast(theArray, first, last);

    // Reposition pivot so it is last in the array
    std::swap(theArray[pivotIndex], theArray[last - 1]);
    pivotIndex = last - 1;
    ItemType pivot = theArray[pivotIndex];

    // Determine the regions S1 and S2
    int indexFromLeft = first + 1;
    int indexFromRight = last - 2;

    bool done = false;
    while (!done) {
        // Locate first entry on left that is >= pivot
        while (theArray[indexFromLeft] < pivot) {
          counter++;//I incremented Count here
          indexFromLeft = indexFromLeft + 1;
        }

        // Locate first entry on right that is <= pivot
        while (theArray[indexFromRight] > pivot) {
          counter++;
          indexFromRight = indexFromRight - 1;
        }

        if (indexFromLeft < indexFromRight) {
            std::swap(theArray[indexFromLeft], theArray[indexFromRight]);
            indexFromLeft = indexFromLeft + 1;
            indexFromRight = indexFromRight - 1;
        }
        else {
            done = true;
        }
    }

    // Place pivot in proper position between S1 and S2, and mark its new location
    std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
    pivotIndex = indexFromLeft;

    return pivotIndex;
}

/**
 * Sorts an array into ascending order. Uses the quick sort with
 * median-of-three pivot selection for arrays of at least MIN_SIZE
 * entries, and uses the insertion sort for other arrays.
 */
template<class ItemType>
int quicksort(ItemType theArray[], int first, int last) {
    int result = 0;
    int counter = 0;
    if (last - first + 1 < MIN_SIZE) {
        result = insertionSort(theArray, first, last);
    }
    else {
        // Create the partition: S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last,counter);
        // Sort subarrays S1 and S2
         result += quicksort(theArray, first, pivotIndex - 1);
         result += quicksort(theArray, pivotIndex + 1, last);
         result += counter;
    }
    return result; //return final count
}


      /******************************/
      /* Start of Sorting Benchmark  */
      /******************************/
int* makeRandomArray(int n, int seed) {
    srand(seed);
    int * a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 1000;
    }
    return a;
}

int main(){
    const int seed = 9000;
    int *a;

    /******************************/
    /* Start of Quick Sort    */
    /******************************/
    std::cout << "Quick sort";

    int n = 10;
    a = makeRandomArray(10, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 100;
    a = makeRandomArray(100, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 1000;
    a = makeRandomArray(1000, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 10000;
    a = makeRandomArray(10000, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1)<<std::endl;
    delete[] a;

    return 0;
}

推荐答案

在快速排序中，当分区方法/函数正在寻找违反以下规则的元素时进行比较:元素小于枢轴的元素必须位于左侧大于必须在右侧的枢轴和元素.这两个时候正是这样做的.当当前元素小于枢轴时，第一个继续向右移动(第一组比较).第二个同时执行相反的操作，即，当当前元素大于枢轴时，它继续向左移动，进行第二组比较.如果左侧索引小于右侧索引，则意味着它找到了一个比左侧枢轴大的元素和一个小于右侧枢轴的元素，因此它将交换它们.该过程继续进行，直到左索引通过右索引为止.完成后，所有左侧的值都小于枢轴，所有右侧的值都大于枢轴，因此它将枢轴与较小侧的最后一个元素交换并返回枢轴位置，因为现在枢轴位于正确的位置和中间"位置找到了该分区的一部分，从而使排序过程可以继续到左分区和右分区.

In quick sort, the comparisons are made when the partition method/function is looking for elements that break the rule that elements smaller than the pivot must be on the left of the pivot and elements larger than it must be on the right. These two whiles do exactly this. The first one keeps going to the right while the current element is smaller than the pivot (first set of comparisons). The second while do the opposite operation, i.e., it keeps going to the left while the current element is bigger than the pivot, doing the second set of comparisons. If the left index is smaller than the right index, it means that it found an element that is bigger than the pivot on the left and an element that is smaller than the pivot on the right, so it will swap them. The process continues, until the left index pass throught the right one. When it finishes, all the left values are smaller than the pivot and all the right values are bigger than the pivot, so it swaps the pivot with the last element of the smaller side and returns the pivot position, since now, the pivot is in the correct position and the "middle" of that partition was found, allowing the sorting process to continue to the left partition and to the right partition.

while (theArray[indexFromLeft] < pivot) {
    // count here
    indexFromLeft = indexFromLeft + 1;
}

while (theArray[indexFromRight] > pivot) {
    // and here
    indexFromRight = indexFromRight - 1;
}

这篇关于C ++计数快速排序比较< Unsolved>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！