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

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

Восстановить пароль Регистрация
 
give_up
1 / 1 / 0
Регистрация: 17.03.2011
Сообщений: 42
05.10.2013, 23:13     Ошибка в коде сортировки слиянием #1
Вобщем, я реализовал рекурсивную сортировку слиянием (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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Сообщений: 42
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     Ошибка в коде сортировки слиянием
Ответ Создать тему
Опции темы

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