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 [ ]:

``````