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

@Mr_Progger · Регистрация: 01.11.2013

Студворк — интернет-сервис помощи студентам

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
70
void merg1(int* mas, int p, int q, int r)
{
    int size1 = p + q;
    int size2 = r - q + 1;
    int *mas1 = new int[size1];
    int *mas2 = new int[size2];
    int j = 0;
    for (size_t i = p; i < q; i++)
    {
        mas1[j] = mas[i];
        j++;
    }
    j = 0;
    for (size_t i = q; i < r + 1; i++)
    {
        mas2[j] = mas[i];
        j++;
    }
    int i = 0; 
    j = 0;
    for (size_t k = p; k <= r; k++)
    {
        if (mas1[i] <= mas2[j])
        {
            mas[k] = mas1[i];
            i++;
        }
        else
        {
            mas[k] = mas2[j];
            j++;
        }
    }
    delete mas1;
    delete mas2;
}
 
 
 
void merge_sort1(int* mas, int p, int r)
{
    if (p >= r)
        return;
    int q = (p + r) / 2;
    merge_sort1(mas, p, q);
    merge_sort1(mas, q + 1, r);
    merg1(mas, p, q, r);
}
 
 
 
int main()
{
    srand(time(NULL));
    const int n = 10;
    int mas[n];
    for (size_t i = 0; i < n; i++)
        mas[i] = rand() % 20 - 10;
    for (size_t i = 0; i < n; i++)
        std::cout << mas[i] << "  ";
    std::cout << std::endl;
 
    merge_sort1(mas, 0, 9);
 
    for (size_t i = 0; i < n; i++)
        std::cout << mas[i] << "  ";
    std::cout << std::endl;
    system("pause");
    return 0;
}

В результате выводит массив из огромных отрицательных чисел, причём всегда одних и тех же.

@Людвиг Бодмер · 06.11.2014, 10:36

Mr_Progger, а вариант кода с википедии не устраивает?:

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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <time.h>
#include <vector>              
template<typename Type>
void MergeSort(std::vector<Type>& buf, size_t l, size_t r)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    size_t m = (l + r) / 2;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, l, m);
    MergeSort(buf, m+1, r);
    merge(buf, l, r, m);
}
 
template<typename Type>
static void merge(std::vector<Type>& buf, size_t l, size_t r, size_t m)
{
    if (l >= r || m < l || m > r) return;
    if (r == l + 1 && buf[l] > buf[r]) {
        std::swap(buf[l], buf[r]);
        return;
    }
 
    std::vector<Type> tmp(&buf[l], &buf[l] + (r + 1));
 
    for (size_t i = l, j = 0, k = m - l + 1; i <= r; ++i) {
        if (j > m - l) {      
            buf[i] = tmp[k++];
        } else if(k > r - l) {
            buf[i] = tmp[j++];
        } else {
            buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
        }
    }
}
 
 
int main()
{
    srand(time(NULL));
    const int n = 10;
    std::vector<int> mas(n);
    for (size_t i = 0; i < n; i++)
        mas[i] = rand() % 20 - 10;
    for (size_t i = 0; i < n; i++)
        std::cout << mas[i] << "  ";
    std::cout << std::endl;
 
    MergeSort(mas, 0, 9);
 
    for (size_t i = 0; i < n; i++)
        std::cout << mas[i] << "  ";
    std::cout << std::endl;
    system("pause");
    return 0;
}

@Mr_Progger · 06.11.2014, 10:47 **[ТС]**

Людвиг Бодмер, не устраивает.

@Kuzia domovenok · 06.11.2014, 10:59

Mr_Progger, но почему? Где гарантии, что исправленная сортировка твоего кода устроит тебя? Может также откажешься от него без видимой причины?!

@TheCalligrapher · 06.11.2014, 12:02

Сообщение от Mr_Progger

В результате выводит массив из огромных отрицательных чисел, причём всегда одних и тех же.

А что показала пошаговая отладка?

В коде большое количество какой-то белиберды.

1. Согласно рекурсии, массив разбивается на подмассивы [p, q] и [q+1, r]. Однако внутри функции слияния 'merg1' первый подмассив берется из диапазона [p, q-1], а второй - из диапазона [q, r]. Что это??? Почему поменялись диапазоны?

Как следствие, в самом низу рекурсии первый подмассив получается размера 0. Тем не менее цикл слияния смело лезет в этот подмассив по индексу 0 и читает оттуда какой-то мусор. Отсюда и берутся странные негативные числа.

2. В цикле слияния вообще нет проверок индексов i и j на выход за пределы сливаемых подмассивов. А выход будет!

3. Почему выделение памяти под первый подмассив делается по размеру p+q? Откуда взялась такая сумма?

4. Память, выделенную через 'new[]' надо освобождать через 'delete[]', а не через 'delete'.

@Mr_Progger · 06.11.2014, 16:15 **[ТС]**

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
void merg1(int* mas, int p, int q, int r)
{
    int size1 = p + q + 1;
    int size2 = r - q;
    int *mas1 = new int[size1];
    int *mas2 = new int[size2];
    int j = 0;
    for (size_t i = p; i < q + 1; i++)
    {
        mas1[j] = mas[i];
        j++;
    }
    j = 0;
    for (size_t i = q + 1; i < r + 1; i++)
    {
        mas2[j] = mas[i];
        j++;
    }
    int i = 0;
    j = 0;
    for (size_t k = p; k <= r; k++)
    {
        if (mas1[i] <= mas2[j])
        {
            mas[k] = mas1[i];
            i++;
        }
        else
        {
            mas[k] = mas2[j];
            j++;
        }
    }
    delete []mas1;
    delete []mas2;
}

Теперь выводит два числа из изначального массива, остальные мусор.
TheCalligrapher, пункты 1,3,4 поправил. Как сделать проверку на выход i j за пределы сливаемых массивов? и как они могут выйти за пределы, ведь если массив сливаем то i++ или j++, если нет не увеличиваем, а перед заходом в цикл сливания i j обнуляем.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@Mr_Progger 24 / 24 / 16 Регистрация: 01.11.2013 Сообщений: 196
	06.11.2014, 10:47 [ТС]
	Людвиг Бодмер, не устраивает. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	06.11.2014, 10:59
	Mr_Progger, но почему? Где гарантии, что исправленная сортировка твоего кода устроит тебя? Может также откажешься от него без видимой причины?! 0