Сбой алгоритма ускорения C++

Question

Я работаю над алгоритмом быстрой сортировки C++, который подсчитывает количество значимых операций во время сортировки. Он будет правильно сортировать 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).

Возможно, у вас есть функция size() из SortData.h, которую мы пока не видим.

Поскольку данные случайные, вы время от времени видите проблему на некоторых наборах ввода.

Незначительное изменение должно помочь:

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].