Участник:Satosik — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модификации)
(Модификации)
Строка 17: Строка 17:
  
 
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>.
 
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>.
 +
 
odd-even_sort(a):
 
odd-even_sort(a):
 
for (int i = 0; i < n; ++i)
 
for (int i = 0; i < n; ++i)
     {
+
      
 
         if (i mod2 =0)
 
         if (i mod2 =0)
 
          
 
          

Версия 20:22, 12 июня 2014

Псевдокод

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] A[0..A.size - 1] [/math].

 BubbleSort(A)
   for i = 0 to a.size - 2:
     for j = 0 to a.size - 2:
       if A[j] > A[j + 1]:
         swap(A[j], A[j + 1]);

Для первой оптимизации точное количество сравнений зависит от исходного массива и в худшем случае составляет [math]\displaystyle \frac {n(n - 1)} {2}[/math]. Следовательно, [math] T_1 = O(n^2) [/math].

Модификации

Сортировка чет-нечет - модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга.

Сортировка расческой - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - [math] O(nlog(n)) [/math].

Сортировка перемешиванием - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - [math] O(N^2) [/math].

В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем [math] (n - 1)^2 [/math] — максимальное количество сравнений для данной сортировки. Следовательно, [math] T_1 = O(n^2) [/math].

odd-even_sort(a): for (int i = 0; i < n; ++i)

       if (i mod2 =0)
       
           for (int j = 2; j < n; j+=2)
               if (a[j] < a[j-1])
                   swap(a[j-1], a[j]);
       
       else
       
           for (int j = 1; j < n; j+=2)
               if (a[j] < a[j-1])
                   swap(a[j-1], a[j]);