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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модификации)
(Модификации)
 
(не показано 8 промежуточных версий этого же участника)
Строка 39: Строка 39:
 
             swapped = false;
 
             swapped = false;
 
             for ( i = 0; i + jump < size; ++i)
 
             for ( i = 0; i + jump < size; ++i)
                 if (a[i + jump]< array[i]))  
+
                 if a[i + jump]< array[i])  
 
                     swap(array[i], array[i + jump]);
 
                     swap(array[i], array[i + jump]);
 
                     swapped = true;
 
                     swapped = true;
 +
 +
  '''function''' shakerSort:
 +
    begin = -1
 +
    end = n - 2
 +
      '''while''' swapped
 +
          swapped = ''false'' 
 +
          begin++
 +
        '''for''' i= begin to end
 +
          '''if''' A[i] > A[i+1]
 +
              swap(A[i],A[i+1])
 +
              swapped = ''true''   
 +
        '''if''' swapped = false
 +
        '''break'''   
 +
          swapped = ''false''
 +
          end = end - 1
 +
        '''for''' i = end '''downto''' begin
 +
            '''if''' A[i]>A[i+1]
 +
            swap(A[i],A[i+1])
 +
            swapped = ''true''

Текущая версия на 20:08, 13 июня 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]. Шаг 1 мы вычисляем k которое равно

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

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

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


combsort(a):
      jump = n
       bool swapped = true;
       while (jump > 1 and swapped) 
           if (jump > 1)
               jump /= 1.24733;
           swapped = false;
           for ( i = 0; i + jump < size; ++i)
               if a[i + jump]< array[i]) 
                   swap(array[i], array[i + jump]);
                   swapped = true;
 function shakerSort:
    begin = -1
    end = n - 2
      while swapped
         swapped = false   
         begin++
        for i= begin to end 
          if A[i] > A[i+1] 
             swap(A[i],A[i+1])
             swapped = true    
        if swapped = false 
        break    
          swapped = false 
          end = end - 1
        for i = end downto begin
           if A[i]>A[i+1] 
           swap(A[i],A[i+1])
           swapped = true