Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.78/9: Рейтинг темы: голосов - 9, средняя оценка - 4.78
0 / 0 / 0
Регистрация: 21.12.2017
Сообщений: 15
1

Сортировка массива по возрастанию методом слияния

13.09.2018, 05:00. Просмотров 1759. Ответов 1
Метки нет (Все метки)

Дан одномерный массив из n (n≤10^6) элементов a1,a2,…,an.(|ai|≤2×10^9). Сортировать по возрастанию методом слияния.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.09.2018, 05:00
Ответы с готовыми решениями:

Сортировка массива методом слияния
5. Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно...

Сортировка массива методом естественного двухпутевого слияния
Всем привет! Вот задали задачку такую, и что - то никак не могу алгоритм сортировки реализовать:...

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

Сортировка одномерного массива по возрастанию методом выбора
Привет. Пытаюсь сам-но написать сортировку выбором (кажется так называется). Не правильно в итоге...

1
Модератор
Эксперт С++
9788 / 8352 / 5087
Регистрация: 18.12.2011
Сообщений: 22,328
13.09.2018, 09:57 2
Лучший ответ Сообщение было отмечено Sangvuba как решение

Решение

Википедия
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
#include <algorithm>
#include <cstddef>
#include <iterator>
#include <memory>
 
template<typename T>
void merge_sort(T array[], std::size_t size) noexcept
{
    if (size > 1)
    {
        std::size_t const left_size = size / 2;
        std::size_t const right_size = size - left_size;
 
        merge_sort(&array[0], left_size);
        merge_sort(&array[left_size], right_size);
 
        std::size_t lidx = 0, ridx = left_size, idx = 0;
        std::unique_ptr<T[]> tmp_array(new T[size]);
 
        while (lidx < left_size || ridx < size)
        {
            if (array[lidx] < array[ridx])
            {
                tmp_array[idx++] = std::move(array[lidx]);
                lidx++;
            }
            else
            {
                tmp_array[idx++] = std::move(array[ridx]);
                ridx++;
            }
 
            if (lidx == left_size)
            {
                std::copy(std::make_move_iterator(&array[ridx]),
                          std::make_move_iterator(&array[size]),
                          &tmp_array[idx]);
                break;
            }
            if (ridx == size)
            {
                std::copy(std::make_move_iterator(&array[lidx]),
                          std::make_move_iterator(&array[left_size]),
                          &tmp_array[idx]);
                break;
            }
        }
 
        std::copy(std::make_move_iterator(tmp_array),
                  std::make_move_iterator(&tmp_array[size]),
                  array);
    }
}
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
/**
  * Сортирует массив, используя рекурсивную сортировку слиянием
  * up - указатель на массив, который нужно сортировать
  * down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер
  * left - левая граница массива, передайте 0, чтобы сортировать массив с начала
  * right - правая граница массива, передайте длину массива - 1, чтобы сортировать массив до последнего элемента
  * возвращает: указатель на отсортированный массив. Из-за особенностей работы данной реализации
  * отсортированная версия массива может оказаться либо в 'up', либо в 'down'
  **/
int* merge_sort(int *up, int *down, unsigned int left, unsigned int right)
{
    if (left == right)
    {
        down[left] = up[left];
        return down;
    }
 
    unsigned int middle = (left + right) / 2;
 
    // разделяй и властвуй
    int *l_buff = merge_sort(up, down, left, middle);
    int *r_buff = merge_sort(up, down, middle + 1, right);
 
    // слияние двух отсортированных половин
    int *target = l_buff == up ? down : up;
 
    unsigned int l_cur = left, r_cur = middle + 1;
    for (unsigned int i = left; i <= right; i++)
    {
        if (l_cur <= middle && r_cur <= right)
        {
            if (l_buff[l_cur] < r_buff[r_cur])
            {
                target[i] = l_buff[l_cur];
                l_cur++;
            }
            else
            {
                target[i] = r_buff[r_cur];
                r_cur++;
            }
        }
        else if (l_cur <= middle)
        {
            target[i] = l_buff[l_cur];
            l_cur++;
        }
        else
        {
            target[i] = r_buff[r_cur];
            r_cur++;
        }
    }
    return target;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.09.2018, 09:57

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Сортировка числового массива по возрастанию методом Шелла
Здравствуйте, форумчане. Помогите пожалуйста изменить программу. Есть аналогичная программа...

Сортировка списка методом слияния
Помогите пожалуйста сделать сортировку методом слияния. Очень выручите.... #include &lt;iostream&gt;...

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

Сортировка одномерного массива целых чисел по возрастанию методом быстрой сортировки
Написать программу для сортировки одномерного массива целых чисел по возрастанию методом быстрой...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.