如何使用 C++ 为快速排序编写分区

Question

我正在用 C++ 编写一个算法，用户键入他们想要排序的数字数量，然后程序生成一个随机数数组，并对它们进行排序。它还会显示排序所花费的时间。

即使我使用相同的输入，它也只适用于一些试验。例如，如果我要求程序对 20 个数字的数组进行排序，将会发生以下三种情况之一：

它将毫无问题地对数组进行排序。
算法超时，终端打印“Segmentation fault: 11”。
算法会按照正确的顺序对数字进行排序，但其中一个数字会被随机的负数替换。

这是我的分区算法（给我带来麻烦）。我选择 first/left 项目作为我的支点：

int partition(int arr[], int leftIndex, int rightIndex)
    {
        int i = leftIndex;
        int j = rightIndex;
        int pivotValue = arr[leftIndex];

        while(i < j){
            while(arr[i] <= pivotValue){
                i++;
            }
            while(arr[j] > pivotValue && i < j){
                j--;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i - 1];
        arr[i - 1] = arr[leftIndex];
        arr[leftIndex] = temp;

        return i - 1;
    }

这是我的快速排序算法：

void quickSort(int arr[], int left, int right)
   {    
      if (left < right)
      {
        int pivot = partition(arr, left, right);

        quickSort(arr, left, pivot - 1);

        quickSort(arr, pivot + 1, right);
      }
      return;
   }

这是我在 main() 中调用所有内容的地方：

int main()
  {
    clock_t sTime, eTime;

    int n;
    cout << "Enter an array size: " << endl;
    cin >> n; 
    cout << endl;
    int originalArray[n];
    
  
    cout << "Start generating random numbers..." << endl;
    for(int index=0; index<n; index++){ 
        originalArray[index] = (rand()%100)+1;

    }
    
    
    cout << "Original array values: "; 
    printArray(originalArray, n);
    cout<<"\n\n";
    

    //Makes a copy of the original array to preserve its original order
    int quickArray[sizeof(originalArray)];
    for(int i = 0; i < sizeof(originalArray); i++){
        quickArray[i] = originalArray[i];
    }

    //Perform quicksort
    sTime = clock();
    quickSort(quickArray, 0, n-1);
    eTime = clock();
    printf("Sorted array by quickSort: ");
    printArray(quickArray, n);
    cout << "\nTotal CPU time used in quickSort: " << (double)(eTime-sTime) / CLOCKS_PER_SEC * 1000.0 << " ms" << endl;
    
    cout << endl; 

 
  
    return 0;
  }

Answer 1

我不确定它是否是您看到的所有问题的原因，但我会从这段代码开始：

        while(i < j){
            while(arr[i] <= pivotValue){
                i++;
            }

如果主元是数组中的最大值，这（尤其是内部循环）会做什么？

Answer 2


#include <bits/stdc++.h>

using namespace std;

int partition(int arr[], int leftIndex, int rightIndex)
    {
        int pivotIndex = leftIndex;
        int pivotValue = arr[pivotIndex];

        int i = leftIndex;
        int j = rightIndex;
        

        while(i < j){
            while(arr[i] <= pivotValue){
                i++;
                if(i >= rightIndex) break;
            }
            while(arr[j] >= pivotValue){
                j--;
                if(j <= leftIndex) break;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap
        arr[pivotIndex] = arr[j];
        arr[j] = pivotValue;

        return j;
    }
    void quickSort(int arr[], int left, int right)
   {    
   
      if (left < right)
      {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
      }
      return;
   }

   int main()
  {
    clock_t sTime, eTime;

    int n;
    cout << "Enter an array size: " << endl;
    cin >> n; 
    cout << endl;
    int originalArray[n];
    
  
    cout << "Start generating random numbers..." << endl;
    for(int index=0; index<n; index++){ 
        originalArray[index] = (rand()%100)+1;

    }
    
    
    cout << "Original array values: "; 
    for(auto c: originalArray) {
        cout << c << " ";
    }

    cout<<"\n\n";
    

    //Makes a copy of the original array to preserve its original order
    int quickArray[n];
    for(int i = 0; i < n; i++){
        quickArray[i] = originalArray[i];
    }

    //Perform quicksort
    sTime = clock();
    quickSort(quickArray, 0, n-1);
    eTime = clock();
    printf("Sorted array by quickSort: ");
    for(auto c: quickArray) {
        cout << c << " ";
    }
    cout << endl;
    cout << "\nTotal CPU time used in quickSort: " << (double)(eTime-sTime) / CLOCKS_PER_SEC * 1000.0 << " ms" << endl;
    
    cout << endl; 

 
  
    return 0;
  }

我遇到过几个错误。首先，我在 partititon() 方法的 while 循环中添加了 break 语句，以便它在超出数组边界时中断递增 i 或递减 j。这可能就是为什么有时会出现分段错误的原因。
然后我更改了分区末尾的交换部分并返回 j。可能这部分没有错误，但我发现这个解决方案更具可读性。
然后我将创建新数组的部分更改为 int quickArray[n]，您正在使用 sizeof(originalArray) 创建 quickArray，这是错误的，因为它曾经使用更多的元素。 sizeof() returns (number of elements) * 4 因为每个 int 占用 4 个字节的内存。
现在，它应该可以正常工作了。

此外，选择第一个元素作为基准可以使您的程序在最坏的情况下以 O(n^2) 时间复杂度运行，请尝试在将数组发送到 quicksort() 函数之前对其进行洗牌。通过这样做，您可以消除最坏的情况。

如何使用 C++ 为快速排序编写分区

How to write partition for quicksort with C++

c++

sorting

algorithm

quicksort

segmentation-fault