Friday, November 1, 2013

Heap Sort Implementation in Python

Here I share my Python implementation of heap sort algorithm. Heap sort is O(n log n) sorting algorithm though quicksort is used more frequently. You should learn heap sort to implement priority queue or at least learn the internals of priority queue. :)

In the Python code, I directly followed the heap sort algorithm presented in Introduction to Algorithms by CLRS.
# heapsort

def max_heapify(li, i, heap_size):
  l = i * 2 #left(i)
  r = l + 1 #right(i)
  if l <= heap_size and li[l] > li[i]:
    largest = l
  else:
    largest = i
  if r <= heap_size and li[r] > li[largest]:
    largest = r
  if i != largest:
    li[i], li[largest] = li[largest], li[i]
    max_heapify(li, largest, heap_size)

def build_max_heap(li, heap_size):
  for i in range(heap_size/2 - 1, 0, -1):
    max_heapify(li, i, heap_size) 

def heap_sort(li, heap_size):
  build_max_heap(li, heap_size)
  for i in range(len(li[1:]), 1, -1):
    li[1], li[i] = li[i], li[1]
    heap_size = heap_size - 1
    max_heapify(li, 1, heap_size)

def main():
  # we shall consider the list from element 1, not 0
  li = [0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
  heap_size = len(li[1:])
  heap_sort(li, heap_size)
  print li[1:]

if __name__ == "__main__":
  main()

Sunday, October 20, 2013

Merge Sort Implementation in Python

Today I post the python implementation of merge sort. This is straight-forward implementation of the algorithm presented in the book Introduction to Algorithms [CLRS]. If you think the implementation can be more Pythonic, feel free to comment.

Here is my code:
def merge(li, start, mid, end):
  left_li = []
  left_li.extend(li[start : mid+1])
  right_li = []
  right_li.extend(li[mid+1: end+1])
  left_li.append(2147483647)
  right_li.append(2147483647)
  i = 0
  j = 0
  for k in range(start, end+1):
    if left_li[i] <= right_li[j]:
      li[k] = left_li[i]
      i += 1
    else:
      li[k] = right_li[j]
      j += 1


def merge_sort(li, start, end):
  if start < end:
    mid = (start + end) / 2
    merge_sort(li, start, mid)
    merge_sort(li, mid+1, end)
    merge(li, start, mid, end)

if __name__ == "__main__": 
  li = [5, 2, 4, 7, 1, 3, 2, 6, -4]
  print li
  merge_sort(li, 0, len(li)-1)
  print li
You can test the merge sort implementation against this problem: http://www.spoj.com/problems/MERGSORT/

Wednesday, October 16, 2013

recursive binary search in python

In my previous post, I showed the iterative way to implement binary search algorithm in Python. Here comes the recursive way.
def binary_search_recursive(li, left, right, key):
  while True:
    if left > right:
      return -1
    mid = (left + right) / 2
    if li[mid] == key:
      return mid
    if li[mid] > key:
      right = mid - 1
    else:
      left = mid + 1
    return binary_search_recursive(li, left, right, key)

if __name__ == "__main__":
  li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
  left = 0
  right = len(li)
  for key in  [8, 6, 1, 12, 7]:
    index = binary_search_recursive(li, left, right, key)
    print key, index


iterative binary search in python

Today I am going to post the code for binary search. This one is iterative and the next one will be recursive. If you don't know about binary search, please read the wikipedia article first.

Now, here is my Python implementation of binary search algorithm:
def binary_search_iterative(li, left, right, key):
  while True:
    if left > right:
      return -1
    mid = (left + right) / 2
    if li[mid] == key:
      return mid
    if li[mid] > key:
      right = mid - 1
    else:
      left = mid + 1

if __name__ == "__main__":
  li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
  left = 0
  right = len(li)
  for key in  [8, 6, 1, 12, 7]:
    index = binary_search_iterative(li, left, right, key)
    print key, index

Tuesday, October 15, 2013

insertion sort implementation in python

I am working on my Python coding skills and this time reviewing various algorithms with which I have not been in touch for many days. So I start with sorting, here is my code for insertion sort:
def insertion_sort(ara):
    for j in range(1, len(ara)):
        key = ara[j]
        i = j - 1
        while i >= 0 and key < ara[i]:
            ara[i+1] = ara[i]
            i -= 1
        ara[i+1] = key

    return ara

if __name__ == "__main__":
    ara = [10, 5, 2, 9, 4, 8, 9, 2, 1]
    print insertion_sort(ara)
More python implementation of various algorithms are coming soon. Meanwhile if you feel that there is chance to improve my code, or make it more pythonic, please feel free to comment.

Oh, if you are not familiar with algorithms yet and wording what the ... is insertion sort, please visit the wikipedia article on insertion sort.

Tuesday, September 10, 2013

scrape macy's deals using beautiful soup

Let me show you a tiny real example on how to use the bs4 (beautiful soup version 4) module of Python. Say we want to collect information about the hot deals from macy's. The URL is here. Well, you can see all the info in one page and copy-paste, but that's not our purpose. First you have to get the content of the page using the cute requests module.
import requests

url = 'http://bit.ly/19zWmQT'
r = requests.get(url)
html_content = r.text
Now start cooking the soup:
from bs4 import BeautifulSoup

soup = BeautifulSoup(html_content)
Now look at the html code (page source code) of the url. You will see that the offers are in a list (li) that has 'offer' as a css class name (and some other class names). So you can write the code in the following way:
offer_list = soup('li', 'offer')
Or you can write:
offer_list = soup.find_all('li', 'offer')
Another way to write this is:
offer_list = soup.select('li.offer')
Now run this loop:
for offer in offer_list:
    title = offer.find('h3').text
    url = offer.find('a')['href']
    description = offer.find('span').text
    promo_code = offer.find('span', class_='promo-code').text
    promo_date = offer.find('span', class_='end-date').text
    print title, url, description, promo_date, promo_code
You are done! :)

Wednesday, September 4, 2013

PHP like trim function in Python

Does python have any trim() function (like php) to remove the leading and trailing whitespace? Answer is yes and it's called strip. Here is the code:
>>> str = ' aa b cde  '
>>> str
' aa b cde  '
>>> str.strip()
'aa b cde'
>>> str = str.strip()
>>> str
'aa b cde'
>>> 
Happy Coding! :)