22
Май
2016

Сортировка слиянием без рекурсии

Функция сортирует массив экземпляров структуры contact по полю sname,для довольно больших массивов возникает проблема с переполнением стека из-за рекурсии в 5-6 строках. Как можно реализовать эту сортировку без использования рекурсии?

void MergeSort(contact* buf, int first, int last)
{
if (first >= last - 1) return;
int mid = (first + last) / 2;
MergeSort(buf, first, mid);
MergeSort(buf, mid, last);

contact * mas = new contact[last - first];
for (int i = first; i < last; ++i)
    mas[i - first] = buf[i];
int l = 0, r = mid - first;
for (int i = first; i < last; ++i)
{
    if (l == mid - first)
        buf[i] = mas[r++];
    else if (r == last - first)
        buf[i] = mas[l++];
    else if (strcmp(mas[l].sname, mas[r].sname) < 0)
        buf[i] = mas[l++];
    else
        buf[i] = mas[r++];
}
delete[] mas;
}

Источник: https://ru.stackoverflow.com/questions/526351/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0-%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC-%D0%B1%D0%B5%D0%B7-%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B8

Тебе может это понравится...

Добавить комментарий