STEM

Sorting, grouping, defragging…a visual working demo

Watching a sorting, grouping, or just a defragmentation process graphically is both educational and curiously satisfying. So, I created a Python script that sorts a set of randomly placed, randomly colored, ungrouped tiles on a board by colors so that all like-colored tiles are placed consecutively, adjacently. Think of it like the good old Windows Defragmenter visual. The script will also shows the process in real-time (actually slowed down by a LOT from actual CPU speed so that we can actually see each step) and in a graphical way. You can run it right on this page (below) to see it in action. I’ll explain at a high level how it’s designed and works after you try it out.

To start it, click on Run button: and the script generate a 10×10 grid and display a message on screen to press SPACEBAR to start the sorting-grouping process. Be sure to click on grid graphics first to ensure your keyboard press will be sent to that window, and press the SPACE key on your keyboard. Once the grouping is complete, press Stop button to end the session. You can Run it again as many times as you wish…each time a new random grid is generated.

Explanation of code

The script creates a 10×10 grid (but it’s fully scalable to any dimension) of titles. The titles get a random color assigned to it from a choice of 10 colors (that I defined) which are: red, grn, blu, yell, cyn, magenta, org, pur, tea, and bla. In code they’re defined as a list of tuples so I can use RGB format. e.g.

colors = [
    (255,99,71),   # tomato Red
    (0, 255, 0),   # Green
    (0, 0, 255),   # Blue
    (255, 255, 0), # Yellow
    (0, 255, 255), # Cyan
    (255, 0, 255), # Magenta
    (255, 165, 0), # Orange
    (128, 0, 128), # Purple
    (0,128,128),   # Teal    
    (0, 0, 0)     # Black

]

Using Pygame library, I draw the grid and fill the tiles with colors as the randomizer assigned to them each session. Each title is tracked in different ways: a dictionary to store the rectangles and their colors:

color_rects = {color: [] for color in colors}

a list that stores the sorted tiles so that we know which ones are already in correct place, and which are not, so that we can visually simulate ‘grabbing’ the next tile and place it in its right order. This is shown on graphically as an unsorted tile’s position turning light gray first, and then being placed adjacent to the current tiles being placed in order. Additionally, there is a list of unsorted tiles, and another dictionary for tracking of which colors appear in the grid and how many times. As this is random at every execution, the code cannot know beforehand, therefore it has to track the metric in real-time.

So, how does the code decide what color to sort first? It sorts in the order of the ‘colors’ list…so, it’ll start to sort and group red tiles first, then green, then blue, and so on until black. However, since colors are randomly picked from the list, it’s very possible that at times, not all colors will be picked…there may theoretically be all titles in just 1 or 2 colors. In that case, the sorting algorithm will still start in the same order described but if it does not find a tile with that color, it simply moves on to the next color until it finds a color that exists on the grid. Essentially, this is how it works: it will place a tile (e.g. first is red) starting from the top-left position of the window (first row), then it’ll look for another tile of same color in the entire board (e.g. red) and if it finds it somewhere, it’ll turn that tile position to light gray and put the red tile next to the previous red tile. This continues until it cannot find any more tiles of the color it’s sorting (e.g. red), then it works the same way for the next color (e.g. green) and the process continues until all tiles are nicely sorted and grouped together. After the process is completely, there should be no gaps (e.g. light gray tiles) left on the board!

When you start the app, you’ll notice there’s a text output at bottom of the grid window that shows how many tiles were created randomly at which tiles were given which colors. It may look like this (10×10 grid, so they add up to 100 tiles total):

Color (255, 99, 71) appears 8 times
Color (0, 255, 0) appears 16 times
Color (0, 0, 255) appears 12 times
Color (255, 255, 0) appears 8 times
Color (0, 255, 255) appears 10 times
Color (255, 0, 255) appears 10 times
Color (255, 165, 0) appears 10 times
Color (128, 0, 128) appears 7 times
Color (0, 128, 128) appears 6 times
Color (0, 0, 0) appears 13 times

The trickiest part of the code is the code to keep track of each tile and its random color and random position, and still being able to sort them and know which tiles have been already sorted and which ones haven’t, and visually depicting the whole process which requires a graphic library as Pygame or Tkinter or Turtle. Finally, to show each step at a pace that our eyes and mind can track and comprehend, delays are put in the code to slow down the pace…otherwise, the whole thing would happen in an instance on any modern CPU making it impossible for us to actually see what steps were taken in-between to arrive at the final stage.

NOTE: The code embedded here is possible because trinket io platform is running my code on an online Python interpreter and server…while it’s convenient for demos and sharing, it is not as flexible. It also may show incorrect outputs at times or not be able to produce outputs for certain code. My underlying code however is a Windowed-app that can be moved around, resized etc. and the count of tiles are always accurate when executed on local Python machine. If you’re interested in getting the full code, you can contact me from the home page, or via email: trseattle at outlook dot com.

For more of my programming related posts (and many with complete source codes posted), click here. Be sure to visit often as I typically post many updates per month, sometimes more than once a day depending on time and material.

I hope this was interesting for you. Thanks for reading!



Interested in creating programmable, cool electronic gadgets? Give my newest book on Arduino a try: Hello Arduino!

Leave a Reply

Your email address will not be published. Required fields are marked *

Back To Top
+