Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
1

Нисходящая сортировка методом слияния

05.06.2016, 18:14. Просмотров 2060. Ответов 9
Метки нет (Все метки)

Добрый день ребята!!!

Мне нужно сделать нисходящею сортировку методом слияния!

Я набросал несколько строк для восходящий сортировки чтобы потом разобраться и поменять на нисходящей, но и с восходящий нечего не получается!!!

Вот строки которые я набросал ->

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
void TForm1::MergeSort(float data[99], int lend)
{
    if (lend > 1) {
        int middle = lend / 2;
        int rem = lend - middle;
        float* L = new float[middle];
        float* R = new float[rem];
        for (i = 0; i < lend; i++) {
            if (i < middle) {
                L[i] = data[i];
            }
            else {
                R[i-middle] = data[i];
            }
        }
        MergeSort(L, middle);
        MergeSort(R, rem);
        Merge(data, lend, L, middle, R, rem);
    }
}
//---------------------------------------------------------------------------
 
void TForm1::Merge(float merged[99], int lend, float L[99], int lenl, float R[99], int lenr)
{
    i = 0; j = 0;
    while (i < lenl || j < lenr)
    {
        if (i < lenl && j < lenr) {
            if (L[i] <= R[j]) {
                merged[i+j] = L[i];
                i++;
            }
            else {
                merged[i+j] = R[j];
                j++;
            }
        }
        else if (i < lenl) {
                merged[i+j] = L[i];
                i++;
             }
             else if (j < lenr) {
                    merged[i+j] = R[j];
                    j++;
                  }
 
    }
    DeleteFile("SortDist.txt");
    ofstream file;
    file.open("SortDist.txt");
    for (i = 0; i < k; i++) {
            file << merged[i] << "\n";
    }
    file.close();
}
 
 
 
//Вот как я её использую ->
 
void __fastcall TForm1::N6CrezfierulSortDisttxt1Click(TObject *Sender)
{
    Form1->Refresh();
    Form1->Inregistreaza();
    Form1->MergeSort(d, k);
}
 
// d -> массив который нужно сортировать
// k -> длинна массива
Нуждаюсь в помощи !!!

Файл SortDist выглядит примерно так ->
Код
0
0
0
0
0
0
0
0
Спасибо заранее
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.06.2016, 18:14
Ответы с готовыми решениями:

Нисходящая сортировка слиянием. Метод абстрактного обменного слияния
Добрый день, изучал различные сортировки и наткнулся на реализацию нисходящей сортировки слиянием....

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

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

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

9
248 / 199 / 96
Регистрация: 13.12.2015
Сообщений: 1,037
05.06.2016, 18:47 2
Цитата Сообщение от hackerbank Посмотреть сообщение
Мне нужно сделать нисходящею сортировку методом слияния!
сортировку чего? массивы, списки, деревья или еще более экзотические структуры?
вот вам и нисходящая и восходящая, и разные реализации - выбирайте сами.
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
-----
template <class Item>
void mergeAB(Item c[], Item a[], int N, 
                       Item 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++];
      }
  }
-----
template <class Item>
void merge(Item a[], int l, int m, int r)
  { int i, j;
    static Item aux[maxN];
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (int k = l; k <= r; k++)
       if (aux[j] < aux[i]) 
          a[k] = aux[j--]; else a[k] = aux[i++];
  }
-----
template <class Item>
void mergesort(Item a[], int l, int r)
  { if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);  
    mergesort(a, m+1, r);
    merge(a, l, m, r);
  }
-----
template <class Item>
void mergesortABr(Item a[], Item b[], int l, int r)
  { if (r-l <= 10) { insertion(a, l, r); return; }
    int m = (l+r)/2;
    mergesortABr(b, a, l, m);  
    mergesortABr(b, a, m+1, r);
    mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);
  }
template <class Item>
void mergesortAB(Item a[], int l, int r)
  { static Item aux[maxN];
    for (int i = l; i <= r; i++) aux[i] = a[i];
    mergesortABr(a, aux, l, r);
  }
-----
inline int min(int A, int B) 
  { return (A < B) ? A : B; }
template <class Item>
void mergesortBU(Item a[], int l, int r)
  {
    for (int m = 1; m <= r-l; m = m+m)
      for (int i = l; i <= r-m; i += m+m)
        merge(a, i, i+m-1, min(i+m+m-1, r));
  }
-----
link merge(link a, link b)
  { node dummy(0); link head = &dummy, c = head;
    while ((a != 0) && (b != 0))
      if (a->item < b->item)
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    c->next = (a == 0) ? b : a;
    return head->next;
  }
-----
link mergesort(link c)
  { 
    if (c == 0 || c->next == 0) return c;
    link a = c, b = c->next;
    while ((b != 0) && (b->next != 0))
      { c = c->next; b = b->next->next; }
    b = c->next; c->next = 0;
    return merge(mergesort(a), mergesort(b));
  }
-----
link mergesort(link t)
  { QUEUE<link> Q(max);
    if (t == 0 || t->next == 0) return t;
    for (link u = 0; t != 0; t = u) 
      { u = t->next; t->next = 0; Q.put(t); }
    t = Q.get();     
    while (!Q.empty())
      { Q.put(t); t = merge(Q.get(), Q.get()); }
    return t;
  }
0
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 18:52  [ТС] 3
Цитата Сообщение от SergioO Посмотреть сообщение
сортировку чего? массивы, списки, деревья или еще более экзотические структуры?
вот вам и нисходящая и восходящая, и разные реализации - выбирайте сами.
спасибо конечно но я хочу сделать сортировку одномерного массива именно через мой метод потому что я новичок и с трудом понял мой метод, а ваш мне не по зубам,извиняюсь но жду ответов!!!
0
248 / 199 / 96
Регистрация: 13.12.2015
Сообщений: 1,037
05.06.2016, 19:06 4
Лучший ответ Сообщение было отмечено hackerbank как решение

Решение

hackerbank, это похвально изобретать свой метод сортировки слиянием, но, уверен, что сначала надо ознакомиться с тем, что уже изобрели до нас, а потом можно и творить.
ваш вариант нисходящего слияния
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class Item>
void merge(Item a[], int l, int m, int r)
  { int i, j;
    static Item aux[maxN];
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (int k = l; k <= r; k++)
       if (aux[j] < aux[i]) 
          a[k] = aux[j--]; else a[k] = aux[i++];
  }
-----
template <class Item>
void mergesort(Item a[], int l, int r)
  { if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);  
    mergesort(a, m+1, r);
    merge(a, l, m, r);
  }
вместо Item ваш тип подставьте(я так понял числовой).
1
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 19:10  [ТС] 5
Цитата Сообщение от SergioO Посмотреть сообщение
ваш вариант нисходящего слияния

Не по теме:

извиняюсь за "тупой" вопрос : Исходный массив после сортировки это Item a[]?

0
248 / 199 / 96
Регистрация: 13.12.2015
Сообщений: 1,037
05.06.2016, 19:12 6
Лучший ответ Сообщение было отмечено hackerbank как решение

Решение

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 l, int m, int r)
  { int i, j;
    static int aux[maxN];
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (int k = l; k <= r; k++)
       if (aux[j] < aux[i]) 
          a[k] = aux[j--]; else a[k] = aux[i++];
  }
-----
 
void mergesort(int a[], int l, int r)// l - индекс начала сортировки, r - индекс конца. может не весь массив надо сортировать.
  { if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);  
    mergesort(a, m+1, r);
    merge(a, l, m, r);
}
 
int main(){
int a[1000] = {1, 2, 3, 4, ...};
mergesort(a, 0, 999)
}
дорабатывайте, либо можете дальше придумывать
1
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 23:02  [ТС] 7
SergioO, спасибо большое!!! всё ок !!!

Добавлено через 48 минут
ИSergioO, извиняюсь что снова вас беспокою у меня после выполнение цикла a[] всё равно имеет числа ровно = 0, я всё как вы показали делал! Но не получается!!!
0
248 / 199 / 96
Регистрация: 13.12.2015
Сообщений: 1,037
05.06.2016, 23:12 8
Цитата Сообщение от hackerbank Посмотреть сообщение
у меня после выполнение цикла
какого цикла? я ж рекурсивный вариант вам дал
0
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 23:32  [ТС] 9
SergioO, вы можете просто сказать в каком массиве из высших перечисленных хранится уже сортированные данные!!!

P.S думаю не имеет значение что я работаю в билдере?

Добавлено через 16 минут
если все данные хранятся в "a[]" тогда они просто как были так и остались!!!
я просто выводил данные на экране в цикл for и они по любому как были так и остались!!!

Не по теме:

сорри может быть за тупость но я прошу понимание потому что я новичок, вы тоже в своё время так были

0
248 / 199 / 96
Регистрация: 13.12.2015
Сообщений: 1,037
06.06.2016, 06:24 10
Цитата Сообщение от hackerbank Посмотреть сообщение
в каком массиве из высших перечисленных хранится уже сортированные данные
в том же самом массиве и хранится. создаете массив и передаете на него указатель, если вы не поняли.
Цитата Сообщение от hackerbank Посмотреть сообщение
сорри может быть за тупость но я прошу понимание потому что я новичок, вы тоже в своё время так были
разбирайтесь
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.06.2016, 06:24

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

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

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

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

Нисходящая сортировка слиянием. Двухпутевое слияние
Доброго времени суток, у меня возникла проблема, мне нужно написать функцию нисходящей сортировки...


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

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

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