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

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

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

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

05.10.2013, 23:13. Просмотров 359. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 23:13     Ошибка в коде сортировки слиянием
Посмотрите здесь:

Алгоритм сортировки слиянием. Исправить ошибки в коде - 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++
Пом-гите решить, заранее благодарен.)) Билет 9 1 .Внешние сортировки. Сортировка слиянием. Естественное слияние. 2 Решить...

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 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;
не?

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++
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 23:59     Ошибка в коде сортировки слиянием
Еще ссылки по теме:

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

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

Объяснить, что происходит в условии if в коде сортировки - C++
Здравствуйте. Нужна ваша помощь Можете объяснить вторую строчку в коде. for (i = 0; i &lt; n; i++) if (arr != 0 &amp;&amp; abs(arr - 1) &gt;...

Пытаюсь реализовать сортировку слиянием (выскакивает ошибка) - C++
Пытаюсь реализовать сортировку слиянием. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &quot;windows.h&quot; #include &quot;math.h&quot; // m -...

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

Ошибка в алгоритме сортировки - C++
Пожалуйста укажите мне ошибку в реализуемом мною алгоритме сортировки #include &lt;iostream&gt; using namespace std; int main() ...


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

Или воспользуйтесь поиском по форуму:
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
05.10.2013, 23:59     Ошибка в коде сортировки слиянием #4
Если бы у Вас сортировка работала за линейное время, Вы бы порушили всю современную математику
Вы просто неточно измеряете время. На современном компьютере сортировка 10000 чисел занимает едва уловимые доли секунды, плюс константные издержки на запуск программы и выделение памяти. В общем, имеет смысл замерять времена от 10 секунд примерно.

Не по теме:

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

Yandex
Объявления
05.10.2013, 23:59     Ошибка в коде сортировки слиянием
Ответ Создать тему
Опции темы

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