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

Не работает сортировка в приведенном коде - C++

Восстановить пароль Регистрация
 
mmd
13 / 13 / 1
Регистрация: 17.05.2012
Сообщений: 80
01.11.2012, 09:59     Не работает сортировка в приведенном коде #1
что тут не так?


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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
using namespace std;
 
void en(int* a, int size);
void ex(int* a, int size);
void merge(int* a,int p,int q,int size);
void merge_sort(int* a,int p,int size);
 
int main(int argc, char *argv[])
{
    int* m;
    int size;
 
    cin >> size;
 
    m=new int[size];
 
    en(m,size);
    merge_sort(m,0,size-1);
    ex(m,size);
 
    delete [] m;
 
    return 0;
}
 
void en(int* a, int size)
{
    for(int i=0; i<size; ++i)
    {
        cin >> a[i];
    }
}
 
void ex(int* a, int size)
{
    for(int i=0; i<size; ++i)
    {
        cout << a[i] << " ";
    }
}
 
void merge(int* a,int p,int q,int size)
{
    int n1=q-p+1;
    int n2=size-q;
    int* L;
    int* R;
    L=new int[n1];
    R=new int[n2];
    for(int i=0;i<n1;i++)
    {
        L[i]=a[p+i-1];
    }
    for(int j=0;j<n2;j++)
    {
        R[j]=a[q+j];
    }
    int i=0;
    int j=0;
    for(int k=p;k<size;k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i=i+1;
        }
        else
        {
            a[k]=R[j];
            j=j+1;
        }
    }
    delete [] L;
    delete [] R;
}
 
void merge_sort(int* a,int p,int size)
{
    if(p<size-1)
    {
        int q=(p+size-1)/2;
        merge_sort(a,p,q);
        merge_sort(a,q+1,size-1);
        merge(a,p,q,size-1);
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2012, 09:59     Не работает сортировка в приведенном коде
Посмотрите здесь:

C++ Как работает функция "test" в приведенном коде
Найти ошибку в приведенном коде C++
Найти ошибку в приведенном коде C++
C++ Не правильно работает if в приведенном коде
Найти ошибку в приведенном коде C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
 Аватар для David Sylva
1280 / 942 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
01.11.2012, 10:08     Не работает сортировка в приведенном коде #2
Изложи суть задания
mmd
13 / 13 / 1
Регистрация: 17.05.2012
Сообщений: 80
01.11.2012, 10:18  [ТС]     Не работает сортировка в приведенном коде #3
нужно остортировать массив методом слияния
все компилируется, но странные результаты выдает
David Sylva
 Аватар для David Sylva
1280 / 942 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
01.11.2012, 10:46     Не работает сортировка в приведенном коде #4
Я не понимаю, какой у тебя конкретно алгоритм. Есть обычное так называемое двух путевое слияние,
абстрактное обменное слияние, нисходящая сортировка слиянием, восходящая сортировка слиянием. Ты какой вариант пытался реализовать?

Добавлено через 10 минут
Вот классический вариант слиянием двух упорядоченных последовательностей из учебника Сенджвика
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream> 
 
void mergeAB(int c[], int a[], int N, int b[], int M) 
{ 
    for ( int i = 0, j = 0, k = 0; k < N+M; k++) 
    { 
        if( i == N) { c[k] = b[j++]; continue; } 
        if( j == M) { c[k] = a[i++]; continue; } 
        c[k] = (a[i] < b[j]) ? a[i++]:b[j++]; 
    }
}
 
int main() 
{ 
    int a[5] = { 1, 2, 3, 4, 5 }; 
    int b[5] = { 6, 7, 8, 9, 10 }; 
    int c[10];
    mergeAB(c, a, 5, b, 5); 
 
    for ( int i = 0; i < 9; i++) 
        std::cout << c[i] << " "; 
    std::cout << std::endl;
}
mmd
13 / 13 / 1
Регистрация: 17.05.2012
Сообщений: 80
01.11.2012, 10:51  [ТС]     Не работает сортировка в приведенном коде #5
я из Кормена делал
David Sylva
 Аватар для David Sylva
1280 / 942 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
01.11.2012, 10:54     Не работает сортировка в приведенном коде #6
Цитата Сообщение от mmd Посмотреть сообщение
я из Кормена делал
Это известный автор, тогда алгоритм правильный, где-то перепутал какую-ту мелкую деталь, пересмотри код внимательно.
Yandex
Объявления
01.11.2012, 10:54     Не работает сортировка в приведенном коде
Ответ Создать тему
Опции темы

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