Я пытаюсь реализовать QuickSort()
используя случайный шарнир
Когда я не рандомизирую пивот и выбираю его как A [0], все работает нормально,
но когда я применяю рандомизацию, все сходит с ума.
Раздел:
int Partition(int A[], int left, int right, int pivot = 0)
{
swap(A[left], A[pivot]);
int temp = right;
while (pivot != temp)
{
// make a swap if needed
if (A[pivot] > A[temp] && temp > pivot || A[temp] > A[pivot] && temp < pivot)
{
// swap both data and index
swap(A[pivot], A[temp]);
swap(pivot, temp);
}
// advance the temp towards pivot
if (temp < pivot)
temp++;
else
temp--;
}
return pivot;
}
QuickSort:
void QuickSort(int A[], int left, int right)
{
int pivot;
if (left < right) {
// randomize pivot
srand(time(NULL));
pivot = rand() % (right - left + 1);
// partition and call quicksort
pivot = Partition(A, left, right, pivot);
QuickSort(A, left, pivot - 1);
QuickSort(A, pivot + 1, right);
}
}
Вот проблема:
pivot = rand() % (right - left + 1);
должно быть
pivot = left + rand() % (right - left + 1);
Других решений пока нет …