2

Возникла проблема в программе сортировки слиянием. Исходный массив, заполненный случайными числами, "разбивается" на два подмассива, каждый из которых сортируется отдельно(если в исходном массиве более 5000 элементов, то используется сортировка выбором, если меньше - гномья сортировка) и потом они сливаются в результирующий массив. Проблема заключается в том, что если задать длину массива больше 128 000, то программа вылетает.

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

int main()
{
const int length = 128000;
int arr1[length];
int i;

for (i = 0; i<length; i++)
{
    arr1[i] = (rand() % 99)+1;
    cout << arr1[i] << " ";
}

int counter1, counter2, counter3; //array's counters

counter1 = 0; //не больше (length-2)/2
counter2 = length / 2; //не больше length-1
counter3 = 0; //не больше length-1

if (length>5000)
{   
    int j, k;
    int number;//the number of the maximum element
    int maximum;//the maximum element

    for (j = counter1; j <= (length - 2) / 2; j++)
    {
        maximum = arr1[j];
        number = j;
        for (k = j + 1; k <= (length - 2) / 2 - 1; k++)
        {
            if (maximum>arr1[k])
            {
                maximum = arr1[k];
                number = k;
            }
        }
        swap(arr1[j], arr1[number]);
    }

    for (j = counter2; j <= length - 2; j++)
    {
        maximum = arr1[j];
        number = j;

        for (k = j + 1; k <= length - 1; k++)
        {
            if (maximum>arr1[k])
            {
                maximum = arr1[k];
                number = k;
            }
        }
        swap(arr1[j], arr1[number]);
    }
}
else
{
    int j = counter1;

    while (j<(length - 2) / 2 + 1)
    {
        if (j == 0 || arr1[j - 1] <= arr1[j])
            j++;
        else
        {
            swap(arr1[j], arr1[j - 1]);
            j--;
        }
    }

    int k = counter2;

    while (k<length)
    {
        if (k == 0 || arr1[k - 1] <= arr1[k])
            k++;
        else
        {
            swap(arr1[k], arr1[k - 1]);
            k--;
        }
    }
}

int arr2[length];
int l;

while (counter3 != length)
{
    if (arr1[counter1] <= arr1[counter2])
    {
        arr2[counter3] = arr1[counter1];
        counter1++;
        if (counter1 == (length - 2) / 2 + 1)
        {
            counter3++;
            for (l = counter2; l <= length - 1; l++)
            {
                arr2[counter3] = arr1[l];
                counter3++;
            }
            break;
        }
    }

    else
    {
        arr2[counter3] = arr1[counter2];
        counter2++;
        if (counter2 == length)
        {
            counter3++;
            for (l = counter1; l <= (length - 2) / 2; l++)
            {
                arr2[counter3] = arr1[l];
                counter3++;
            }
            break;
        }
    }
    counter3++;
}

int s;

cout << "\n";

for (s = 0; s <= length - 1; s++)
    cout<< arr2[s];
return 0;

}

1

1 ответ 1

5

Краткий ответ - 128000*4 = а это пол мегабайта.

Ваш массив выделяется на стеке, а стек в большинстве современных систем - обычно не больше 1 мегабайта на поток. Хотите больше - используйте std::vector<int>.

Очень похоже, что заменив строку

int arr1[length];

на

std::vector<int> arr1(length);

и добавив в самый верх #include <vector>, все будет работать.

Но можно конечно выделять память через malloc/new. Но это и не модно, и требует существенной переделки программы.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.