Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
give_up
1 / 1 / 0
Регистрация: 17.03.2011
Сообщений: 51
#1

Ошибка в коде сортировки слиянием - C++

05.10.2013, 23:13. Просмотров 373. Ответов 3
Метки нет (Все метки)

Вобщем, я реализовал рекурсивную сортировку слиянием (Merge Sort), но она работает за O(N), а должна за O(N log N), помогите найти ошибку в коде (a - исходный массив, N - количество элементов в нем)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(int *a, int *b, int *c, int Na, int Nb)
{   
    int i=0; int j=0;
    while (i<Na && j<Nb) {
        if (a[i]<=b[j]) {c[i+j]=a[i];i++;}
        else {c[i+j]=b[j];j++;}}
    while (i<Na) {c[i+j]=a[i];i++;}
    while (j<Nb) {c[i+j]=b[j];j++;} 
}
 
void sort(int *a, int N)
{   
    int i,c;
    if (N<2) return;
    if (N==2) {if (a[0]>a[1]) {c=a[0];a[0]=a[1];a[1]=c;} return;}
    sort(a,N/2);
    sort(a+N/2,N-N/2);
    int *b = (int*)malloc(sizeof(int) * N);
    merge(a,a+N/2,b,N/2,N-N/2);
    for (i = 0; i < N; i++) a[i]=b[i];
    free(b);
    return;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 23:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ошибка в коде сортировки слиянием (C++):

Алгоритм сортировки слиянием. Исправить ошибки в коде - C++
#include &lt;iostream&gt; #include &lt;time.h&gt; void merge(int array, int left, int right, int n) { int middle, start1, start2, j; ...

Сортировки слиянием с динамическим массивом - C++
Добрый вечер! мне нужно отсортировать массив слиянием с динамическим массивом помогите пожалуйста!!! массив #include &quot;stdafx.h&quot; ...

Ассемблерные вставки в C++. Алгоритм сортировки слиянием - C++
Нужна помощь.Необходимо реализовать алгоритм сортировки слиянием по возрастанию из элементов массивов, отсортированный по убыванию. Пишу в...

Внешние сортировки. Сортировка слиянием. Простое слияние - C++
Пом-гите решить, заранее благодарен.)) Билет 8 1 .Внешние сортировки. Сортировка слиянием. Простое слияние. 2 Решить задачу: ...

Внешние сортировки. Сортировка слиянием. Естественное слияние - C++
Пом-гите решить, заранее благодарен.)) Билет 9 1 .Внешние сортировки. Сортировка слиянием. Естественное слияние. 2 Решить...

может кто представить схему алгоритма сортировки слиянием? - C++
пожалуйстаааааа:cry:

3
Fyret
185 / 171 / 13
Регистрация: 30.07.2013
Сообщений: 359
05.10.2013, 23:34 #2
Откуда мысль, что работает за O(N)? На мой взгляд все правильно, и сложность алгоритма O(NlogN).

Не по теме:

Тема как бы в разделе C++.

C++
1
2
3
int* b = new int[N];
memcpy( b, a, sizeof(int)*N );
delete[] b;
не?

0
give_up
1 / 1 / 0
Регистрация: 17.03.2011
Сообщений: 51
05.10.2013, 23:43  [ТС] #3
Я проверял зависимость времени от количества элементов, от десяти до 2 000 000 000, и она получилась линейная(
Цитата Сообщение от give_up Посмотреть сообщение
for (i = 0; i < N; i++) a[i]=b[i];
Может здесь нужно
C++
1
for (i = N/2; i < N; i++) a[i]=b[i];
?

P.s. я думал malloc' и работают и в c++
0
Fyret
185 / 171 / 13
Регистрация: 30.07.2013
Сообщений: 359
05.10.2013, 23:59 #4
Если бы у Вас сортировка работала за линейное время, Вы бы порушили всю современную математику
Вы просто неточно измеряете время. На современном компьютере сортировка 10000 чисел занимает едва уловимые доли секунды, плюс константные издержки на запуск программы и выделение памяти. В общем, имеет смысл замерять времена от 10 секунд примерно.

Не по теме:

malloc-то в C++ есть, но это функция из C. В C++ есть оператор new.

0
05.10.2013, 23:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 23:59
Привет! Вот еще темы с ответами:

Реализуйте алгоритм сортировки слиянием применительно к односвязным спискам - C++
Реализуйте алгоритм сортировки слиянием применительно к односвязным спискам. Основные шаги алгоритма должна быть идентичным сортировке...

[Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки - C++
Добрый, на момент написания, день всем. Изучаю алгоритмы данных, дошёл до сортировки слиянием (Merge Sort). Прочитал, что для...

Подскажите что не в моем коде(Сортировка слиянием) - C++
Я не очень понимаю где именно неверно в моем коде. Хотел рассортировать массив методом слияния. Если найдете заранее спасибо! ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....


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

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

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