# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Sorting
#
# ## Setup

# +
import time
import numpy as np
import matplotlib.pyplot as plt
# %config InlineBackend.figure_format = 'retina'

def gettime(f, *args):
    "Return time in seconds; %time, %timeit don't work in functions so we write our own"
    t0 = time.time()
    f(*args)
    t1 = time.time()
    return t1 - t0

def showtime(f, A, step=1):
    n = len(A)
    times = [gettime(f, A[0:i]) for i in range(1,n,step)]
    plt.figure(figsize=(4,3))
    plt.plot(range(1,n,step), times, '.', color='#fdae61',
             alpha=.8, markersize=10, markeredgewidth=.3, markeredgecolor='grey')
    plt.xlabel("Problem size")
    plt.ylabel("Time in seconds")
    plt.show()


# -

# ## Bubble sort

# +
def lprint(A,start=-1,stop=-1):
    for i,a in enumerate(A):
        print(f"{a:3}", end=' ')
        print("\b", end="")
        if i>=start and i<=stop: print("\u0332", end="")
        
def bubble(A, verbose=True):
    swapped=True
    second_to_last_idx = len(A)-2
    n = 1
    while swapped:
        swapped=False
        if verbose: print(); lprint(A); print(f"\t\tPass {n}"); n += 1
        for i in range(second_to_last_idx+1):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
                swapped = True
                if verbose: lprint(A,i,i+1); print(f"\t\tSwap A[{i}], A[{i+1}]")


# -

A = [9,1,4,2,-3]
bubble(A)

A = np.random.randint(1,100,400)
def quiet_bubble(A): return bubble(A,verbose=False)
showtime(quiet_bubble, A)


# ## Merge sort

# +
def merge(a,b):
    "Merge two sorted lists in O(nlogn)"
    return sorted(a+b) # cheating: easy but not O(n)
    
def mergesort(data):
    if len(data)==0:
        return []
    if len(data)==1:
        return [data[0]]
    if len(data)==2:
        if data[0]<data[1]:
            return data
        return [data[1], data[0]]

    m = len(data) // 2
    left = mergesort(data[0:m])
    right = mergesort(data[m:])
    return merge(left, right)


# +
data = [1]
print(data, '->', mergesort(data))

data = [5,1]
print(data, '->', mergesort(data))

data = []
print(data, '->', mergesort(data))

data = [10,3,1,10,99,100]
print(data, '->', mergesort(data))
# -

A = list(np.random.randint(1,100,2000))
showtime(mergesort, A)


def merge(a,b):
    "Merge two sorted arrays, returning another, w/o wasting so much space"
    i = 0
    j = 0
    c = []
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    # might have remainders
    if i<len(a):
        for k in range(i,len(a)):
            c.append(a[k])
    elif j<len(b):
        for k in range(j,len(b)):
            c.append(b[k])
    return c


# +
data = [1]
print(data, '->', mergesort(data))

data = [5,1]
print(data, '->', mergesort(data))

data = []
print(data, '->', mergesort(data))

data = [10,3,1,10,99,100]
print(data, '->', mergesort(data))
# -

A = list(np.random.randint(1,100,2_000))
showtime(mergesort, A)


# ## Quicksort

def partition(A,lo,hi):
    pivot = A[hi]    # pick last element as pivot  
    # Filter for all less/greater than pivot (ignore pivot spot)
    left  = [A[i] for i in range(lo,hi) if A[i]<pivot]
    right = [A[i] for i in range(lo,hi) if A[i]>=pivot]
    A[lo:hi+1] = left+[pivot]+right # copy back to A
    return lo + len(left) # return index of pivot


# +
def qsort_(A, lo, hi):
    if lo >= hi: return
    pivot_idx = partition(A,lo,hi)
    qsort_(A, lo, pivot_idx-1)
    qsort_(A, pivot_idx+1, hi)
    
def qsort(A):
    return qsort_(A, lo=0, hi=len(A)-1)


# -

A = np.random.randint(-2,10,20)
print(A)
qsort(A)
print(A)

A = np.random.randint(1,100,1000)
showtime(qsort, A)


# ### Slightly better partition
#
# Well, it *should* be better but it uses more/slower python looping, which makes it take much longer. Seems like it'd be faster as I make just one pass over the list but list comprehension probably optimized like crazy.

def partition(A, lo, hi):
    pivotidx = hi
    pivot = A[pivotidx]  # pick last element as pivot
    less = []
    more = []
    for i in range(lo,hi):
        if i==pivotidx:
            continue
        elif A[i]<pivot:
            less.append(A[i])
        else:
            more.append(A[i])
    # Copy less,pivot,more into A
    A[0:len(less)] = less
    pivotidx = lo + len(less)
    A[pivotidx] = pivot
    A[pivotidx+1:pivotidx+1+len(more)] = more
    return pivotidx


A = np.random.randint(-2,10,20)
print(A)
qsort(A)
print(A)

A = np.random.randint(1,100,1000)
showtime(qsort, A)


# Ouch. That likely pretty nonlinear...not sure it's quadratic...could be nlogn.

# ### In-place partition

def partition(A,lo,hi):
    """
    Follows Wikipedia "Lomuto partition scheme" description:
    reorder the array so that all elements with
    values less than the pivot come before the pivot, while
    all elements with values greater than the pivot come after
    it (equal values can go either way).
    """
    i = lo
    pivot = A[hi]    # pick last element as pivot  
    for j in range(lo, hi+1):  
        if A[j] < pivot:   
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[hi] = A[hi], A[i]
    return i


A = np.random.randint(-2,10,20)
print(A)
qsort(A)
print(A)

A = np.random.randint(1,100,1000)
showtime(qsort, A)


# ## Pigeonhole sort

# +
# avoid negative numbers for simplicity
# also assume min(A) is close to 0
def psort(A:list) -> list:
    size = max(A) + 1
    holes = [0] * size
    for a in A:
        holes[a] += 1
    A_ = []
    for i in range(0,size):
        A_.extend([i] * holes[i])
#         for j in range(holes[i]):  # alternative
#             A_.append(i)
    return A_

A = np.random.randint(1,30,10)
psort(A)
# -

A = np.random.randint(1,100,1000)
showtime(psort, A)

# ## Bucket sort

# +
import numpy as np

def bsort(A:list, nbuckets=5) -> list:
    mx = max(A)
    buckets = []
    for i in range(nbuckets):
        buckets.append([])
    for a in A:
        a_normalized = a / mx # get into 0..1
        i = int(a_normalized * (nbuckets-1)) # spread across buckets
        buckets[i].append(a)
        
    A_ = []
    for i in range(nbuckets):
        A_.extend( sorted(buckets[i]) )
    return A_

A = np.random.random(size=10) * 100 + 10
bsort(A, 5)
# -

A = np.random.random(size=1000) * 100 + 10
showtime(bsort, A)


# ## Bucket sort on strings

# +
# assume lowercase English letters for simplicity
def pstr_sort(A:list) -> list:
    size = ord('z') - ord('a') + 1
    holes = []
    for i in range(size):
        holes.append([])
    for s in A:
        i = ord(s[0])-ord('a')
        holes[i].append(s)
    #objviz(holes).view()
    A_ = []
    for i in range(ord('z')-ord('a') + 1):
        A_.extend( sorted(holes[i]) )
    return A_

from lolviz import *

A = ['apple', 'ape', 'zebra', 'cat', 'canary', 'civet', 'dog'] 
pstr_sort(A)


StarcoderdataJupyterScriptsDedupFiltered