Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
1 / 1 / 3
Регистрация: 23.09.2014
Сообщений: 45
1

Сортировка одномерного массива методом слияния с минимальным количеством сравнений

26.09.2014, 16:09. Просмотров 2237. Ответов 2
Метки нет (Все метки)

Доброе время суток господа программисты. Я полный чайник в программировании. Прошу помочь мне в нелегком деле. Надо написать программу сортировки одномерного массива методом слияния с минимальным количеством сравнений. Определить сложность алгоритма и вычислить время выполнения алгоритма сортировки. Сформировать график зависимости времени выполнения алгоритма в зависимости от размера массива для сортировки. Максимальный размер массива 20000 элементов, шаг - 100 элементов. Кто шарит в теории алгоритмов помогите примером, литературой или советом.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.09.2014, 16:09
Ответы с готовыми решениями:

Сортировка массива с ограниченным количеством сравнений
Задача состоит в следуещем: " Ввести пять попарно различных целых чисел a, b, c, d, e....

Сортировка массива методом слияния
Ввести массив А. В массив В перенести все элементы массива А, стоящие правее максимального...

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

Сортировка массива строк методом слияния
Добрый день! Пожалуйста, нужна помощь! Совсем не понимаю как на ассемблере сделать Сортировку...

2
Модератор
Эксперт С++
9913 / 8436 / 5129
Регистрация: 18.12.2011
Сообщений: 22,581
26.09.2014, 18:29 2
Подскажите что не в моем коде(Сортировка слиянием)
Сортировка слиянием
Сортировка слиянием
1
1 / 1 / 3
Регистрация: 23.09.2014
Сообщений: 45
27.09.2014, 01:47  [ТС] 3
Лучший ответ Сообщение было отмечено Ziberman как решение

Решение

Уже не сплю 3 день, все мучаюсь с этой задачей. Вроде чет сделал но не знаю или правильно. Кто светила всех светил ? Правильно я намутил?
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
#include <iostream>
#include <conio.h>
 
using namespace std;
 
#define maxn 100
 
int a[maxn];
 
int n;
 
void merge(int l, int r) {
    if (r == l)
        return;
    if (r - l == 1) { 
        if (a[r] < a[l])
            swap(a[r], a[l]);
        return;
    }
    int m = (r + l) / 2;
    merge(l, m);
    merge(m + 1, r);
    int buf[maxn];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
        if (xl > m)
            buf[cur++] = a[xr++];
        else if (xr > r)
            buf[cur++] = a[xl++];
        else if (a[xl] > a[xr])
            buf[cur++] = a[xr++];
        else buf[cur++] = a[xl++];
 
    }
    for (int i = 0; i < cur; i++)
        a[i + l] = buf[i];
}
 
int main() {    
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    merge(0, n - 1);
 
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
 
    getch();
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.09.2014, 01:47

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

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

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

Сортировка массива методом Шейкера с выводом количества сравнений и обменом
Написал код для сортировки массива по Шейкеру. Мне еще нужно реализовать подсчет числа сравнений и...

Сортировка одномерного массива методом выбора
Сортировка одномерного массива методом выбора.для N=10,100, 1000,15000

Сортировка одномерного массива методом выбора
помогите пожалуйста с програмкой по одномерному массиву, где нужно произвести сортировку методом...

Сортировка одномерного массива методом выбора
Здравствуйте, подскажите кто может, по заданию мне нужно&quot;Сортировка выбором: отыскивается...


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

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

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