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

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

Войти
Регистрация
Восстановить пароль
 
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
#1

Сортировка Шелла и вставок - C++

15.10.2013, 02:45. Просмотров 230. Ответов 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
 // 3. Метод вставки
   copy_array(a_result,aa,n,m);
   sravnenij=perestanovok=0;
   
for (int k=0;k<n;k++)            
{ 
CopyNechetFromArray(a,a_result[k],m);    //
  
   for (i=1;i<len;i++)
   {
      int k=a[i]; 
      int j=i-1;                           
      while (k<a[j])
      {
         sravnenij++;
         j--;
         if (j<=-1)// это значит, что нужно вставить в самое начало;     
         {
         sravnenij--;
         }
      }
      sravnenij++;
      if (j>=-1&&j!=i-1) // если вставку требуется осуществить:
      {
         // сдвигаем все элементы от места вставки (j) до положения k (i) вправо на 1 элемент:
         for (int l=i-1;l>=j+1;l--)
         {
            a[l+1]=a[l];
            perestanovok++;
         }
         // вставляем сам элемент k в массив a в позицию j+1 (это место как раз освободилось после смещения элементов вправо):
         a[j+1]=k;
       
      }
   }
CopyNechetToArray(a_result[k],a,m);
}
   
   cout<<endl<<endl<<"3. Metod vstavki"<<endl;
   cout<<endl<<"Unsorted array: "<<endl<<endl;
   ShowArray(aa,n,m);
   cout<<endl<<"Sorted array:"<<endl<<endl;
   ShowArray(a_result,n,m);
   cout<<endl<<"   perestanovok done: "<<perestanovok<<endl;
   cout<<"   Comparings done: "<<sravnenij<<endl;
   _getch();   
   
// Метод Шелла:
   copy_array(a_result,aa,n,m);
   sravnenij=perestanovok=0;
 
   const int mclen=9;
   const int mc[mclen]={1,4,10,23,57,132,301,701,1750}; 
   
for (int k=0;k<n;k++)
{
CopyNechetFromArray(a,a_result[k],m);
   // перемещаемся по mc[] сверху до тех пор, пока не найдём первый элемент, который будет по размеру меньше или равен размеру массива минус один:
   int mc_index=mclen-1;
   while (mc[mc_index]>len-1)
   {
      mc_index--;
   }
   // теперь работаем методом вставки до тех пор, пока не дойдём до шага 1, то есть пока mc_index не равен 0:   8 15 6 10 2 11 13 12 6 0
   while (mc_index>=0)
   {
      for (i=mc[mc_index];i<len;i+=mc[mc_index])
      {
         int k=a[i];
         int j=i-mc[mc_index];
         while (k<a[j])
         {
            sravnenij++;
            j-=mc[mc_index];
            if (j<=-mc[mc_index])// это значит, что нужно вставить в самое начало;
            {
             sravnenij--;
            }
         }
         sravnenij++;
 
         if (j>=-mc[mc_index]&&j!=i-mc[mc_index]) // если вставку требуется осуществить:
         {
            // сдвигаем все элементы от места вставки (j) до положения k (i) вправо на 1 элемент:
            for (int l=i-mc[mc_index];l>=j+mc[mc_index];l-=mc[mc_index])
            {
               a[l+mc[mc_index]]=a[l];
               perestanovok++;
            }
            // вставляем сам элемент k в массив a в позицию j+1 (это место как раз освободилось после смещения элементов вправо):
            a[j+mc[mc_index]]=k;
        
         }
      }
      mc_index--;
   }
 
CopyNechetToArray(a_result[k],a,m);
}
   
   cout<<endl<<endl<<"4. Metod Shella"<<endl;
   cout<<endl<<"Unsorted array: "<<endl<<endl;
   ShowArray(aa,n,m);
   cout<<endl<<"Sorted array:"<<endl<<endl;
   ShowArray(a_result,n,m);
   cout<<endl<<"   Reversings done: "<<perestanovok<<endl;
   cout<<"   Comparings done: "<<sravnenij<<endl;
   getch();
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2013, 02:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка Шелла и вставок (C++):

Сортировка диагоналей матрицы методом Шелла/вставок - C++
Дана матрица размерностью n*n, содержащая целые числа. Отсортировать диагонали матрицы, параллельные побочной, по возрастанию элементов...

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

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

Сортировка методом вставок - C++
Заполнить массив размером 20 случайными числами в диапазоне от 0 до 200. Во второй массив выбрать все двузначные элементы, отсортировать...

Сортировка методом вставок - C++
Заполнить массив размером 20 случайными числами в диапазоне от 0 до 200. Во второй массив выбрать все двузначные элементы, отсортированные...

Сортировка методом Вставок - C++
Вот собственно вопрос. Масив записей структура которого конечная остановка, и время прибытия, нужно посортировать по направлению. ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.10.2013, 02:45
Привет! Вот еще темы с ответами:

Сортировка методом простых вставок - C++
Сортировка методом простых вставок - алгоритм S с. Вычисление трудоемкости Замер времени для отсортированного массива, отсортированного в...

Сортировка методом центрированных вставок - C++
Доброго времени суток. Помоги доделать программу. Я решил сделать эту сортировку через массивы(возможно зря)). И теперь, допусти если у...

Сортировка списка методом простых вставок - C++
Помогите сделать чтобы в программе были двусвязные списки и чтобы списки из файла выводились в нормальном порядке (как в файлах), а не с...

Пирамидальная сортировка и сортировка Шелла - C++
Ребята помогите пожалуйста, я NEWBIE и не могу решить такая задача : Выполнить сортировку по убыванию. Пирамидальная сортировка и...


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

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

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