#!/usr/bin/env python
# coding: utf
'''
Изобрести более эффективный алгоритм сортировки списка (не массива!), основанный на бинарном поиске
Оформить два алгоритма сортировки (медленный и быстрый) в виде функций. Сравнить время выполнения
'''

def bubblesort(L):
    '''Сортировка пузырьком'''
    for i in xrange(len(L)-1):          # N-1 оборотов цикла
        for j in xrange(len(L)-i-1):    # N-i-1 ооротов цикла
            if L[j]>L[j+1]:
                L[j],L[j+1] = L[j+1],L[j]
# Итого (N-2)+(N-3)+...+2+1 = (N-1)*(N-2)/2 = N**2/2 - 3*N/2 + 1

def inssort(L):
    '''Сортировка вставками'''
    for w in xrange(1,len(L)):          # N-1 оборотов цикла
        b,e=0,w
        while b<e:                      # e-b каждый оборот уменьшается вдвое
            m=(b+e)/2                   
            if L[m]==L[w]:              # => не боле, чем log по основанию 2 от w
                break                   # оборотов цикла
            elif L[m]>L[w]:
                e=e-(e-b+1)/2
            else:
                b=b+(e-b+1)/2
        else:
            m=b
        L.insert(m,L.pop(w))
# Итого < (N-1)*log(2,N-1)

l=list(input("Введите список чисел через запятую: "))
# Имена функуций -- тоже объекты!
for fun in (bubblesort, inssort):
    L=l[:]
    fun(L)
    print L