сортировка — c ++ ceil () в сортировке не работает

Question

сортировка — c ++ ceil () в сортировке не работает

Я осуществляю сортировку марионеток.

void stoogeSort(int arr[], int low, int high)
{
int size = high - low + 1;

if (size == 2 && arr[0] > arr[1])
{
int temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}

else if (size > 2)
{
int mid = (int) ceil((2 * size) / 3);
stoogeSort(arr, low, mid - 1);
stoogeSort(arr, size - mid, high);
stoogeSort(arr, low, mid - 1);
}
}

Кажется, есть проблема в int mid = (int) ceil((2 * size) / 3) как это не возвращает правильный номер. Например, если для размера задано значение 4, то в середине должно быть 3, поскольку потолок (2 * 4) / 3 равен 3. Однако он равен 2.

я имею #include <cmath> а также using std::ceil ниже этого. Независимо от того, какой тип преобразования я выполняю, он либо содержит неправильное число, либо заканчивает тем, что выдает ошибку переполнения стека в верхней части этой функции. Есть идеи? Спасибо!

ПРИМЕЧАНИЕ. Изменение значения 3 на 3,0 приводит к ошибке переполнения стека в верхней части функции.

0

c++ceil sorting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

int mid = (int) ceil((2 * size) / 3);

Вы делаете целочисленное деление и передаете результат ceil(), Следовательно ceil() звонок не имеет никакого эффекта.

Попробуйте что-то вроде этого:

int mid = ((2 * size) + 2) / 3;

Это не решит вашу реальную проблему. В вашем алгоритме есть несколько ошибок. Переходя к реализации в Википедия эта часть:

if (size == 2 && arr[0] > arr[1])
{
int temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}

должно быть что-то вроде этого:

if (arr[low] > arr[high])
{
std::swap(arr[low], arr[high]);
}

Эта часть :

else if (size > 2)

должно быть :

if (size > 2)

Это :

int mid = (int) ceil((2 * size) / 3);

должно быть :

int mid = size / 3;

и это :

stoogeSort(arr, low, mid - 1);
stoogeSort(arr, size - mid, high);
stoogeSort(arr, low, mid - 1);

должно быть:

stoogeSort(arr, low, high - mid);
stoogeSort(arr, low + mid, high);
stoogeSort(arr, low, high - mid);

Вы должны отметить, что mid не является индексом среднего элемента. Это размер, который вы добавляете к low или вычесть из high, Это может быть меньше, чем low, Отсюда и название mid вводит в заблуждение.

Сшивая все это вместе, вы получите это:

void stoogeSort(int arr[], int low, int high)
{
if (arr[low] > arr[high])
{
std::swap(arr[low], arr[high]);
}
int size = high - low + 1;
if (size > 2)
{
int mid = size / 3;
stoogeSort(arr, low, high - mid);
stoogeSort(arr, low + mid, high);
stoogeSort(arr, low, high - mid);
}
}

2