�������������� ��������� ���������� �� ������� ������ � ����������

• ����� �� �������������������� ��������� ��� ?����-������?:
  • ������ �����: ~N ��������
  • ��������� ������: ~N ��������
• ����� �� �������������� ���������
  • �������������� �������: ��������� ������� � ������ ������ � ���������
  • ��������: ���������� ������� (�������� �����)
    • ������ �����: ~log?N ��������
    • ��������� �����: ~log?N ��������
• ����������
  • �������� ������ � ������ �������
• ���������� �������
  • ������ ���������: (N-1)*(N-2)/2 ? ~N�

  • ���������: ����� ���������� ���������

       1   for i in xrange(N-1):
       2       m = i
       3       for j in xrange(i+1,N):
       4           if A[m]>A[j]:
       5               m = j
       6       A[m], A[i] = A[i], A[m]
    

• ���������� ���������: ����� ?�������? ������� � �������� (��� � ������, � �� ��� � �������):
  • ����: ��������� ��������� ������� � ������������� ������ (N-1 ���), ��� ���� ����� ������� ���������� �������� ������� (log?N ���������)

       1   def binsert(el, seq, st, end):
       2     if end-st<2:
       3         seq.insert(st+(el>seq[st]),el)
       4     elif el<seq[(st+end)/2]:
       5         binsert(el, seq, st, (st+end)/2)
       6     else:
       7         binsert(el, seq, (st+end)/2, end)
       8 
       9   def insertsort(seq):
      10     for en in xrange(1,len(seq)):
      11         e = seq.pop(en)
      12         binsert(e, seq, 0, en)
    

  • ? ��������� ~N*log?N

• ���������� ��������: ����� �������������� ������ (������������ ����� ������), ���� ���������� ����������������� ������� � ���������

     1 def joinsort(seq, st=0, en=None):
     2     if en-st<2: return seq[st:en]
     3     l = joinsort(seq, st, (st+en)/2)
     4     r = joinsort(seq, (st+en)/2, en)
     5     new = []
     6     while l and r:
     7         new.append((l if l[0]<r[0] else r).pop(0))
     8     new.extend(l)
     9     new.extend(r)
    10     return new
    11  
  

  • ���������� ������� ����� ������������ ��������� ~N*log?N

�������� �������

1. ������

2. ���������� ������� Compare(), Read() � Write(), ������� ���������� ��� �������� ������������������, ������ � ����� ������� ��������������, ���� ��� ���� ������� ����������� ��������. ����������������� ��������� ���������� ���, ����� �������������� ������ ��� �������. �������� ���������� ���������, ������ � ������� � ������ ����������.

�������� �����������

• ? ���� �� Linux

• ?? ���� ���������� ���������

• ? ������������� �������

• ? ���� ��� ���������������� ��������

CategoryClass CategoryVmsh