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

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

10.08.2016, 14:08. Показов 6203. Ответов 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
19491 / 10097 / 2460
Регистрация: 30.01.2014
Сообщений: 17,805
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
19491 / 10097 / 2460
Регистрация: 30.01.2014
Сообщений: 17,805
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
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru