2 / 2 / 2
Регистрация: 20.10.2016
Сообщений: 130
1

Нисходящая сортировка слиянием. Метод абстрактного обменного слияния

27.10.2017, 21:00. Показов 2724. Ответов 5
Метки нет (Все метки)

Добрый день, изучал различные сортировки и наткнулся на реализацию нисходящей сортировки слиянием. Метод слияния - абстрактный обменный.
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
#include<bits/stdc++.h>
 
void printArray(int *arr, int n) {
    int i;
    printf("[%d",arr[0]);
    for (i=1; i < n;i++) {
        printf(",%d",arr[i]);
    }
    printf("]\n");
}
 
void merge(int a[], int l, int m, int r)
  { int i, j;
    static int aux[16];
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (int k = l; k <= r; k++) {
        if (aux[i] > aux[j])
            a[k] = aux[j--];
        else
            a[k] = aux[i++];
    }
    printArray (aux, 16);
  }
 
void mergesort(int a[], int l, int r)
  { if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);
    mergesort(a, m+1, r);
    merge(a, l, m, r);
  }
 
 
int main()
{
    int a[] = {3, 7, 4, 8, 6, 2, 1, 5, 36, 18, 25, 34, 17, 14, 20, 29};
    mergesort(a, 0, 16-1);
}
Но, к сожалению, я не очень понимаю как работает этот метод слияния

Не могли бы вы прокомментировать данный код.
Конкретно вот эту функцию:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int a[], int l, int m, int r)
  { int i, j;
    static int aux[16];
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (int k = l; k <= r; k++) {
        if (aux[i] > aux[j])
            a[k] = aux[j--];
        else
            a[k] = aux[i++];
    }
    printArray (aux, 16);
  }
А то я немного путаюсь в этих циклах.

Заранее спасибо, очень благодарен вам.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.10.2017, 21:00
Ответы с готовыми решениями:

Сортировка слиянием. Метод абстрактного обменного слияния
Доброго времени суток, недавно начал разбираться с сортировкой слиянием, хотел бы освоить метод...

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

Нисходящая сортировка слиянием. Двухпутевое слияние
Доброго времени суток, у меня возникла проблема, мне нужно написать функцию нисходящей сортировки...

Сравнительный анализ Методов Сортировки(метод прямого выбора,метод слиянием,сортировка подсчетом)
Ввод данных: 1. с клавиатуры, 2.с файла (C:\Users\'NAME'\Desktop), 3.случайным образом количество...

5
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
27.10.2017, 23:45 2
Цитата Сообщение от EDWIN503 Посмотреть сообщение
static int aux[16];
Т.е. с помощью нее можно отсортировать максимум только 16 элементов?
Какая-то отстойная сортировка, найди себе что-нибудь получше.

Цитата Сообщение от EDWIN503 Посмотреть сообщение
нисходящей сортировки слиянием. Метод слияния - абстрактный обменный.
Столько слов, за которыми скрывается обычная классическая сортировка слиянием.
0
2 / 2 / 2
Регистрация: 20.10.2016
Сообщений: 130
27.10.2017, 23:50  [ТС] 3
nonedark2008, нет, не только 16, количество элементов равное 2 в n степени, конкретно в данной реализации, для примера взято 16 элементов, как мне кажется.
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
28.10.2017, 00:20 4
Цитата Сообщение от EDWIN503 Посмотреть сообщение
количество элементов равное 2 в n степени
Тут ты ошибаешься.
0
2 / 2 / 2
Регистрация: 20.10.2016
Сообщений: 130
28.10.2017, 19:06  [ТС] 5
nonedark2008, Не могли бы вы поправить меня, раз я ошибаюсь?

Добавлено через 5 часов 39 минут
Все еще нужна помощь, подскажите, что происходит в этих циклах, насколько я понимаю, именно там массив разбивается надвое и поочередно записывается в дополнительный массив aux. Я нигде не ошибся? Подскажите, где массив снова соединяется в один?
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
28.10.2017, 21:28 6
Лучший ответ Сообщение было отмечено EDWIN503 как решение

Решение

EDWIN503, твоя функция merge принимает указатель на массив, индекс начала его некоторого подмассива l, индекс конца r и индекс середины m.
Подразумевается, что подмассивы https://www.cyberforum.ru/cgi-bin/latex.cgi?l \dots m и https://www.cyberforum.ru/cgi-bin/latex.cgi?(m+1)\dots r отсортированы.
Задача merge собрать из двух отсортированных массивов собрать один.
Строки 4-5 копируют эти подмассивы в массив aux, при этом второй массив переворачивается (не знаю ачем так сделано).
После этого в строке 6 начинается цикл, который попарно сравнивает элементы обоих подмассивов, записанных в aux, и записывает их обратно в массив a согласно некоторому правилу. Оно очень простое, ты сам сможешь догадаться, если нарисуешь себе два отсортированных массива и попытаешься их объединить в один отсортированный.

Добавлено через 3 минуты
Цитата Сообщение от EDWIN503 Посмотреть сообщение
Не могли бы вы поправить меня, раз я ошибаюсь?
Если не учитывать массив aux, то алгоритм сортирует массивы произвольного размера.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2017, 21:28
Помогаю со студенческими работами здесь

Сортировка 2 массивов по возрастанию и используя метод слияния запись в другой массив
пожалуйста очень очень необходима задача ,если можно до завтрашних 9.00 Суть задачи 2...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким...

Из абстрактного в виртуальный метод
Помогите сделать met из абстрактного в виртуальный abstract class Graph { ...

Сортировка слиянием. трехленточная сортировка. считывание из файла
Сделал только без считывания из файла, как это сделать. Нужна помощь. У меня считывается с клавы и...


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

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

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