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

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

25.02.2020, 15:39. Просмотров 2606. Ответов 15
Метки нет (Все метки)

5. Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно заполняется случайными числами. Добавить возможность предварительной сортировки начальных серий методом простой вставки. Провести статистические наблюдения над временем работы сортировки слиянием: без предварительной сортировки начальных серий; с отсортированными начальными сериями, размером 8, 16 элементов. Время подготовки начальных серий также учитывается при замере. Выбор варианта статистического наблюдения вводится с клавиатуры.

Можете обяснить суть работы и как его сделать??
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.02.2020, 15:39
Ответы с готовыми решениями:

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

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

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

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

15
4536 / 3049 / 1277
Регистрация: 07.05.2019
Сообщений: 9,395
Записей в блоге: 1
25.02.2020, 15:53 2
Цитата Сообщение от nurtyleu Посмотреть сообщение
Можете обяснить суть работы и как его сделать??
Что именно непонятно?
1
0 / 0 / 0
Регистрация: 05.11.2019
Сообщений: 23
25.02.2020, 16:07  [ТС] 3
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Что именно непонятно?
суть я вроде понел но как сделать поможете??
0
4536 / 3049 / 1277
Регистрация: 07.05.2019
Сообщений: 9,395
Записей в блоге: 1
25.02.2020, 16:10 4
Цитата Сообщение от nurtyleu Посмотреть сообщение
суть я вроде понел но как сделать поможете??
Сделай сначала хоть что-то. С сортировкой, думаю, проблем не будет - посмотри ссылки внизу страницы.
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
25.02.2020, 18:59 5
Структуры и алгоритмы обработки данных:
объектно-ориентированный подход и реализация на C++
Глава 2. Базовые алгоритмы
2.2. Сортировка и поиск в массивах
Автор : А.Кубенский
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
//-------------------------------------------------------------
// Шаблон insertSort задает функцию сортировки элементов
// массива методом простых вставок.
//   - Key - класс, задающий тип элементов массива;
//   - array - упорядочиваемый массив;
//   - low, high - индексы, задающие диапазон сортировки;
//-------------------------------------------------------------
 
template <class Key>
void insertSort(Key * array, int low, int high) {
  // Предполагается, что в начале работы low <= high
  // В результате сортировки получается упорядоченный фрагмент
  // массива в диапазоне от low до high
  for (int i = low+1; i <= high; i++) {
    // Уже упорядочен фрагмент массива от low до i-1
    // Сдвигаем элементы массива в сторону больших индексов,
    // пока не найдем элемент, меньший или равный array[i]
    Key temp = array[i];    // Копия вставляемого элемента
    int j;
    for (j = i-1; j >= low && array[j] > temp; j--) {
      array[j+1] = array[j];
    }
    // Вставляем элемент temp на свое место в массив
    array[j+1] = temp;
  }
}
0
0 / 0 / 0
Регистрация: 05.11.2019
Сообщений: 23
03.03.2020, 18:36  [ТС] 6
можете написать полный код программы
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
03.03.2020, 19:18 7
Лучший ответ Сообщение было отмечено nurtyleu как решение

Решение

Цитата Сообщение от nurtyleu Посмотреть сообщение
Массив предварительно заполняется случайными числами. Добавить возможность предварительной сортировки начальных серий методом простой вставки.
начало этой работы будет выглядеть так, оформление в стиле си или си++ уже далее сами решайте.
С предварительной сортировкой надеюсь разберетесь что и где изменить для этого. Ну дальше приделайте сортировку методом слияния и наблюдайте что да как

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/* Написать программу для сортировки одномерного массива целых чисел по возрастанию методом простой вставки. 
Размерность массива, а также границы диапазона изменения элементов N и M вводятся пользователем с клавиатуры, 
а сам массив заполняется случайными числами из указанного пользователем диапазона. 
Сортировку массива и генерацию массива оформить в виде отдельных функций.    
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
#include <malloc.h>
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
// Функция сортировки 
//-------------------------------------------------------------
// Шаблон insertSort задает функцию сортировки элементов
// массива методом простых вставок.
//   - Key - класс, задающий тип элементов массива;
//   - array - упорядочиваемый массив;
//   - low, high - индексы, задающие диапазон сортировки;
//-------------------------------------------------------------
 
template <class Key>
void insertSort(Key * array, int low, int high) {
  // Предполагается, что в начале работы low <= high
  // В результате сортировки получается упорядоченный фрагмент
  // массива в диапазоне от low до high
  for (int i = low+1; i <= high; i++) {
    // Уже упорядочен фрагмент массива от low до i-1
    // Сдвигаем элементы массива в сторону больших индексов,
    // пока не найдем элемент, меньший или равный array[i]
    Key temp = array[i];    // Копия вставляемого элемента
    int j;
    for (j = i-1; j >= low && array[j] > temp; j--) {
      array[j+1] = array[j];
    }
    // Вставляем элемент temp на свое место в массив
    array[j+1] = temp;
  }
}
int * creatArr( int size,int N, int M);     // прототип
void printArr( int *p, int size)
{
     for (int i = 0; i < size; ++i)
    {
        printf ("%i " ,*(p+i));
    }
        printf ("\n\n");
} 
 
int main()
{
    setlocale(LC_ALL, "Rus");
    srand(time(NULL));
    int * vec;
    int size,N,M;
    printf ( "Введите размер массива : ");
    scanf ("%i",&size);
    printf ( "Введите N : ");
    scanf ("%i",&N);
    printf ( "Введите M : ");
    scanf ("%i",&M);
    
    vec = creatArr( size,N,M );
    insertSort(vec,0,size);
    printArr(vec,size);
    
    free(vec);
    getchar();
    return 0;
}
 
int * creatArr( int size, int N, int M)
{
    int * p;
    const int Start = N;
    const int End = M;
 
    // Выделение памяти
    p =  (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; ++i)
    {
        p[i] = Start + rand() % (End-Start+1);       // целая часть [-101, 101]
       // p[i] += (rand() % 1000) / 1000.;  // дробная часть(3 знака) [000, 999]
        printf("%i ", p[i]);
    }
        printf ("\n\n");
    return p;   
}
1
0 / 0 / 0
Регистрация: 05.11.2019
Сообщений: 23
04.03.2020, 04:22  [ТС] 8
'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. вот такая ошибка
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
04.03.2020, 07:02 9
#define _CRT_SECURE_NO_WARNINGS
11 строчку можно убрать , от этого код не перестанет работать. Вам карты в руки перейти на cin, cout
0
бах-бах и в продакшен!
1692 / 1004 / 380
Регистрация: 23.09.2014
Сообщений: 3,239
Записей в блоге: 4
04.03.2020, 07:58 10
marat_miaki,
выход за верхнюю границу диапазона массива vec:
C++
1
    for (int i = low+1; i <= high; i++) {
нет такого элемента vec[i] с индексом i = high = size!
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
04.03.2020, 08:23 11
XLAT, ничего страшного, insertSort(vec,0,size-1) исправит положение? Тем более требуется не полная сортировка
0
бах-бах и в продакшен!
1692 / 1004 / 380
Регистрация: 23.09.2014
Сообщений: 3,239
Записей в блоге: 4
04.03.2020, 08:52 12
Цитата Сообщение от marat_miaki Посмотреть сообщение
insertSort(vec,0,size-1) исправит положение?
да тест проходит.

Цитата Сообщение от marat_miaki Посмотреть сообщение
ничего страшного
Кубенского жалко
0
0 / 0 / 0
Регистрация: 05.11.2019
Сообщений: 23
18.04.2020, 18:20  [ТС] 13
можете помочь с предварительной сортировки как это добавить?

Добавлено через 55 секунд
marat_miaki, можете помочь с предварительной сортировки как это добавить?
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
18.04.2020, 19:58 14
в чем проблема? Проблема использовать low, high - индексы, задающие диапазон сортировки
0
0 / 0 / 0
Регистрация: 05.11.2019
Сообщений: 23
19.04.2020, 19:24  [ТС] 15
Цитата Сообщение от marat_miaki Посмотреть сообщение
в чем проблема? Проблема использовать low, high - индексы, задающие диапазон сортировки
я не понимаю куда это добавить предварительный сортировку и как его там?
0
298 / 243 / 133
Регистрация: 08.04.2013
Сообщений: 1,066
19.04.2020, 20:38 16
Все что необходимо уже написано, начни с начала (прочти снова и снова)...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.04.2020, 20:38

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

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

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

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

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


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

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

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