Don’t ever Bubble Sort your socks.
I don’t mind the sorting and folding part of doing laundry, especially if I have a good podcast or audio book to distract me. That’s a good thing as I have a six person household. Things used to be easier when the kids were very different sizes; now as they are mostly teenagers things can get confusing. Even with all those other clothes, it is always the socks that take the most time to match up. It’s a good thing I learned useful strategies for sock matching in graduate school to make the process the most efficient it can be!
Imagine a big pile of unmatched socks that vary in color, pattern, and size. If you pick up a single sock, let’s say it is a blue sock with pizza slices on it, and then you hunt for it’s mate, you are bubble sorting. Bubble sorting is the simplest sorting algorithm. You are “bubbling up” each sock individually to see if it matches the pizza sock in your hand. Bubble sorting is generally regarded as inefficient.
“In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.’’¹
That’s a pretty sick burn for Information Theory. I had thought it would be a quick search to find the person who first contemplated the efficiency of the bubble sort but that seems to have been lost to time. Bubble sorting became a thing sometime around 1960. Hating bubble sorting became a thing soon thereafter. That may/may not have anything to do with my not being able to put a name to the algorithm.
Of course, the ‘sorting’ part of bubble sorting is about putting things in order, not matching exactly. In the case of socks, assuming you have not lost one mysteriously (big assumption, I know), matching them up is simply sorting that pile twice so that you end up with two perfectly matched rows.
If laundry could run code (what a glorious invention that would be!), and our socks were integers (less glorious), we could run the following:
def bubbleSort(socks):
length = len(socks)
for i in range(length-1):
for j in range(0, length-i-1):
if socks[j] > socks[j+1] :
socks[j], socks[j+1] = socks[j+1], socks[j]
socks = [10, 3, 7, 8, 9, 1, 5, 2]
bubbleSort(socks)
print(socks) After, we would have our #1 socks, then our #2 socks, etc., all matched up (if you are still with me on this quickly falling apart metaphor, print() now is an action for a real world robot). First our magic robot counts the number of socks length = len(array). You could have your magic sock matching robot exit the matching loop when the unmatched sock pile is =< 1, but we can do slightly better. By finding the maximum length (max pairs of socks) and then running the matching action one time less than the max number of pairs range(length-1) we have saved ourselves the effort of one matching attempt as the final two unsorted socks should match.
We began our laundry sorting before by double bubble sorting (‘Double Bubble Sorting’, first coined by C. Gibson, 2023). There are two other simple sort algorithms we can try on our socks: insertion sort and selection sort. Both can be used on their own or as part of a more complex algorithm. Like bubble sorting, they also work best with smaller amounts of data (socks). Please don’t attempt to set some sort of sock matching world record with any of these algorithms.
Let’s try an insertion sort on our sock pile (I hope you have a good amount of floorspace to use). Set down one sock. Pick up another sock. Is this sock’s number greater than or less than the first sock’s? Please your second sock down according to its number so that you end up with two ordinal line of socks.
def insertionSort(socks):
for step in range(1, len(socks)):
key = socks[step]
j = step - 1
while j >= 0 and key < socks[j]:
socks[j + 1] = socks[j]
j = j - 1
socks[j + 1] = key
socks = [10, 3, 7, 8, 9, 1, 5, 2]
insertionSort(socks)
print(socks)This is slightly more efficient than bubble sorting. Unfortunately, I just don’t have enough floorspace to insertion sort my socks, so let’s try a selection sort instead.
Pick up one sock from the pile and set it down. Now pick up another. Is it’s number greater than or less than the sock on the floor? If the number is less than, place this sock on top of the first sock. If greater than, place it beneath the floor sock. Continue in this patter until all socks are sorted.
Selection sorting is a lot like insertion sorting but with one key difference: selection sorting never takes up more memory/space than that of the original unsorted data/socks. Insertion sorting will always take up the amount of memory/space of the original data/sock pile +1.
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
if array[i] < array[min_idx]:
min_idx = i
(array[step], array[min_idx]) = (array[min_idx], array[step])
socks = [10, 3, 7, 8, 9, 1, 5, 2]
size = len(socks)
selectionSort(socks, size)
print(socks)I’ll admit that real world socks are not a perfect analogy for data sorting, but sorting techniques in the real world and computer science do have some practical overlap. Plus, sorting socks is boring enough of a task that you will have extra brain capacity to now name your sort technique as you go. I plan on continuing my search for the perfect sock sorting algorithm. If you have any suggestions, please let me know.
[1] Knuth, D. The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998.
