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

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

Восстановить пароль Регистрация
 
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
15.10.2013, 02:45     Сортировка Шелла и вставок #1
Здравствуйте, проблема вот в чем в этих сортировках постоянно одно и тоже количество перестановок что здесть не так:
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();
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2013, 02:45     Сортировка Шелла и вставок
Посмотрите здесь:

C++ Сортировка методом Вставок
C++ сортировка методом вставок
Сортировка Шелла C++
C++ Сортировка методом простых вставок
Сортировка методом центрированных вставок C++
Сортировка Шелла C++
C++ Сортировка Шелла
C++ Сортировка списка методом простых вставок

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru