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

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

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

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

05.10.2013, 23:13. Просмотров 352. Ответов 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++
C++ Подскажите что не в моем коде(Сортировка слиянием)
C++ Сортировки слиянием с динамическим массивом
Пытаюсь реализовать сортировку слиянием (выскакивает ошибка) C++
C++ [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки
C++ Алгоритм сортировки слиянием. Исправить ошибки в коде
C++ может кто представить схему алгоритма сортировки слиянием?
C++ Внешние сортировки. Сортировка слиянием. Простое слияние
Внешние сортировки. Сортировка слиянием. Естественное слияние C++
C++ Объяснить, что происходит в условии if в коде сортировки
Найти причины возникновения ошибок в коде и исправить эти ошибки (классы, алгоритм сортировки) C++
C++ Ассемблерные вставки в C++. Алгоритм сортировки слиянием

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++
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     Ошибка в коде сортировки слиянием
Ответ Создать тему
Опции темы

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