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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
(Модификации)
 
(не показано 27 промежуточных версий этого же участника)
Строка 7: Строка 7:
 
           swap(A[j], A[j + 1]);
 
           swap(A[j], A[j + 1]);
  
В оптимизированной версии точное количество сравнений зависит от исходного массива и в худшем случае составляет <tex>\displaystyle \frac {n(n - 1)} {2}</tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
+
Для первой оптимизации точное количество сравнений зависит от исходного массива и в худшем случае составляет <tex>\displaystyle \frac {n(n - 1)} {2}</tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
 +
 
 +
== Модификации ==
 +
[http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort  Сортировка чет-нечет] - модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга.
 +
 
 +
[http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой] - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - <tex> O(nlog(n)) </tex>.
 +
'''Шаг 1''' мы вычисляем k которое равно
 +
 
 +
[http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием]  - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - <tex> O(N^2) </tex>.
 +
 
 +
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>.
 +
 
 +
  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''

Текущая версия на 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