bubble sort all the things
In [102]:
%matplotlib inline
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython import display
import random
import numpy as np
First up, generating a random list to sort then actually sorting it:
In [49]:
data = [random.randint(0,100) for i in range(100)]
plt.title("The Unsorted data")
plt.bar(np.arange(len(data)), data)
plt.show()
def bubble_sort(data):
done = False
while not done:
swapped = False
for i in range(0, len(data)-1):
if data[i] > data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
swapped = True
if not swapped:
done = True
return data
plt.title("All sorted")
plt.bar(np.arange(len(data)), bubble_sort(data));
In [96]:
NUMS = 10
x = np.arange(NUMS)
y = np.random.randint(0, 100, size=NUMS)
x,y
Out[96]:
changing bubble sort to get back a list containing all the steps from the initial list to the final sorted list:
In [97]:
def bubble_sort_2(data):
done = False
all_the_sorts = []
all_the_sorts.append(data)
while not done:
swapped = False
for i in range(0, len(data)-1):
if data[i] > data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
all_the_sorts.append(data)
swapped = True
if not swapped:
done = True
return all_the_sorts
print(y)
bs_sorts = bubble_sort_2(y)
bs_sorts
Out[97]:
now to eyeball it:
In [106]:
y = bs_sorts
fig, ax = plt.subplots()
fig.set_size_inches(8,6)
ax.set_title("Bubble Sort")
ax.set_xlabel('X')
ax.set_ylabel('Y')
# this displays the data to be sorted as a scatter plot
original_line = ax.scatter(x,y[0], alpha = 0.2, label = "original data")
# the final sorted line.
sorted_line = ax.plot(x,y[-1], lw=2, alpha = 0.7, label="sorted")
# this displays the data being sorted in a scatter plot
scatterplot = ax.scatter(x,y[0], label="sorting")
def animate(i):
scatterplot.set_offsets(np.c_[x,y[i]])
ani = animation.FuncAnimation(fig, animate,
frames=len(y), interval=150, repeat=False)
#print(f"it took {len(qs_steps)-1} steps to sort {len(qs_steps[0])} items")
plt.legend()
ani.save("bubblesort_animate.mp4")
In [ ]: