Before running this notebook, be sure that you have previously executed the following commands, which we specified in the Before You Begin section of the book:
pip install ipympl
conda install nodejs
jupyter labextension install @jupyter-widgets/jupyterlab-manager
jupyter labextension install jupyter-matplotlib
%matplotlib widget
pip install pysine
ipython selectionsortanimation.py 10
selection_sort
function in the next subsection implements the selection sort algorithm but is interspersed with:yield
and yield from
statements that provide values for the FuncAnimation
to pass to the update
functionplay_sound
calls to play musical notesyield
and yield from
make selection_sort
a generator functionFuncAnimation
obtains values on demand from the generator and passes them to update
to animate the algorithm.yield
Statements¶yield
keyword returnq the next generated item, then the function's execution suspends until the program requests another itemyield
Statements (cont.)¶def square_generator(values):
for value in values:
yield value ** 2
numbers = [10, 20, 30]
squares = square_generator(numbers)
for number in squares:
print(number, end=' ')
yield
Statements (cont.)¶next
StopIteration
exception, which is how a for
statement knows when to stop iterating through any iterable objectsquares = square_generator(numbers)
next(squares)
next(squares)
next(squares)
next(squares)
# selectionsortanimation.py
"""Animated selection sort visualization."""
from matplotlib import animation
import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns
import sys
from ch11soundutilities import play_sound
update
Function That Displays Each Animation Frame¶FuncAnimation
calls update
once per animation frame to redraw the animation’s graphical elementsupdate
method’s frame_data
parameter receives a tuple, which we unpack into:data
—the array being sortedcolors
—an array of color names containing the specific color for each barswaps
—an integer representing the number of swaps performed so farcomparisons
—an integer representing the number of comparisons performed so fardef update(frame_data):
"""Display bars representing the current state."""
# unpack info for graph update
data, colors, swaps, comparisons = frame_data
plt.cla() # clear old contents of current Figure
# create barplot and set its xlabel
bar_positions = np.arange(len(data))
axes = sns.barplot(bar_positions, data, palette=colors) # new bars
axes.set(xlabel=f'Comparisons: {comparisons}; Swaps: {swaps}',
xticklabels=data)
flash_bars
Function That Flashes the Bars About to be Swapped¶flash_bars
before and after a swap to flash the corresponding barsyield
statementsyield
throughout this example returns a tuple of the values the FuncAnimation
passes to update
's frame_data
parameterplay_sound
calls occur before the swap, the notes play in decreasing pitch to indicate that the values are out of orderplay_sound
calls occur after the swap, the notes play in increasing pitch to indicate that the values are now in orderdef flash_bars(index1, index2, data, colors, swaps, comparisons):
"""Flash the bars about to be swapped and play their notes."""
for x in range(0, 2):
colors[index1], colors[index2] = 'white', 'white'
yield (data, colors, swaps, comparisons)
colors[index1], colors[index2] = 'purple', 'purple'
yield (data, colors, swaps, comparisons)
play_sound(data[index1], seconds=0.05)
play_sound(data[index2], seconds=0.05)
selection_sort
as a Generator Function¶colors
array specifies that all the bars should be 'lightgray'
initiallyyield
ed, the FuncAnimation
passes them to the update
functionyield
causes the animation to display the bars in their initial unsorted orderdef selection_sort(data):
"""Sort data using the selection sort algorithm and
yields values that update uses to visualize the algorithm."""
swaps = 0
comparisons = 0
colors = ['lightgray'] * len(data) # list of bar colors
# display initial bars representing shuffled values
yield (data, colors, swaps, comparisons)
# loop over len(data) - 1 elements
for index1 in range(0, len(data) - 1):
print('outerloop')
smallest = index1
# loop to find index of smallest element's index
for index2 in range(index1 + 1, len(data)):
print('innerloop')
comparisons += 1
colors[smallest] = 'purple'
colors[index2] = 'red'
yield (data, colors, swaps, comparisons)
play_sound(data[index2], seconds=0.05)
# compare elements at positions index and smallest
if data[index2] < data[smallest]:
colors[smallest] = 'lightgray'
smallest = index2
colors[smallest] = 'purple'
yield (data, colors, swaps, comparisons)
else:
colors[index2] = 'lightgray'
yield (data, colors, swaps, comparisons)
# ensure that last bar is not purple
colors[-1] = 'lightgray'
# flash the bars about to be swapped
yield from flash_bars(index1, smallest, data, colors,
swaps, comparisons)
# swap the elements at positions index1 and smallest
swaps += 1
data[smallest], data[index1] = data[index1], data[smallest]
# flash the bars that were just swapped
yield from flash_bars(index1, smallest, data, colors,
swaps, comparisons)
# indicate that bar index1 is now in its final spot
colors[index1] = 'lightgreen'
yield (data, colors, swaps, comparisons)
# indicate that last bar is now in its final spot
colors[-1] = 'lightgreen'
yield (data, colors, swaps, comparisons)
play_sound(data[-1], seconds=0.05)
# play each bar's note once and color it darker green
for index in range(len(data)):
colors[index] = 'green'
yield (data, colors, swaps, comparisons)
play_sound(data[index], seconds=0.05)
selection_sort
as a Generator Function (cont.)¶comparisons
to keep track of the total number of comparisons performedsmallest
is always colored purple during a pass of the algorithmindex2
is always colored red (the value being compared with the smallest) during a pass of the algorithm’s nested loopyield
s data
, colors
, swaps
and comparisons
, so we can see the purple and red bars indicating the values that are being comparedselection_sort
as a Generator Function (cont.)¶if/else
statement ensures that only one bar is red and one is purple during the comparisons and yield
s values for the next animation frameselection_sort
as a Generator Function (cont.)¶selection_sort
) needs to yield
the results of another, chained generator functions are requiredflash_bars
), in a yield from
statement to ensure that the values yield
ed by flash_bars
“pass through” to the FuncAnimation
for the next update
callselection_sort
as a Generator Function (cont.)¶yield
to draw the next animation frame and play that bar’s noteyield
to draw the next animation frame and play that bar’s musical noteFuncAnimation
terminates when the source of its animation-frame data has no more valuesmain
Function That Launches the Animation¶FuncAnimation
's frames
keyword argument receives a value that specifies how many animation frames to executeframes
keyword argument receives a call to the generator function selection_sort
yield
ed by selection_sort
are the source of the update
function’s frame_data
def main():
number_of_values = int(sys.argv[1]) if len(sys.argv) == 2 else 10
figure = plt.figure('Selection Sort') # Figure to display barplot
numbers = np.arange(1, number_of_values + 1) # create array
np.random.shuffle(numbers) # shuffle the array
# start the animation
anim = animation.FuncAnimation(figure, update, repeat=False,
frames=selection_sort(numbers), interval=50)
plt.show() # display the Figure
Instuctor Note: If this does not execute in your notebook, the Jupyter Lab extensions may have changed--this was still under development when we created the notebook. In this case, just run the script with IPython at the command line.
# call main to execute the animation (we removed the if statement from the script in the book)
main()
The file ch11soundutilities.py
contains two constants that we use to calculate musical note frequencies programmatically and three functions that play MIDI notes
©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.
DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.