Sorting



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)


Out[22]:
[0,
 1,
 4,
 11,
 32,
 42,
 59,
 59,
 71,
 87,
 94,
 120,
 127,
 163,
 182,
 192,
 195,
 196,
 221,
 229,
 230,
 234,
 238,
 246,
 256,
 260,
 272,
 277,
 297,
 302,
 320,
 322,
 330,
 334,
 338,
 344,
 349,
 363,
 410,
 424,
 439,
 442,
 471,
 474,
 480,
 492,
 501,
 512,
 513,
 515,
 518,
 530,
 543,
 547,
 555,
 581,
 611,
 614,
 622,
 627,
 636,
 639,
 643,
 661,
 664,
 672,
 683,
 694,
 706,
 732,
 737,
 743,
 755,
 769,
 770,
 773,
 783,
 793,
 809,
 820,
 820,
 826,
 845,
 853,
 874,
 888,
 889,
 895,
 896,
 902,
 904,
 911,
 925,
 940,
 961,
 978,
 980,
 991,
 992,
 996]

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)


Out[32]:
[0,
 1,
 4,
 11,
 32,
 42,
 59,
 59,
 71,
 87,
 94,
 120,
 127,
 163,
 182,
 192,
 195,
 196,
 221,
 229,
 230,
 234,
 238,
 246,
 256,
 260,
 272,
 277,
 297,
 302,
 320,
 322,
 330,
 334,
 338,
 344,
 349,
 363,
 410,
 424,
 439,
 442,
 471,
 474,
 480,
 492,
 501,
 512,
 513,
 515,
 518,
 530,
 543,
 547,
 555,
 581,
 611,
 614,
 622,
 627,
 636,
 639,
 643,
 661,
 664,
 672,
 683,
 694,
 706,
 732,
 737,
 743,
 755,
 769,
 770,
 773,
 783,
 793,
 809,
 820,
 820,
 826,
 845,
 853,
 874,
 888,
 889,
 895,
 896,
 902,
 904,
 911,
 925,
 940,
 961,
 978,
 980,
 991,
 992,
 996]

In [ ]: