C++ Quicksort Algorithm Crashing

Question

我正在研究一種C++ quicksort算法，它可以計算排序過程中重要操作的數量。它會正確地對100個值進行排序，但之後會陷入無限循環。任何幫助將不勝感激！

//QuickSort.cpp

#include "QuickSort.h" 
#include <algorithm> 

using namespace std; 

QuickSort::QuickSort(int max) : SortData(max) 
{ 
    /* 
    maxSize = max; 
    theData = new long[max]; 
    */ 
    SortData::randomize(12); 

} 

QuickSort::~QuickSort(void) 
{ 

} 

_int64 QuickSort:: sort() 
{ 
    numops = 0; 
    quicksort(theData, 0, (size()-1)); 
    return(numops); 
} 

//Include counting number of operations 
void QuickSort::quicksort(long theData[], int left, int right) 
{ 
    //Default variables 

    if (size() <= 1 || left >= size() || right >= size()) return; //Bounds checking 

    if (left < right) 
    { 
     long pivot = partition(theData, left, right); 

     quicksort(theData, left, pivot-1); 
     quicksort(theData, pivot+1, right); 
    } 
} 

int QuickSort::partition(long theData[], int left, int right) 
{ 
    long pivot = theData[left]; 
    while (true) 
    { 
     while (theData[left] < pivot) left++; 
     numops ++; 

     while (theData[right] > pivot) right--; 
     numops ++; 

     if (left < right) 
     { 
      swap(theData[left], theData[right]); 
      numops+=3; 
     } 

     else 
     { 
      return right; 
     } 
    } 
} 

//QuickSort.h

#pragma once 
#include "SortData.h" 

class QuickSort : public SortData 
{ 

public: 
    QuickSort(int max = 100); 
    ~QuickSort(void); 
    _int64 sort(); 
private: 
    _int64 numops; 
    void QuickSort::quicksort(long theData[], int left, int right); 
    int partition(long theData[], int left, int right); 
}; 

Answer 1

在你的分區功能

if (left < right) 

總是正確的。因此，你可以得到無限的while（true）循環。

而且你可能在SortData.h中的size（）函數中有一個問題，我們目前還看不到它。

由於數據是隨機的，因此您會在某些輸入集上不時看到問題。

輕微的修改必須幫助：

if (left <= right) { 
     if (left < right) { 
      swap(theData[left], theData[right]); 
      numops += 3; 
     } 
     left++; 
     right--; 
} 
else { 
    return right; 
} 

對不起，我仔細檢查:)

Answer 2

partition卡住如果left < right和theData[left] == theData[right]。