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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модификации)
(Модификации)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 43: Строка 43:
 
                     swapped = true;
 
                     swapped = true;
  
Shakersort:      
+
  '''function''' shakerSort:
count=0
+
     begin = -1
for (int i = 0; i < n/2; i++)                                                 
+
     end = n - 2
     beg = 0;
+
      '''while''' swapped
     end = n - 1;
+
          swapped = ''false''  
+
          begin++
    while beg<=end do
+
        '''for''' i= begin to end
                               
 
        count += 2
 
                                     
 
        if a[beg] >a[beg + 1]                 
 
            Swap(a[beg],a[beg+1]);   
 
              beg++
 
        if a[end-1] > a[end]
 
              Swap(a[end - 1], a[end]);
 
              end--;
 
'''function''' Shakersort:
 
    '''while''' swapped
 
    swapped = '''false'''
 
    '''for''' i = 0 '''to''' n - 2
 
 
           '''if''' A[i] > A[i+1]  
 
           '''if''' A[i] > A[i+1]  
               swap(A[i], A[i+1])  
+
               swap(A[i],A[i+1])
        swapped = '''true'''       
+
              swapped = ''true''  
    '''if''' swapped = '''false'''     
+
        '''if''' swapped = false  
      '''break''' \\выходим из while'а    
+
        '''break'''     
    swapped = '''false'''
+
          swapped = ''false''  
    '''for''' i = n-2 '''downto''' 0
+
          end = end - 1
      '''if''' A[i]>A[i+1]  
+
        '''for''' i = end '''downto''' begin
        swap (A[i],A[i+1])
+
            '''if''' A[i]>A[i+1]  
        swapped = '''true'''
+
            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