Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Merfes07
0 / 0 / 0
Регистрация: 02.10.2016
Сообщений: 108
1

Сортировка слиянием неправильно сортирует массив

13.04.2017, 20:43. Просмотров 191. Ответов 5
Метки нет (Все метки)

Есть программа сортировки слиянием. Она непонятным образом сортирует массив из 1000 элементов (или вообще этого не делает). Когда сортируется массив из 10 элементов они сортируются группами, то есть так 1 2 3 0 1 2 3. По три элемента короче. Как исправить?

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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <ctime>
 
using namespace std;
 
void merge(int *a, int n)
{
  int mid = n / 2; 
  if (n % 2 == 1)
    mid++;
  int h = 1; 
  
  int *c = (int*)malloc(n * sizeof(int));
  int step;
  while (h < n) 
  {
    step = h;
    int i = 0;   
    int j = mid; 
    int k = 0;   
    while (step <= mid) 
    {
      while ((i < step) && (j < n) && (j < (mid + step))) 
      { 
        
        
        if (a[i] < a[j])  
        {
          c[k] = a[i];
          i++; k++;
        }
        else {
          c[k] = a[j];
          j++; k++;
        }
      }
      while (i < step) 
      { 
        c[k] = a[i];
        i++; k++;
      }
      while ((j < (mid + step)) && (j<n)) 
      {  
        c[k] = a[j];
        j++; k++;
      }
      step = step + h; 
    }
    h = h * 2;
    
    for (i = 0; i<n; i++)
      a[i] = c[i];
  }
}
int main() 
{
    clock_t t;
    int n;
    cin >> n;
  int *a = new int[n];
  
  for (int i = 0; i<n; i++)
    a[i] = rand() % 100;
  
  t = clock();
  for (int i = 0; i<n; i++)
    printf("%d ", a[i]);
  printf("\n");
  merge(a, n);
   
 
  for (int i = 0; i<n; i++)
    printf("%d ", a[i]);
    t = clock () - t;
  printf("\n");
  cout << "\n" << t;
  getchar();
  return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2017, 20:43
Ответы с готовыми решениями:

Неправильно работает сортировка слиянием
Всем привет!!! Пытаюсь реализовать алгоритм по книге , там псевдокод, я...

Неправильно сортирует массив методом вставки
#include &lt;iostream&gt; #include &lt;cstdlib&gt; using namespace std; int main() {...

Отсортируйте каждый нечётный столбец массива по возрастанию (неправильно сортирует массив)
Объявите двумерный вещественный массив, в котором n x m элементов. Отсортируйте...

Быстрая сортировка не сортирует весь массив
Программа быстрой сортировки сортирует только первые 10 элементов, остальная...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит...

5
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
14.04.2017, 09:26 2
Для примера я взял массив из 5 элементов.
Цитата Сообщение от Merfes07 Посмотреть сообщение
C++
1
2
3
4
int mid = n / 2; 
if(n % 2 == 1)
* * mid++;
int h = 1;
- если верить Википедии, то вначале сортировки слиянием определяется номер половины этого массива. Т.е. mid = 2 и его не надо увеличивать на 1 после деления на 2.
Ссылка на Википедию:
https://ru.wikipedia.org/wiki/Сортировка_слиянием.
Этот код даже работает. Я даже проверял по-моему.
Возьмите готовый код с Википедии, чтобы долго не мучиться.

Добавлено через 1 минуту
Кстати, это рекурсивная сортировка, а что-то у Вас никакой рекурсии я не вижу.
0
Ferrari F1
793 / 522 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
Завершенные тесты: 1
14.04.2017, 09:41 3
Демолитион мен верно говорит
1
Merfes07
0 / 0 / 0
Регистрация: 02.10.2016
Сообщений: 108
14.04.2017, 23:04  [ТС] 4
Не получается

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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <ctime>
 
using namespace std;
 
template<typename T>
void MergeSort(T a[], size_t l)
{
    size_t BlockSizeIterator;
    size_t BlockIterator;
    size_t LeftBlockIterator;
    size_t RightBlockIterator;
    size_t MergeIterator;
 
    size_t LeftBorder;
    size_t MidBorder;
    size_t RightBorder;
    for (BlockSizeIterator = 1; BlockSizeIterator < l; BlockSizeIterator *= 2)
    {
        for (BlockIterator = 0; BlockIterator < l - BlockSizeIterator; BlockIterator += 2 * BlockSizeIterator)
        {
            //Ïðîèçâîäèì ñëèÿГ*ГЁГҐ Г± ñîðòèðîâêîé ГЇГ*ðû áëîêîâ Г*Г*Г·ГЁГ*Г*ГѕГ№ГіГѕГ±Гї Г± ýëåìåГ*ГІГ* BlockIterator
            //ëåâûé Г°Г*çìåðîì BlockSizeIterator, ГЇГ°Г*âûé Г°Г*çìåðîì BlockSizeIterator èëè ìåГ*ГјГёГҐ
            LeftBlockIterator = 0;
            RightBlockIterator = 0;
            LeftBorder = BlockIterator;
            MidBorder = BlockIterator + BlockSizeIterator;
            RightBorder = BlockIterator + 2 * BlockSizeIterator;
            RightBorder = (RightBorder < l) ? RightBorder : l;
            int* SortedBlock = new int[RightBorder - LeftBorder];
 
            //ÏîêГ* Гў îáîèõ Г¬Г*Г±Г±ГЁГўГ*Гµ ГҐГ±ГІГј ýëåìåГ*ГІГ» âûáèðГ*ГҐГ¬ ìåГ*ГјГёГЁГ© ГЁГ§ Г*ГЁГµ ГЁ Г§Г*Г*îñèì Гў îòñîðòèðîâГ*Г*Г*ûé áëîê
            while (LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder)
            {
                if (a[LeftBorder + LeftBlockIterator] < a[MidBorder + RightBlockIterator])
                {
                    SortedBlock[LeftBlockIterator + RightBlockIterator] = a[LeftBorder + LeftBlockIterator];
                    LeftBlockIterator += 1;
                }
                else
                {
                    SortedBlock[LeftBlockIterator + RightBlockIterator] = a[MidBorder + RightBlockIterator];
                    RightBlockIterator += 1;
                }
            }
            //Ïîñëå ýòîãî Г§Г*Г*îñèì îñòГ*ГўГёГЁГҐГ±Гї ýëåìåГ*ГІГ» ГЁГ§ ëåâîãî èëè ГЇГ°Г*âîãî áëîêГ*
            while (LeftBorder + LeftBlockIterator < MidBorder)
            {
                SortedBlock[LeftBlockIterator + RightBlockIterator] = a[LeftBorder + LeftBlockIterator];
                LeftBlockIterator += 1;
            }
            while (MidBorder + RightBlockIterator < RightBorder)
            {
                SortedBlock[LeftBlockIterator + RightBlockIterator] = a[MidBorder + RightBlockIterator];
                RightBlockIterator += 1;
            }
 
            for (MergeIterator = 0; MergeIterator < LeftBlockIterator + RightBlockIterator; MergeIterator++)
            {
                a[LeftBorder + MergeIterator] = SortedBlock[MergeIterator];
            }
            delete SortedBlock;
        }
    }
}
int main() 
{
    clock_t t;
    int n;
    cin >> n;
  int *a = new int[n];
  
  for (int i = 0; i<n; i++)
    a[i] = rand() % 100;
  
  t = clock();
  for (int i = 0; i<n; i++)
    printf("%d ", a[i]);
  printf("\n");
  merge(a, n);
   
 
  for (int i = 0; i<n; i++)
    printf("%d ", a[i]);
    t = clock () - t;
  printf("\n");
  cout << "\n" << t;
  getchar();
  return 0;
}
0
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
15.04.2017, 09:35 5
Я же Вам сказал, возьмите с Википедии и не мучайтесь.
0
Merfes07
0 / 0 / 0
Регистрация: 02.10.2016
Сообщений: 108
15.04.2017, 16:58  [ТС] 6
так я взял
0
15.04.2017, 16:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.04.2017, 16:58

сортировка не сортирует
нужно сортировать по году рождения не сортирует туплю #include &lt;iostream&gt;...

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма...

Шейкерная сортировка + сортировка слиянием
вот часть когда,которая выполняет шейкерную сортировку : для символьного и...


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

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

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