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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.78
Chpoki
6 / 6 / 0
Регистрация: 02.12.2012
Сообщений: 44
#1

Merge sort - C++

09.10.2013, 00:50. Просмотров 4301. Ответов 3
Метки нет (Все метки)

Здравствуйте, пытаюсь написать сортировку по методу слияния (merge). не получается, подскажите пожалуйста в чем ошибка?
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
void merge_sort(int* A, int p,int r ,int q )
    {
        
        int n1,n2;
        n1 = q - p ;
        n2 = r - q;
        int  *L = new int [n1];
        int  *R = new int [n2];
 
        for (int i = 0 ; i <= n1; ++i)
            L[i] = A[i];
 
        for (int j = 0 ; j <= n2 ; ++j)
            R[j] = A[j + q+1];
        
 
 
        n1 = n2 = 1;
        for (int k = p; k < r; ++k)
        {
            
            if (L[n1] > R[n2] && n1 <l && n1 <k)
            {
                A[k] = L[n1];
                n1++;
            }
            else
            {
                A[k] = R[n2];
                n2++;
            }
        }
 
 
 
    }
    void merge(int *A,int p,int r){
        int q = 0;
        if (p < r && r !=13 )
        {
            q = (r + p)/2;
 
        merge(&A[0],p,q);
        merge(&A[0],q +1,r);
        merge_sort(&A[0],p,r,q);
        }
 
    }
 
    int main()
    {
        
        int p,r;
        int A[21] = {3,6,4,1,5,7,2,9,8,10,3,11,14,12,15,19,18,20,17,13,11};
            p = 0;
            r = (sizeof(A)/sizeof(int));
            merge(&A[0],p,r);
            for (int j = 0 ; j < r; j++)
                cout << A[j] << endl;
        }
Добавлено через 16 минут
23 строка:
C++
1
if (L[n1] > R[n2] )
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2013, 00:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Merge sort (C++):

Merge Sort - C++
написал реализацию Merge Sort но что то не так получилось))) помогите найти ошибку ) using namespace std; void Merge(int ,int ,int...

Merge sort - C++
Было 100500 раз, знаю. Видел коды, но всеравно не понимаю. У меня есть класс Array. class Array { private: int *arr; public: ...

Реализация merge sort на C++14 - C++
Помогите найти (или покажите сами) профессиональную реализацию merge sort с использованием 14-го стандарта. Интернет завален только сишными...

Сортировка слиянием (Merge sort) - C++
Пожалуйста, помогите сортировать лист в C++ только надо именно слиянием отсортировать

Алгоритм сортировки In-place merge sort - C++
Для здачи лабораторной нужно написать алгоритм сортировки vector и массивов любых типов данных(как пользовательских так и стандартных),...

Реализация Merge Sort, ошибка в объявлении массивов - C++
Я пишу реализацию Merge Sort по псевдокоду, и у меня возникла ошибка при объявлении временных массивов &quot;выражение должно иметь константное...

3
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
09.10.2013, 00:57 #2
Цитата Сообщение от Chpoki Посмотреть сообщение
if (L[n1] > R[n2] && n1 <l && n1 <k)
что такое l ?
0
Chpoki
6 / 6 / 0
Регистрация: 02.12.2012
Сообщений: 44
09.10.2013, 01:01  [ТС] #3
я добавил в конце:
Цитата Сообщение от Chpoki Посмотреть сообщение
23 строка:
Код C++
1
if (L[n1] > R[n2] )
0
TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
09.10.2013, 01:09 #4
Почитайте Т. Кормен, Ч. Лейзер "Алгоритмы" 2005г Москва. страници 72-78. Там понятно описано.
Вообще вот код:
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
#include <iostream>
 
void merge(int * AP,int p,int q,int r) {
    int n1=q-p+1;
    int n2=r-q;
    int * L; int * R;
    L=new int[n1+1];
    R=new int[n2+1];
    for(int i=1;i<=n1; i++) {
        L[i-1]=AP[p+i-1];
    }
    for(int j=1;j<=n2; j++) {
        R[j-1]=AP[q+j];
    }
    for(int i=0,j=0,k=p; k<=r; k++) {
        if(i<n1 && j<n2) {
            if(L[i]<=R[j]) {
                AP[k]=L[i];
                i++;
            } else {
                AP[k]=R[j];
                j++;
            }
        } else if(i<n1) {
            AP[k]=L[i];
            i++;
        } else {
            AP[k]=R[j];
            j++;
        }
    }
    delete [] L; delete [] R;
}
void merge_sort(int * AP,int p,int r) {
    int q;
    if(p<r) {
        q=(p+r)/2;
        merge_sort(AP,p,q);
        merge_sort(AP,q+1,r);
        merge(AP,p,q,r);
    }
}
 
 
void print(int * A,int size) {
    for(int i=0; i<size; i++)
        printf("%d ",A[i]);
    printf("\n");
}
 
int main() {
    //int arr[] = { 4,2,7,1,23,1,23,1 };
    int arr[] = { 3,6,4,1,5,7,2,9,8,10,3,11,14,12,15,19,18,20,17,13,11 };
 
    print(arr,sizeof(arr)/sizeof(int));
    merge_sort(arr,0,sizeof(arr)/sizeof(int)-1); printf("\n");
    print(arr,sizeof(arr)/sizeof(int));
 
    getchar();
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2013, 01:09
Привет! Вот еще темы с ответами:

Merge sort, сортирует не в том порядке что нужно - C++
Здравствуйте, подскажите пожалуйста, правильна ли в данном коде последовательность исполнения сортировки методом merge sort? Я пошагово...

Merge и сортировка - C++
Почему merge не сортирует массив в алфавитном порядке? c:

Не рабочий merge() - C++
Подскажите пожалуйста почему данная программа напрочь отказывается работать ? #include&lt;iostream&gt; #include&lt;algorithm&gt; using...

list.merge( - C++
// list_merge.cpp // compile with: /EHsc #include &quot;stdafx.h&quot; #include &lt;list&gt; #include &lt;iostream&gt; int main( ) { ...


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
09.10.2013, 01:09
Ответ Создать тему
Опции темы

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