Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Snap_Suzun
1

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

28.04.2013, 18:28. Просмотров 1542. Ответов 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;
}
Очень прошу помочь. Заранее благодарен за ответы=)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.04.2013, 18:28
Ответы с готовыми решениями:

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

Сортировка массива методом слияния
5. Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно...

Сортировка списка методом слияния
Помогите пожалуйста сделать сортировку методом слияния. Очень выручите.... #include &lt;iostream&gt;...

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.04.2013, 18:28

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Сортировка массива по возрастанию методом слияния
Дан одномерный массив из n (n≤10^6) элементов a1,a2,…,an.(|ai|≤2×10^9). Сортировать по возрастанию...

Сортировка массива методом естественного двухпутевого слияния
Всем привет! Вот задали задачку такую, и что - то никак не могу алгоритм сортировки реализовать:...

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

Сортировка методом прямого выбора
Есть массив структур, который нужно в отдельности отсортировать методом прямого выбора по всем...


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

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

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