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

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

05.06.2016, 18:14. Просмотров 882. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 18:14
Ответы с готовыми решениями:

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

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

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

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

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

9
SergioO
168 / 184 / 90
Регистрация: 13.12.2015
Сообщений: 995
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
hackerbank
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 18:52  [ТС] 3
Цитата Сообщение от SergioO Посмотреть сообщение
сортировку чего? массивы, списки, деревья или еще более экзотические структуры?
вот вам и нисходящая и восходящая, и разные реализации - выбирайте сами.
спасибо конечно но я хочу сделать сортировку одномерного массива именно через мой метод потому что я новичок и с трудом понял мой метод, а ваш мне не по зубам,извиняюсь но жду ответов!!!
0
SergioO
168 / 184 / 90
Регистрация: 13.12.2015
Сообщений: 995
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
hackerbank
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 19:10  [ТС] 5
Цитата Сообщение от SergioO Посмотреть сообщение
ваш вариант нисходящего слияния

Не по теме:

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

0
SergioO
168 / 184 / 90
Регистрация: 13.12.2015
Сообщений: 995
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
hackerbank
-2 / 1 / 1
Регистрация: 25.03.2016
Сообщений: 44
05.06.2016, 23:02  [ТС] 7
SergioO, спасибо большое!!! всё ок !!!

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

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

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

Не по теме:

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

0
SergioO
168 / 184 / 90
Регистрация: 13.12.2015
Сообщений: 995
06.06.2016, 06:24 10
Цитата Сообщение от hackerbank Посмотреть сообщение
в каком массиве из высших перечисленных хранится уже сортированные данные
в том же самом массиве и хранится. создаете массив и передаете на него указатель, если вы не поняли.
Цитата Сообщение от hackerbank Посмотреть сообщение
сорри может быть за тупость но я прошу понимание потому что я новичок, вы тоже в своё время так были
разбирайтесь
0
06.06.2016, 06:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2016, 06:24

Алгоритм сортировки методом слияния
Напишите программу, реализующую алгоритм сортировки методом слияния и получите...

Сортировка посредством слияния списков
Помогите пожалуйста написать алгоритм сортировки посредством слияния списков

Реализовать шаблон сортировки массива методом слияния
Реализовать шаблон сортировки массива методом слияния.


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

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

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