python 알고리즘 학습통 정렬 알고리즘 실례 (블록 정렬)

 
  
# -*- coding: utf-8 -*- 
   
  
def insertion_sort(A):
    """    ，         """
    n = len(A)
    if n <= 1:
        return A
    B = [] #     
    for a in A:
        i = len(B)
        while i > 0 and B[i-1] > a:
            i = i - 1
        B.insert(i, a);
    return B
 
  
def bucket_sort(A):
    """   ，    ：
    BUCKET-SORT(A)
    1  n ← length[A] //   
    2  for i ← 1 to n
    3    do insert A[i] into list B[floor(nA[i])] //  n         
    4  for i ← 0 to n-1
    5    do sort list B[i] with insertion sort //            
    6  concatenate the lists B[0],B[1],...,B[n-1] together in order //           
 
  
                    ，              [0,1) 。
    """
    n = len(A)
    buckets = [[] for _ in xrange(n)] # n   
    for a in A:
        buckets[int(n * a)].append(a)
    B = []
    for b in buckets:
        B.extend(insertion_sort(b))
    return B
 
  
if __name__ == '__main__':
    from random import random
    from timeit import Timer
 
  
    items = [random() for _ in xrange(10000)]
 
  
    def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)
 
  
    def test_bucket_sort():
        print(items)
        sorted_items = bucket_sort(items)
        print(sorted_items)
 
  
    test_methods = [test_sorted, test_bucket_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = Timer(name + '()', 'from __main__ import ' + name)
        print(name + ' takes time : %f' % t.timeit(1))