Форум программистов, компьютерный форум CyberForum.ru

Алгоритм сортировки слиянием. Исправить ошибки в коде - C++

Восстановить пароль Регистрация
 
lowlol
2 / 2 / 2
Регистрация: 02.12.2012
Сообщений: 102
16.03.2014, 16:32     Алгоритм сортировки слиянием. Исправить ошибки в коде #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <time.h>
 
void merge(int array[], int left, int right, int n)
{
    int middle, start1, start2, j;
    
    int *tempArray = new int[n];
 
    middle = (left + right)/2;
    start1 = left;//начало левой части
    start2 = middle + 1;// начало второй части
    
    for( j = left; j <= right; j++)
    {
        if ((start1 <= middle) && ((start2 >= middle) || (array[start1] < array[start2])))
        {
            tempArray[j] = array[start1];
            start1++;
        }
        else
        {
            tempArray[j] = array[start2];
            start2++;
        }
 
        for(j = left; j <= right; j++)
        {
            array[j] = tempArray[j];
            delete[]tempArray;
        }
    }
 
}
 
void mergeSort(int array[], int left, int right, int n)
{
    if (left<right)
    {
        mergeSort(array, left, (left+right)/2, n); //сортировка левой части //от первого элемента до элемента посередине
        mergeSort(array, (left+right)/2+1, right, n); //сортировка правой части //от элемента (середина + 1) до последнего
        merge(array, left, right, n); //слияние двух частей
    }
}
 
void main()
{
    int n;
    std::cout << "enter scale of array " << std::endl;
    std::cin >> n;
    int *array = new int[n];
 
    srand(time(NULL));
 
    for(int i = 0; i < n; i++)
    {
        array[i] = rand()%100 + 1;
        std::cout << array[i] << ", ";
    }
 
    mergeSort(array, 1, n, n);
 
    for (int i = 0; i < n; i++)
    {
        std::cout << array[i] << ", ";
    }
 
    system("pause");
}
Подскажите, пожалуйста, почему ругается в функции merge. Конкретно при создании tempArray
Expression: _BLOCK_TYPE_IS_VALID(pHea->nBlockUse)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2014, 16:32     Алгоритм сортировки слиянием. Исправить ошибки в коде
Посмотрите здесь:

C++ Исправить ошибки в коде
C++ исправить ошибки в коде
исправить ошибки в коде C++
Исправить код, реализующий алгоритм сортировки C++
Ошибка в коде сортировки слиянием C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_Vertigo_
13 / 13 / 2
Регистрация: 07.09.2013
Сообщений: 158
Завершенные тесты: 1
16.03.2014, 21:05     Алгоритм сортировки слиянием. Исправить ошибки в коде #2
Кхм, попробуй лучше такой вариант реализации:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void Slivaem(int *a, int first, double middle, int last) {
  int pos1=first;
 
  int pos2=middle+1;
 
  int pos3=0;  
 
  int *temp = new int[last-first+1];
 
  // идет слияние, пока есть хоть один элемент в каждой последовательности
  while (pos1 <= middle && pos2 <= last) {
    if (a[pos1] < a[pos2])
      temp[pos3++] = a[pos1++];
    else
      temp[pos3++] = a[pos2++];
  }
 
  // одна последовательность закончилась - 
  // копировать остаток другой в конец буфера 
  while (pos2 <= last)   // пока вторая последовательность непуста 
    temp[pos3++] = a[pos2++];
  while (pos1 <= middle)  // пока первая последовательность непуста
    temp[pos3++] = a[pos1++];
 
  for (pos3 = 0; pos3 < last-first+1; pos3++)
    a[first+pos3] = temp[pos3];
 
  delete []temp;
}
void SortSlivaem(int *mas, int first, int last)
{
    double middle = 0;
if (first<last)
{
    middle = (first + last)/2;
SortSlivaem(mas, first, (first+last)/2); //сортируем левую часть
SortSlivaem(mas, (first+last)/2+1, last); //сортируем правую часть
Slivaem(mas, first, middle, last); //сливаем две части
}
}
Добавлено через 58 секунд
Ошибка в твоем коде, возможно, исправляется так:
int *tempArray = new int[right-left+1];
lowlol
2 / 2 / 2
Регистрация: 02.12.2012
Сообщений: 102
16.03.2014, 23:42  [ТС]     Алгоритм сортировки слиянием. Исправить ошибки в коде #3
_Vertigo_,
C++
1
2
3
4
5
for(j = left; j <= right; j++)
        {
            array[j] = tempArray[j];
            delete[]tempArray;
        }
вот тут ошибка была, удалял массив несколько раз де-факто

Добавлено через 2 часа 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <time.h>
 
using namespace std;
//функция, сливающая массивы
void Merge(int *A, int first, int last)
{
    int middle, start, final, j;
    int *mas=new int[last];
    middle=(first+last)/2; //вычисление среднего элемента
    start=first; //начало левой части
    final=middle+1; //начало правой части
    for(j=first; j<=last; j++) //выполнять от начала до конца
    {
        if ((start<=middle) && ((final>last) || (A[start]<A[final])))
        {
            mas[j]=A[start];
            start++;
        }
        else
        {
            mas[j]=A[final];
            final++;
        }
    }
//возвращение результата в список
    for (j=first; j<=last; j++) 
        {
            A[j]=mas[j];
        }
    //delete[]mas;
};
//рекурсивная процедура сортировки
void MergeSort(int *A, int first, int last)
{
    if (first<last)
    {
        MergeSort(A, first, (first+last)/2); //сортировка левой части
        MergeSort(A, (first+last)/2+1, last); //сортировка правой части
        Merge(A, first, last); //слияние двух частей
    }
};
//главная функция
void main()
{
    setlocale(LC_ALL, "Rus");
    int i, n;
    
    cout<<"Размер массива > "; cin>>n;
    int *A=new int[n];
 
    for (i=1; i<=n; i++)
    { 
        cout<<i<<" элемент > "; 
        cin>>A[i];
    }
 
    MergeSort(A, 1, n); //вызов сортирующей процедуры
    cout<<"Упорядоченный массив: "; //вывод упорядоченного массива
 
    for (i=1; i<=n; i++) 
        {
            cout<<A[i]<<" ";
        }
    delete []A;
    system("pause>>void");
}
в общем взял чужой код, но вставил динамический массив
ругается при создании массива mas
HEAP CORRUPTION DETECTED
кто-нибудь может подсказать в чем дело?
fishec
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
17.03.2014, 00:15     Алгоритм сортировки слиянием. Исправить ошибки в коде #4
У меня работает
Размер массива > 5
0 элемент > 4
1 элемент > 1
2 элемент > 0
3 элемент > 2
4 элемент > 3
Упорядоченный массив: 0 1 2 3 4

Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <time.h>
 
using namespace std;
//функция, сливающая массивы
void Merge(int *A, int first, int last)
{
    int middle, start, final, j;
    int *mas=new int[last];
    middle = (first + last) / 2; //вычисление среднего элемента
    start = first; //начало левой части
    final = middle + 1; //начало правой части
    for (j = first; j <= last; j++) //выполнять от начала до конца
    {
        if ((start <= middle) && ((final>last) || (A[start]<A[final])))
        {
            mas[j] = A[start];
            start++;
        }
        else
        {
            mas[j] = A[final];
            final++;
        }
    }
    //возвращение результата в список
    for (j = first; j <= last; j++)
    {
        A[j] = mas[j];
    }
    delete[]mas;
};
//рекурсивная процедура сортировки
void MergeSort(int *A, int first, int last)
{
    if (first<last)
    {
        MergeSort(A, first, (first + last) / 2); //сортировка левой части
        MergeSort(A, (first + last) / 2 + 1, last); //сортировка правой части
        Merge(A, first, last); //слияние двух частей
    }
};
//главная функция
int main()
{
    setlocale(LC_ALL, "Rus");
    int i, n;
 
    cout << "Размер массива > "; cin >> n;
    int *A = new int[n];
 
    for (i = 0; i < n; i++)
    {
        cout << i << " элемент > ";
        cin >> A[i];
    }
 
    MergeSort(A, 0, n-1); //вызов сортирующей процедуры
    cout << "Упорядоченный массив: "; //вывод упорядоченного массива
 
    for (i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    delete[]A;
    system("pause>>void");
}
lowlol
2 / 2 / 2
Регистрация: 02.12.2012
Сообщений: 102
17.03.2014, 12:46  [ТС]     Алгоритм сортировки слиянием. Исправить ошибки в коде #5
fishec, у меня тоже самое выводит в консоль, но сразу после вывода вылетает окно с ошибкой heap corruption detected и вариантами прерервать/повтор/пропустить

Добавлено через 56 секунд
fishec, а если разкомментить
C++
1
delete[]mas;
то тоже самое только без вывода упорядоченного массива
Alex5
881 / 616 / 81
Регистрация: 12.04.2010
Сообщений: 1,551
17.03.2014, 13:25     Алгоритм сортировки слиянием. Исправить ошибки в коде #6
Цитата Сообщение от lowlol Посмотреть сообщение
C++
1
int *mas=new int[last];
Число элементов массива равно last. Значит допустимые значения для индексов: 0, 1, 2, ..., last-1. (Нумерация начинается с 0.) А в функции может встретиться mas[last]=... , т.е. записывается значение за пределами выделенной области памяти.
lowlol
2 / 2 / 2
Регистрация: 02.12.2012
Сообщений: 102
17.03.2014, 13:30  [ТС]     Алгоритм сортировки слиянием. Исправить ошибки в коде #7
Alex5,
C++
1
int *mas=new int[last + 1];
так тоже heap corruption
C++
1
int *mas=new int[last + 10];
так тоже
Alex5
881 / 616 / 81
Регистрация: 12.04.2010
Сообщений: 1,551
17.03.2014, 14:12     Алгоритм сортировки слиянием. Исправить ошибки в коде #8
Цитата Сообщение от lowlol Посмотреть сообщение
так тоже
lowlol, проверьте индексы для других динамических массивов. Что насчёт A[] в функции main()?

Добавлено через 12 минут
C++
1
2
3
4
5
6
void Merge(int *A, int first, int last)
{
    int middle, start, final, j;
    int *mas=new int[last];
    // ...
    final = middle + 1; //начало правой части
Как это будет работать, когда first== last? А если и first, и last равны нулю?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2014, 14:25     Алгоритм сортировки слиянием. Исправить ошибки в коде
Еще ссылки по теме:

C++ Рекурсивный алгоритм для вычисления выражения. Исправить ошибки в коде
Исправить ошибки в коде C++
Исправить ошибки в коде C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lowlol
2 / 2 / 2
Регистрация: 02.12.2012
Сообщений: 102
17.03.2014, 14:25  [ТС]     Алгоритм сортировки слиянием. Исправить ошибки в коде #9
Alex5, с А[] все в норме.
я поставил брэйкпоинт на функции merge
Когда он проходит строчку создания массива mas он пишет в значении переменной "чтение памяти невозможно"
Yandex
Объявления
17.03.2014, 14:25     Алгоритм сортировки слиянием. Исправить ошибки в коде
Ответ Создать тему
Опции темы

Текущее время: 00:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru