0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 23
1

Сортировка массива методом естественного двухпутевого слияния

11.05.2018, 19:34. Показов 2944. Ответов 1
Метки нет (Все метки)

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

Вот задали задачку такую, и что - то никак не могу алгоритм сортировки реализовать:
Необходимо отсортировать массив, используя нерекурсивный метод слияний (естественный, с выделением серий в противоположных направлениях)

У меня есть вот такой код:
Кликните здесь для просмотра всего текста

C++ (Qt)
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
template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
    T* ret = new T[l1 + l2];
 
    int n = 0;
    while (l1 && l2) 
    {
        if (*m1 < *m2) 
        {
            ret[n] = *m1;
            ++m1;
            --l1;
        }
        else 
        {
            ret[n] = *m2;
            ++m2;
            --l2;
        }
        ++n;
    }
 
    if (l1 == 0) 
    {
        for (int i = 0; i < l2; ++i) {
            ret[n++] = *m2++;
        }
    }
    else 
    { 
        for (int i = 0; i < l1; ++i) 
        {
            ret[n++] = *m1++;
        }
    }
 
    return ret;
}
 
template <class T>
void mergesort(T * mas, int len)
{
    int n = 1, l, ost;
 
    T * mas1;
    while (n < len) 
    {
        l = 0;
        while (l < len) 
        {
            if (l + n >= len) 
                break;
            ost = (l + n * 2 > len) ? (len - (l + n)) : n;
            mas1 = merge(mas + l, mas + l + n, n, ost);
            for (int i = 0; i < n + ost; ++i)
                mas[l + i] = mas1[i];
            delete[] mas1;
            l += n * 2;
        }
        n *= 2;
    }
}

Алгоритм, вроде бы, реализован правильно, но нужно его немного изменить, чтобы серии брались с противоположных направлений.

Заранее спасибо, друзья!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.05.2018, 19:34
Ответы с готовыми решениями:

Сортировка массива по возрастанию методом слияния
Дан одномерный массив из n (n≤10^6) элементов a1,a2,…,an.(|ai|≤2×10^9). Сортировать по возрастанию...

Сортировка одномерного массива методом слияния с минимальным количеством сравнений
Доброе время суток господа программисты. Я полный чайник в программировании. Прошу помочь мне в...

Нисходящая сортировка методом слияния
Добрый день ребята!!! Мне нужно сделать нисходящею сортировку методом слияния! Я набросал...

Сортировка методом каскадного слияния со специальным распределением
Задание - реализовать этот алгоритм для однмоерного динамического массива. попытки почитать Кнута...

1
0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 23
19.05.2018, 19:16  [ТС] 2
Вот, нашел описание алгоритма по шагам, может, кто - то сможет реализовать? Заранее благодарен, ребят!)
Миниатюры
Сортировка массива методом естественного двухпутевого слияния  
0
19.05.2018, 19:16
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2018, 19:16
Помогаю со студенческими работами здесь

Реализовать шаблон сортировки массива методом слияния
Реализовать шаблон сортировки массива методом слияния.

Реализовать сортировку по росту (по убыванию) методом вставок и методом слияния
Добавлено через 1 час 27 минут ... Список лист заполняется экземплярами класса: void...

Сортировка слов текстового файла путём слияния данных из файла и заданного внутреннего массива
Здравствуйте. Имеется задание, которое я ни в коем случае не прошу за меня сделать. Мне...

Сортировка массива пузырьковым методом и методом вставки
нужно написать программу которая будет делать сортировку этими способами в массиве 3x10, две...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru