Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.76/29: Рейтинг темы: голосов - 29, средняя оценка - 4.76
Заблокирован

Реализация merge sort на C++14

10.08.2016, 14:08. Показов 6277. Ответов 15
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите найти (или покажите сами) профессиональную реализацию merge sort с использованием 14-го стандарта. Интернет завален только сишными выдристами типа того, что я сам написал. В лучшем случае в таких реалиазциях из интернета от C++ будет только std::cout.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void merge(int L[], int left_count, int R[], int right_count, int a[]){
    int i = 0, j = 0, k = 0;
 
    while(i < left_count && j < right_count){
        if(L[i] <= R[j])
            a[k] = L[i++];
        else
            a[k] = R[j++];
        k++;
    }
    if(i == left_count)
        memcpy(&a[k], &R[j], sizeof(R[0]) * (right_count - j));
    else
        memcpy(&a[k], &L[j], sizeof(L[0]) * (left_count - i));
}
 
void mergesort(int a[], int n){
    int i;
    int split = n / 2;
    int *L = (int *)malloc(split * sizeof(a[0]));
    int *R = (int *)malloc((n - split) * sizeof(a[0]));
 
    if(n > 1){
        for(i = 0; i < split; i++)
            L[i] = a[i];
        for(i = split; i < n; i++)
            R[i - split] = a[i];
        mergesort(L, split);
        mergesort(R, n - split);
        merge(L, split, R, n - split, a);
    }
    free(L);
    free(R);
}
 
int main(int argc, char *argv[]){
    int i;
    int v[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
 
    mergesort(v, 10);
 
    for(i = 0; i < 10; i++)
        printf("%d ", v[i]);
 
    scanf("%d", &i);
    return 0;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.08.2016, 14:08
Ответы с готовыми решениями:

Реализация Merge Sort, ошибка в объявлении массивов
Я пишу реализацию Merge Sort по псевдокоду, и у меня возникла ошибка при объявлении временных массивов &quot;выражение должно иметь...

Merge sort
Здравствуйте, пытаюсь написать сортировку по методу слияния (merge). не получается, подскажите пожалуйста в чем ошибка? void...

Merge sort
Было 100500 раз, знаю. Видел коды, но всеравно не понимаю. У меня есть класс Array. class Array { private: int *arr; public: ...

15
829 / 253 / 34
Регистрация: 27.07.2016
Сообщений: 497
Записей в блоге: 1
10.08.2016, 14:11
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
профессиональную реализацию merge sort с использованием 14-го стандарта
std::merge. Реализацию можете посмотреть в сорцах.
Причем здесь C++14 вообще не понятно. C++14 может помочь разве что в шаблонной реализации, но Ваша реализация не шаблонная и вообще C'ишная, так что здесь не то что C++14, а вообще C++ даже не в теме.
1
Заблокирован
10.08.2016, 14:17  [ТС]
но Ваша реализация не шаблонная и вообще C'ишная, так что здесь не то что C++14, а вообще C++ даже не в теме
Ну в том и проблема. Сделать из функции шаблон - только часть дела. Я вижу, что в профессиональном коде C++14 используется очень много новых конструкций, которые там к месту, я тоже хочу научиться так писать.
0
829 / 253 / 34
Регистрация: 27.07.2016
Сообщений: 497
Записей в блоге: 1
10.08.2016, 14:20
Только щас заметил, что у Вас там еще merge_sort, тогда реализация std::merge не поможет.

Добавлено через 2 минуты
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Сделать из функции шаблон - только часть дела.
В данном случае переделать под шаблон уже будет намного сложнее, чем изначально написать шаблонное.
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Я вижу, что в профессиональном коде C++14 используется очень много новых конструкций
Ну так сначала изучите зачем они нужны. Не везде нужно их пихать.
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
я тоже хочу научиться так писать.
Узнаете зачем они и что делают, а потом уже применяйте. А применение вслепую ничего хорошего не даст.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
10.08.2016, 14:20
Invoke Virtual, а вы с возможностями c++11 знакомы?
0
 Аватар для Voivoid
710 / 283 / 16
Регистрация: 31.03.2013
Сообщений: 1,340
10.08.2016, 14:21
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Помогите найти (или покажите сами) профессиональную реализацию merge sort с использованием 14-го стандарта
В c++14 не попали ranges, поэтому от нового стандарта при реализации данного алгоритма толку будет мало. Будет по сути вся та же возня с итераторами что и в c++03
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
10.08.2016, 14:22
Invoke Virtual,
И еще: потерпите годик, выйдет новый стандарт.
Как выйдет, так и пишите на нем, с++14 уже будет устаревшим)
0
Заблокирован
10.08.2016, 14:24  [ТС]
а вы с возможностями c++11 знакомы?
Да, я сейчас читаю книги Лимпана и Майерса о новых стандартах. Понимание "зачем это нужно" у меня пока что на том уровне, что применение новых конструкций требуется в задачах из книг.
0
829 / 253 / 34
Регистрация: 27.07.2016
Сообщений: 497
Записей в блоге: 1
10.08.2016, 14:25
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Майерса
ИМХО, читать Майерса нужно когда уже есть понимание что и зачем нужно.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
10.08.2016, 14:27
Invoke Virtual,
А Липпмана до какой страницы дошли? Просто я сейчас уже почти дочитываю его, уже второй месяц пошел с момента начала. Могу сказать, что читать его нужно очень и очень вдумчиво.
За неделю по нему не пробежишься. Читать надо не просто чтоб все понятно было, а так, чтобы прям в памяти все оседало после прочтения, а для этого надо перечитывать, и хотя бы пересказ ключевых моментов главы помнить после ее прочтения.
0
19500 / 10105 / 2461
Регистрация: 30.01.2014
Сообщений: 17,818
10.08.2016, 14:32
Лучший ответ Сообщение было отмечено gru74ik как решение

Решение

Цитата Сообщение от Invoke Virtual Посмотреть сообщение
В лучшем случае в таких реалиазциях из интернета от C++ будет только std::cout.
Просто не нужно использовать русский для запросов в поисковик.

https://en.wikibooks.org/wiki/... rt#C.2B.2B
1
Заблокирован
10.08.2016, 14:33  [ТС]
А Липпмана до какой страницы дошли?
До потоковых итераторов. Просто кроме этого я еще задачи из SICP решаю на схеме и читаю книгу по обработке сигналов.

Читать надо не просто чтоб все понятно было, а так, чтобы прям в памяти все оседало после прочтения
Вот это без практики сложно. А для написания небольших проектов еще не хватает знаний.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
10.08.2016, 14:35
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Вот это без практики сложно. А для написания небольших проектов еще не хватает знаний.
согласен, но это уже зависит от способностей человека, его памяти, поэтому и читаю как асфальтоукладчик, туда-сюда главу перечитываю
0
Заблокирован
10.08.2016, 14:36  [ТС]
Вроде, это не очень хорошая реализация, потому что const auto n = std::distance(first, last); делает O(n) итераций вместо вычисления разности.
0
19500 / 10105 / 2461
Регистрация: 30.01.2014
Сообщений: 17,818
10.08.2016, 14:43
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
Вроде, это не очень хорошая реализация, потому что const auto n = std::distance(first, last); делает O(n) итераций вместо вычисления разности.
Смотря на каком контейнере. На векторе будет O(1).
0
829 / 253 / 34
Регистрация: 27.07.2016
Сообщений: 497
Записей в блоге: 1
10.08.2016, 14:43
Цитата Сообщение от Invoke Virtual Посмотреть сообщение
делает O(n) итераций вместо вычисления разности.
Если итераторы произвольного доступа, то не делает, а если другие, то придется.
Так что каким образом Вы можете оценивать профессионализм и эффективность, если база у Вас шаткая?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.08.2016, 14:43
Помогаю со студенческими работами здесь

Merge Sort
написал реализацию Merge Sort но что то не так получилось))) помогите найти ошибку ) using namespace std; void Merge(int ,int ,int...

Merge Sort - Ошибка в коде
Всем привет, написал алгоритм сортировки слиянием, но работает он неправильно. Помогите найти ошибку в коде. Спасибо. К примеру при...

Сортировка слиянием (Merge sort)
Пожалуйста, помогите сортировать лист в C++ только надо именно слиянием отсортировать

Слияние массивов. Merge sort
Пытаюсь сделать сортировку больших обьемов данных. В моем случае файл с double числом в каждой новой строчке. Файл примерно весит 1гб....

Алгоритм сортировки In-place merge sort
Для здачи лабораторной нужно написать алгоритм сортировки vector и массивов любых типов данных(как пользовательских так и стандартных),...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 30.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru