In [21]:

    

import numpy as np


    

In [40]:

    

def radix_sort(alist):
    all_lists = []
    alist = np.array(alist)
    all_lists.append(alist)
    for i in (2, 1, 0):
        print alist
        tmp_list = [item[i] for item in alist]
        index = np.argsort(tmp_list)
        
        alist = alist[index]
        all_lists.append(alist)
        
    print alist
    return all_lists


    

In [ ]:

    




    

In [41]:

    

items = ['COW', 'DOG', 'SEA', 'RUG', 'ROW', 'MOB', 'BOX', 'TAB', 'BAR', 'EAR', 'TAR', 'DIG', 'BIG', 'TEA', 'NOW',
'FOX']


    

In [42]:

    

out = radix_sort(items)


    

    




['COW' 'DOG' 'SEA' 'RUG' 'ROW' 'MOB' 'BOX' 'TAB' 'BAR' 'EAR' 'TAR' 'DIG'
 'BIG' 'TEA' 'NOW' 'FOX']
['SEA' 'TEA' 'MOB' 'TAB' 'DOG' 'RUG' 'DIG' 'BIG' 'BAR' 'EAR' 'TAR' 'COW'
 'ROW' 'NOW' 'BOX' 'FOX']
['TAB' 'BAR' 'EAR' 'TAR' 'SEA' 'TEA' 'DIG' 'BIG' 'MOB' 'DOG' 'COW' 'ROW'
 'NOW' 'BOX' 'FOX' 'RUG']
['BAR' 'BIG' 'BOX' 'COW' 'DIG' 'DOG' 'EAR' 'FOX' 'MOB' 'NOW' 'ROW' 'RUG'
 'SEA' 'TAB' 'TAR' 'TEA']

In [43]:

    

out


    

    
Out[43]:





[array(['COW', 'DOG', 'SEA', 'RUG', 'ROW', 'MOB', 'BOX', 'TAB', 'BAR',
        'EAR', 'TAR', 'DIG', 'BIG', 'TEA', 'NOW', 'FOX'], 
       dtype='|S3'),
 array(['SEA', 'TEA', 'MOB', 'TAB', 'DOG', 'RUG', 'DIG', 'BIG', 'BAR',
        'EAR', 'TAR', 'COW', 'ROW', 'NOW', 'BOX', 'FOX'], 
       dtype='|S3'),
 array(['TAB', 'BAR', 'EAR', 'TAR', 'SEA', 'TEA', 'DIG', 'BIG', 'MOB',
        'DOG', 'COW', 'ROW', 'NOW', 'BOX', 'FOX', 'RUG'], 
       dtype='|S3'),
 array(['BAR', 'BIG', 'BOX', 'COW', 'DIG', 'DOG', 'EAR', 'FOX', 'MOB',
        'NOW', 'ROW', 'RUG', 'SEA', 'TAB', 'TAR', 'TEA'], 
       dtype='|S3')]

In [48]:

    

for i in range(len(out[0])):
    for j in range(len(out)):
        print out[j][i],'  ',
    print


    

    




COW    SEA    TAB    BAR   
DOG    TEA    BAR    BIG   
SEA    MOB    EAR    BOX   
RUG    TAB    TAR    COW   
ROW    DOG    SEA    DIG   
MOB    RUG    TEA    DOG   
BOX    DIG    DIG    EAR   
TAB    BIG    BIG    FOX   
BAR    BAR    MOB    MOB   
EAR    EAR    DOG    NOW   
TAR    TAR    COW    ROW   
DIG    COW    ROW    RUG   
BIG    ROW    NOW    SEA   
TEA    NOW    BOX    TAB   
NOW    BOX    FOX    TAR   
FOX    FOX    RUG    TEA   

In [74]:

    

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


    

In [75]:

    

def partition(A, p, r):
    x = A[r]
    i = p - 1
    
    for j in range(p, (r-1)+1):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    
    return i+1


    

In [76]:

    

items = [4, 5, 6, 3, 2, 1]
quicksort(items, 0, len(items)-1)
print items


    

    




[1, 2, 3, 4, 5, 6]

In [ ]:

    

def quicksortPrime(A, p, r):
    if p < r:
        q, t = partitionPrime(A, p, r)
        
        #-- ignore values equal to the pivot
        #-- all values on the interval q..t
        quicksortPrime(A, p, q-1)
        quicksortPrime(A, t+1, r)


    

In [307]:

    

def partitionPrime(A, p, r):
    """Working"""
    x = A[p]
    h = p
    i = p
    
    for j in range(p+1, r+1):
        if A[j] < x:
            A[i], A[j], A[h+1] = A[j], A[h+1], A[i] 
            i = i+1
            h = h+1
            
        elif A[j] == x:
            A[h], A[j] = A[j], A[h] 
            h = h+1
            
    return h, i


    

In [320]:

    

def randomizedQuicksortPrime(A, p, r):
    if p < r:
        q, t = randomizedPartition(A, p, r)
        
        #-- ignore values equal to the pivot
        #-- all values on the interval q..t
        quicksortPrime(A, p, q-1)
        quicksortPrime(A, t+1, r)


    

In [346]:

    

def randomizedPartition(A, p, r):
    import random
    
    #-- Select a random index between p and r
    i = random.randint(p, r)
    
    #-- Swap p and i
    A[p], A[i] = A[i], A[p]
    
    #-- Run standard partition function
    return partitionPrime(A, p, r)


    

In [322]:

    

items = [3, 3, 2, 24, 18, 4, 12, 12, 12, 12, 12, 13, 4, 2, 54, 14]
quicksortPrime(items, 0, len(items)-1)
print items


    

    




[2, 2, 3, 3, 4, 4, 12, 12, 12, 12, 12, 13, 14, 18, 24, 54]

In [331]:

    

items = [3, 3, 2, 24, 18, 4, 12, 12, 12, 12, 12, 13, 4, 2, 54, 14]
randomizedQuicksortPrime(items, 0, len(items)-1)
print items


    

    




[2, 2, 4, 3, 3, 4, 12, 12, 12, 12, 12, 13, 14, 18, 24, 54]

In [349]:

    

np.ceil(np.log2(8)) -1


    

    
Out[349]:





2.0

In [ ]: