'''
algorithms from ch02, DMA.
    by Yue Wang
    28.11.2014
'''

'''
max
'''
def max(seq):
    max = seq[0]
    for elem in seq:
        if elem > max   :   max = elem
    return max

'''
linear seach
'''
def linear_search(seq,val):
    for idx,elem in enumerate(seq):
        if elem == val  :   return idx
    return None

'''
binary search
'''
def binary_search(seq,val):
    beg = 0
    end = len(seq)
    while beg < end:
        mid = beg + (end-beg)//2
        if seq[mid] == val  :   return mid
        elif seq[mid] > val :   end = mid
        else                :   beg = mid
    return None

'''
insertion sort
'''
def insertion_sort(seq):
    if len(seq) < 2 : return;
    for i in range(1,len(seq)):
        key = seq[i]
        j = i-1
        while(j > -1 and seq[j] > key):
            seq[j+1] = seq[j]
            j -= 1
        seq[j+1] = key




		





@@ -67,17 +67,22 @@
 %0A'''%0Amax
+ O(n)
 %0A
-
 '''%0Adef 
@@ -200,16 +200,21 @@
 ar seach
+ O(n)
 %0A'''%0Adef
@@ -347,16 +347,24 @@
 y search
+ O(lg n)
 %0A'''%0Adef
@@ -635,16 +635,28 @@
 ion sort
+ O(lg n %5E 2)
 %0A'''%0Adef
@@ -709,9 +709,8 @@
 turn
-;
 %0A   
@@ -864,16 +864,16 @@
  j -= 1%0A
-
         
@@ -888,16 +888,269 @@
  = key%0A%0A
+'''%0Abubble sort O(lg n %5E 2)%0A'''%0Adef bubble_sort(seq):%0A    size = len(seq)%0A    if size %3C 2 : return%0A    for i in range(size-1) :%0A        for j in range(size-1-i):%0A            if(seq%5Bj%5D %3E seq%5Bj+1%5D): seq%5Bj%5D,seq%5Bj+1%5D = seq%5Bj+1%5D, seq%5Bj%5D%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A%0A
 %0A%0A%0A%09%09%0A%0A%0A

add bubble sort modified: ch02.py