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

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

Войти
Регистрация
Восстановить пароль
 
Snap_Suzun
Сообщений: n/a
#1

Сортировка методом прямого слияния (Merge Sort) - C++

28.04.2013, 18:28. Просмотров 840. Ответов 0
Метки нет (Все метки)

Всем доброго времени суток! Вообщем немогу разобраться с реализацией сортировки последовательностей. Загвоздка похоже в слияниях серий. Сам код:
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <conio.h>
#include <string.h>
using namespace std;
 
struct st
{
    
    char a[30];
    unsigned short int b;
    char c[10];
    char d[22];
};
struct RECORD_LIST:st{RECORD_LIST*next; RECORD_LIST *head; RECORD_LIST*tail;};
 
RECORD_LIST *create(void);
void rassheplenie(RECORD_LIST *S, RECORD_LIST *a, RECORD_LIST *b, int &n);
RECORD_LIST *sliyanie(RECORD_LIST *a, int q, RECORD_LIST *b, int r, RECORD_LIST *c);
void merge_sort(RECORD_LIST *S);
main()
{
    RECORD_LIST *head;
    head=create();
    merge_sort(head);
        system("pause");
    return 0;
}
void merge_sort(RECORD_LIST *S)
{
    int i, n, p, m, q, r;
    RECORD_LIST *a, *b, *c0, *c1, *h0, *h1;
    h0=c0=new RECORD_LIST;
    h1=c1=new RECORD_LIST;
    a=S;
    b=S->next;
    rassheplenie(S,a,b,n);
    p=1;
    while(p<n)
    {
        h0->next=NULL;
        h1->next=NULL;
        c0=h0;
        c1=h1;
        getch();
        i=0; m=n;
        while(m>0)
        {
            if(m>=p) q=p;
            else q=m;
            m=m-q;
            if(m>=p) r=p;
            else r=m;
            m=m-r;
            if(i==0)
             sliyanie(a,q,b,r,c0);
            else  
            sliyanie(a,q,b,r,c0);
           i=1-i;
        }
        a=h0->next;
        b=h1->next;
        p=p*2;
    }
    h0->next=NULL;
    S=h0;
}
 
void rassheplenie(RECORD_LIST *S, RECORD_LIST *k, RECORD_LIST *p, int &n)
{
    
    n=1;
    while(p!=NULL)
    {
        n=n+1;
        k->next=p->next;
        k=p;
        p=p->next;
    }
}
 
RECORD_LIST *sliyanie(RECORD_LIST *a, int q, RECORD_LIST *b, int r, RECORD_LIST *c)
{
    while(q!=0 && r!=0 && a->next!=NULL && b->next!=NULL)
    {
        if(strcmp(a->a,b->a)<=0)
        {
            c->next=a;
            c=a;
            a=a->next;
            q--;
            
        }
        else
        {
            c->next=b;
            c=b;
            b=b->next;
            r--;
        }
    }
    
    while(q>0 && a->next!=NULL)
    {
        c->next=a;
        c=a;
        a=a->next;
        q--;
    }
    while(r>0 && b->next!=NULL)
    {
        c->next=b;
        c=b;
        b=b->next;
        r--;
    }
    return c;
}
Очень прошу помочь. Заранее благодарен за ответы=)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2013, 18:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка методом прямого слияния (Merge Sort) (C++):

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

Нисходящая сортировка методом слияния - C++
Добрый день ребята!!! Мне нужно сделать нисходящею сортировку методом слияния! Я набросал несколько строк для восходящий...

Сортировка методом каскадного слияния со специальным распределением - C++
Задание - реализовать этот алгоритм для однмоерного динамического массива. попытки почитать Кнута успехом не увенчались - не понятно. Буду...

Сортировка методом прямого включения - C++
Даны n целых положительных двузначных чисел. Трактуя каждое число как пару цифр из интервала 0–9, отсортировать их (цифры) по возрастанию. ...

Сортировка методом прямого выбора - C++
Помогите пожалуйста! Есть код, но в конце сортировка сбивается. есть массив: A={1, 6, 9, 7, 2, 0, 4, 3, 5, 8} после выполнения моего...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2013, 18:28
Привет! Вот еще темы с ответами:

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

Merge sort - C++
Здравствуйте, пытаюсь написать сортировку по методу слияния (merge). не получается, подскажите пожалуйста в чем ошибка? void...

Сортировка массива методом прямого выбора - C++
Объясните пожалуйста как работает эта программа. Задание: Массив из 5 целых чисел заполнить с клавиатуры. Произвести сортировку...

Сортировка одномерного массива методом слияния с минимальным количеством сравнений - C++
Доброе время суток господа программисты. Я полный чайник в программировании. Прошу помочь мне в нелегком деле. Надо написать программу...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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