Showing posts with label Searching and Sorting - DataStructure & Algorithm. Show all posts
Showing posts with label Searching and Sorting - DataStructure & Algorithm. Show all posts

Thursday, March 31, 2016

bubble sort - o(n*n)

#!/usr/bin/python

def bubble_sort(arr):
for i in range(0, len(arr)):
for j in range(i, len(arr)):
if arr[i] > arr[j]:
arr[j], arr[i] = arr[i], arr[j]

arr= [8, 3, 0, 8, 9, 3, 0, 5]
bubble_sort(arr)
print arr

selection sort - O(n*n)

#!/usr/bin/python
def selection_sort(arr):
    for i in range(0,len(arr)):
        min_index = i
        ## find minimum element in remaining
        ## array
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        ## swap the minimum element with arr[i]
        arr[i], arr[min_index] = arr[min_index], arr[i]

arr = [3, 0, 9, 4, 2, 9, 1, 0]
selection_sort(arr)
print arr

Wednesday, March 30, 2016

Binary Search O(log N)

#!/usr/bin/python

### A recursive binary search function
def binarySort(arr,l,r,ele):
    m = (l+r)/2
    if arr[m] == ele:
        return m;
    elif arr[m] < ele:
        return binarySort (arr, m + 1, r, ele)
    else:
        return binarySort (arr, l, m - 1, ele)
    return -1
'''
##A iterative binary search function
def binarySort(arr, l, r, ele):
    while l < r:
        m = (l+r)/2;
        if arr[m] == ele:
            return m
        elif arr[m] < ele:
            l = m + 1
        else:
            r = m - 1
    return -1
'''
arr = [1,2,3,4,5,6,7]
l= 0
r= len(arr)-1
ele= 2
index = binarySort(arr, l, r, ele)
if index == -1:
    print "not found"
else:
    print "found at index -- "+str(index)