#!/usr/bin/esizev pythosize
# -*- coding:utf-8 -*-
# @Author: Vayn a.k.a. VT <[email protected]>
# @Name: sort.py
# @Date: 2011年03月19日 星期六 12时20分29秒

import timeit
from random import shuffle
from time import time

# Bubble Sort
def bubble_sort(array):
    size = len(array)
    for i in xrange(size-1, 0, -1): # for (i = size - 1; i > 0; --i)
        issorted = False
        j = 0
        for j in xrange(0, i-j, 1):
            if array[j] > array[j+1]:
                issorted = True
                array[j], array[j+1] = array[j+1], array[j]
        if not issorted:
            break;

# Insert Sort
def insert_sort(array):
    size = len(array)
    i = 0
    for i in xrange(0, size-i-1, 1): # for (i = 0; i + 1 < size; ++i)
        j = i + 1
        tmp = array[j]
        while j > 0 and tmp < array[j-1]:
            array[j] = array[j-1]
            j -= 1
        array[j] = tmp

# Shell Sort
def shell_sort(array):
    size = len(array)
    step = size / 2
    while step > 0:
        for i in xrange(step):
            for j in xrange(i+step, size, step):
                for k in xrange(j-step, i-1, -step):
                    if array[k] > array[k+step]:
                        array[k], array[k+step] = array[k+step], array[k]
                    else:
                        break
        if step == 2:
            step = 1
        else:
            step = (step - 1) / 3

# Quick Sort
# http://hetland.org/coding/python/quicksort.html
def partition(array, start, end):
    pivot = array[end]
    bottom = start - 1
    top = end

    done = 0
    while not done:

        while not done:
            bottom += 1
            if bottom == top:
                done = 1
                break
            if array[bottom] > pivot:
                array[top] = array[bottom]
                break

        while not done:
            top -= 1

            if top == bottom:
                done = 1
                break
            if array[top] < pivot:
                array[bottom] = array[top]
                break
    array[top] = pivot
    return top
def quick_sort_ip(array, start, end):
    if start < end:
        split = partition(array, start, end)
        quick_sort_ip(array, start, split-1)
        quick_sort_ip(array, split+1, end)
    else:
        return
# http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
def quick_sort(array):
   if not array: return []
   return quick_sort([x for x in array[1:] if x< array[0]]) + array[0:1] + \
          quick_sort([x for x in array[1:] if x>=array[0]])

# Merge Sort
# http://en.literateprograms.org/Merge_sort_%28Python%29
def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
def merge_sort(array):
    size = len(array)
    if size < 2:
        return array
    else:
        middle = size / 2
        left = merge_sort(array[:middle])
        right = merge_sort(array[middle:])
        return merge(left, right)

# Heap Sort
def sift(array, start, count): # sift to build the heap rooted by array[start]
    root = array[start]
    while (2 * start + 1 < count):
        child = 2 * start + 1
        if (child + 1 < count) and (array[child+1] > array[child]):
            child += 1
        if array[child] > root:
            array[start] = array[child]
            start = child
        else:
            break;
    array[start] = root
def heap_sort(array):
    size = len(array)
    # for (i = (size - 2) / 2; i >= 0, --i)
    for i in xrange((size-2)/2, -1, -1): # build heap
        sift(array, i, size)
    # for (i = 1; i < size; ++i)
    for i in xrange(1, size-i, 1): # rebuild the decreasing heap over and over
        array[0], array[size-i] = array[size-i], array[0]
        sift(array, 0, size-i)

def timeit_test():
    random_array = range(1000000)
    shuffle(random_array)

    sort_list = [shell_sort, merge_sort, heap_sort, quick_sort_ip,]
    funcs = ','.join([x.__name__ for x in sort_list])
    funcs += ',random_array'

    for sortfunc in sort_list:
        name = sortfunc.__name__
        if name not in ('quick_sort_ip',):
            statement = "%s(random_array)" % name
        else:
            statement = "quick_sort_ip(random_array, 0, 1000000-1)"
        t = timeit.Timer(statement, "from __main__ import %s" % funcs)
        print name.ljust(15), t.timeit(1)

def shanzhai_test():
    def timer():
        return int(time())
    def t1(func, array):
        shuffle(array)
        start = timer()
        func(array)
        return timer() - start
    def t2(array):
        shuffle(array)
        start = timer()
        quick_sort_ip(array, 0, len(array)-1)
        return timer() - start

    sort_list = [shell_sort, merge_sort, heap_sort, quick_sort_ip, quick_sort]
    lst = range(500000)
    for func in sort_list:
        if func.__name__ != 'quick_sort_ip':
            print func.__name__.ljust(15), t1(func, lst)
        else:
            print func.__name__.ljust(15), t2(lst)

if __name__ == '__main__':
    shanzhai_test()