Rabbit House

#-*-coding:utf-8-*-
'''
Created on 2016/12/19
Last updated on 2016/12/21
@author: Camp Nou
'''

'''
Sorting Algorithms
    Bubble Sort      stable    T(n)=Θ(n^2)
    Selection Sort   unstable  T(n)=Θ(n^2)
    Insert Sort      stable    T(n)=Θ(n^2)
    Merge Sort       stable    T(n)=Θ(nlogn)
    Quick Sort       unstable  T(n)=Θ(nlogn)
    Shell Sort       unstable  T(n)=Θ(n^1.3) on average
    Heap Sort        unstable  T(n)=Θ(nlogn)
    Bucket Sort      stable    T(n)=Θ(n)
    Count Sort       stable    T(n)=Θ(n)
'''
from math import ceil

def BubbleSort(a):
    array=a
    l=len(array)
    while l>0:
        for i in range(l-1):
            if array[i]>array[i+1]:
                array[i],array[i+1]=swap(array[i],array[i+1])
        l-=1
    return array

def SelectionSort(a):
    # T(n)=Θ(n^2), unstable
    array=a
    for i in range(len(array)):
        min=array[i]
        index=i
        for j in range(i,len(array)):
            if array[j]<min:
                min=array[j]
                index=j
        t=array[i]
        array[i]=array[index]
        array[index]=t
    return array

def InsertSort(a):
    # T(n)=Θ(n^2)
    array=a
    for i in range(1,len(array)):
        for j in range(0,i):
            if array[j]>array[i]:
                tmp=array[i]
                index=j
                array[index+1:i+1]=array[index:i]
                array[index]=tmp
    return array

def MergeSort(a):
    # T(n)=Θ(nlogn)
    array=a 
    if len(array)<=1:
        return array
    mid=int(len(array)/2)
    left=MergeSort(array[:mid])
    right=MergeSort(array[mid:])

    def Merge(left,right):
        result=[]
        while left and right:
            if left[0]<=right[0]:
                result.append(left[0])
                left.pop(0)
            else:
                result.append(right[0])
                right.pop(0)
        result+=left 
        result+=right
        return result

    return Merge(left,right)


def QuickSort(a):
    # T(n)=Θ(nlogn), unstable
    array=a
    less=[]
    more=[]
    pivotlist=[]
    if len(array)<=1:
        return array
    else:
        pivot=array[0]
        for i in range(len(array)):
            if array[i]<pivot:
                less.append(array[i])
            if array[i]>pivot:
                more.append(array[i])
            if array[i]==pivot:
                pivotlist.append(array[i])
        less=QuickSort(less)
        more=QuickSort(more)
    return less+pivotlist+more 

def ShellSort(a):
    # T(n)=Θ(n^1.3) on average, not stable
    array=a
    n=len(array)
    group=int(ceil(n/2)) 
    #print group
    while group>=1:
        ary=[]
        for i in range(group):
            ary.append([])
        for i in range(n):
            ary[i%group].append(array[i])
        for i in ary:
            i=InsertSort(i)
        array=[]
        for i in ary:
            array.extend(i)
        #print array 
        group=int(ceil(group/2))
    return array 

def HeapSort(array):
    # T(n)=Θ(nlogn), not stable
    length=len(array)
    sortedarray=[]
    def maxHeapify(array):
        n=len(array)/2-1
        while n>=0:
            if 2*n+1<len(array):
                [array[n],array[2*n+1]].sort()
            else:
                [array[n],array[2*n+1],array[2*n+2]].sort()
            n=n-1
    while len(sortedarray)<length:
        maxHeapify(array)
        sortedarray.append(array.pop(0))
    return sortedarray[::1]

def BucketSort(a):
    array=a 
    result=[]
    # 10 buckets
    if len(array)<=1:
        return array 
    buckets=[[],[],[],[],[],[],[],[],[],[]]
    #buckets[1].append(1)
    for i in array:
        index=i/10
        buckets[index].append(i) 
        #print i,index,buckets[index]
        #print buckets[index]
    for i in buckets:
        #print i,
        result.extend(QuickSort(i))
    return result 

def CountSort(a):
    array=a 
    MAX=max(a)
    MIN=min(a)
    count=[0]*(MAX-MIN+1)
    for i in array:
        count[i-MIN]+=1
    result=[]
    for j in range(len(count)):
        if count[j]!=0:
            for k in range(count[j]):
                result.append(j+MIN)
    return result 

a=[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]
print "QuickSort:    ",QuickSort(a)
print "BubbleSort:   ",BubbleSort(a)
print "SelectionSort:",SelectionSort(a)
print "InsertSort:   ",InsertSort(a)
print "MergeSort:    ",MergeSort(a)
print "ShellSort:    ",ShellSort(a)
print "BucketSort:   ",BucketSort(a)
print "CountSort:    ",CountSort(a)
print "HeapSort:     ",HeapSort(a)

Sorting Algorithms