

In [14]:

    
import numpy as np

Intro

This notebook explores sorting algorithms mostly for interviews purposes.

Simple Sorts

Insertion sort
Selection sort



In [13]:

    
a = np.random.randint(0, 1000, 100)
a_sorted = sorted(a)



In [30]:

    
# first naive implementation (which turned out to be insertion sort)
def sort(a):
    a = a.copy()
    for i in range(len(a)-1):
        if a[i+1]<a[i]:
            tmp = a[i]
            a[i] = a[i+1]
            a[i+1] = tmp
            for j in range(i-1, -1, -1):
                if a[j]>a[j+1]:
                    tmp = a[j]
                    a[j] = a[j+1]
                    a[j+1] = tmp
                else:
                    break
    return a



In [2]:

    
# structurally improved
def insertion_sort(a):
    a = a.copy()
    for i in range(len(a)):
        j = i
        while j>0 and a[j]<a[j-1]:
            tmp = a[j]
            a[j] = a[j-1]
            a[j-1] = tmp
            j -= 1
    return a



In [3]:

    
# selection sort
def selection_sort(a):
    a = a.copy()
    for i in range(len(a)-1):
        min_val = a[i]
        min_idx = i
        for j in range(i+1, len(a)):
            if a[j] < min_val:
                min_val = a[j]
                min_idx = j
        if min_idx != i:
            a[min_idx] = a[i]
            a[i] = min_val
    return a



In [41]:

    
sort(a)









    Out[41]:





array([  2,   6,   9,  24,  29,  39,  41,  48,  52,  54,  65,  66,  79,
        79,  85, 112, 118, 157, 172, 201, 214, 218, 234, 246, 246, 263,
       267, 270, 273, 278, 279, 291, 292, 294, 298, 327, 358, 362, 375,
       378, 378, 388, 390, 397, 401, 402, 426, 426, 428, 432, 443, 447,
       485, 495, 499, 500, 513, 529, 585, 585, 605, 608, 611, 616, 651,
       655, 664, 668, 676, 682, 685, 685, 689, 690, 702, 743, 779, 797,
       798, 809, 816, 817, 821, 832, 853, 871, 872, 875, 904, 907, 909,
       915, 921, 930, 943, 969, 980, 984, 990, 992])

Bubble Sort

$n | n^2 | n^2 | 1 |Yes$



In [5]:

    
def bubble_sort(a):
    a = a.copy()
    is_sorted = False
    while not is_sorted:
        is_sorted = True
        for i in range(len(a)-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                is_sorted = False
    return a



In [13]:

    
%timeit -r 1000 bubble_sort(np.random.randint(0, 1000, 100))









    



100 loops, best of 1000: 2.41 ms per loop

Efficient Sorts

Merge Sort



In [8]:

    
def merge_sort(a):
    if len(a) <= 1:
        return a
    
    left = merge_sort(a[:len(a)//2])
    right = merge_sort(a[len(a)//2:])
    
    return merge(left, right)

def merge(left, right):
    res = []
    while len(left)>0 and len(right)>0:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    if len(left) == 0:
        res += right
    else:
        res += left
    return res



In [11]:

    
%timeit merge_sort(list(np.random.randint(0, 1000, 100)))









    



1000 loops, best of 3: 368 µs per loop



In [22]:

    
merge_sort(a)

Quick Sort



In [31]:

    
def quick_sort(a, lo=0, hi=len(a)-1):
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p-1)
        quick_sort(a, p+1, hi)
    return a
    
def partition(a, lo, hi):
    pivot = a[hi]
    i = lo-1
    for j in range(lo, hi):
        if a[j]<pivot:
            i += 1
            tmp = a[i]
            a[i] = a[j]
            a[j] = tmp
    a[hi] = a[i+1]
    a[i+1] = pivot
    return i+1



In [32]:

    
quick_sort(a)



In [ ]: