Algorithms

In [3]:

    

def binarySearch(l,elem):
    low = 0
    high = len(l)-1
    while low<high:
        mid = (low + high)/2
        if l[mid] == elem:
            return mid
        elif l[mid]>elem:
            high = mid-1
        elif l[mid]<elem:
            low = mid+1
    else:
        return 'not found'


    

In [5]:

    

binarySearch([1,2,3,4],9)


    

    
Out[5]:





'not found'

In [3]:

    

def bubbleSort(l):
    for i in xrange(len(l)):
        for j in xrange(1,len(l)-i):
            if l[j-1]>l[j]:
                l[j],l[j-1] = l[j-1],l[j]
            
    print l


    

In [4]:

    

bubbleSort([1004,2,5,4,31])


    

    




[2, 4, 5, 31, 1004]

In [19]:

    

def selectionSort(l):
    for i in xrange(len(l)):
        k = i
        for j in xrange(i,len(l)):
            if l[j]<l[k]:
                k = j
            print l
        l[i],l[k] = l[k],l[i]
    return l


    

In [20]:

    

selectionSort([95,5,4,3,4,2,1])


    

    




[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[95, 5, 4, 3, 4, 2, 1]
[1, 5, 4, 3, 4, 2, 95]
[1, 5, 4, 3, 4, 2, 95]
[1, 5, 4, 3, 4, 2, 95]
[1, 5, 4, 3, 4, 2, 95]
[1, 5, 4, 3, 4, 2, 95]
[1, 5, 4, 3, 4, 2, 95]
[1, 2, 4, 3, 4, 5, 95]
[1, 2, 4, 3, 4, 5, 95]
[1, 2, 4, 3, 4, 5, 95]
[1, 2, 4, 3, 4, 5, 95]
[1, 2, 4, 3, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]
[1, 2, 3, 4, 4, 5, 95]






    
Out[20]:





[1, 2, 3, 4, 4, 5, 95]

In [23]:

    

def insertionSort(l):
    for j in xrange(1,len(l)):
        key = l[j]
        i = j-1
        while(i>-1 and l[i]>key):
            l[i+1] = l[i]
            i-=1
        l[i+1] = key
    return l


    

In [45]:

    

insertionSort([1,2,34,4,99,33,22,11,1000004])


    

    
Out[45]:





[1, 2, 4, 11, 22, 33, 34, 99, 1000004]

In [35]:

    

def selectionSort(l):
    for i in xrange(len(l)):
        k = i
        for j in xrange(i,len(l)):
            if l[j]<l[k]:
                k = j
            l[k],l[i] = l[i],l[k]
    return l


    

In [36]:

    

selectionSort([1,2,3,4,5,6,7,8,1,33,22])


    

    
Out[36]:





[1, 1, 2, 3, 4, 5, 6, 7, 8, 22, 33]

In [44]:

    

def insertionSort(l):
    for i in xrange(1,len(l)):
        key = l[i]
        j = i-1
        while j>-1 and l[j]>key:
            l[j+1] = l[j]
            j-=1
        l[j+1] = key
    return l


    

In [ ]: