{"id":10662,"date":"2023-11-17T09:38:13","date_gmt":"2023-11-17T09:38:13","guid":{"rendered":"https:\/\/www.mrericsir.com\/blog\/?p=10662"},"modified":"2024-07-10T02:49:00","modified_gmt":"2024-07-10T02:49:00","slug":"bubblewrap-sort","status":"publish","type":"post","link":"https:\/\/www.mrericsir.com\/blog\/technology\/bubblewrap-sort\/","title":{"rendered":"Bubblewrap sort"},"content":{"rendered":"\n
\"bubble<\/a>
Photo by creative_stock<\/a><\/figcaption><\/figure>\n\n\n\n

The problem<\/strong><\/p>\n\n\n\n

Anyone familiar with computer science algorithms knows about bubble sort<\/a>. In this algorithm, you sort a list of things in “bubbles” by going over it repeatedly in sequence and swapping two bubbles next to one another until they’re all sorted.<\/p>\n\n\n\n

Although this algorithm is simple to explain, it’s really inefficient as you will have to go over the list potentially many, many times until it’s sorted.<\/p>\n\n\n\n

And it has one more problem: isn’t the most fun part of bubbles popping <\/em>them?<\/p>\n\n\n\n

The solution: Bubblewrap sort<\/strong><\/p>\n\n\n\n

Enter bubblewrap sort! This takes advantage of a shortcut most sorting algorithms haven’t even thought of. Here’s how it works.<\/p>\n\n\n\n

After putting everything in our list in bubbles, we simply pop all the bubbles. You know, like bubblewrap. Now the list is empty, and by definition<\/em> an empty list is a sorted list.<\/p>\n\n\n\n

C++ code listing<\/strong><\/p>\n\n\n\n

Here’s an implementation of bubblewrap sort on a C++ vector:<\/p>\n\n\n\n

#include <vector>\n#include <iostream>\n\n\/\/ Perform a bubblewrap sort.\ntemplate <class T>\nvoid bubblewrap_sort(std::vector<T>& vec) {\n    vec.clear();\n}\n\n\/\/ Print the contents of a vector.\ntemplate <class T>\nvoid print_vector(std::vector<T>& vec) {\n    std::cout << \"Vector:\";\n    for (T content : vec) {\n        std::cout << ' ' << content;\n    }\n    std::cout << std::endl;\n}\n\nint main() {\n    \/\/ Create an unsorted list of integers.\n    std::vector<int> list_to_sort;\n    list_to_sort.push_back(3);\n    list_to_sort.push_back(6);\n    list_to_sort.push_back(1);\n    list_to_sort.push_back(-2);\n    list_to_sort.push_back(10);\n\n    \/\/ Print our original list.\n    print_vector(list_to_sort);\n\n    \/\/ Run bubblewrap sort and print our list again!\n    bubblewrap_sort(list_to_sort);\n    print_vector(list_to_sort);\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
Program output:<\/p>\n\n\n\n
Vector: 3 6 1 -2 10
Vector:<\/code><\/code><\/pre>\n\n\n\n
Conclusion<\/strong><\/p>\n\n\n\n
Traditionally we expect a sorting algorithm to return a list with the same elements in a sorted order, but if we shave those requirements down to just returning a sorted list — any <\/em>sorted list, really — the problem becomes much simpler to solve. And more fun, because there’s nothing more satisfying than popping bubblewrap.<\/p>\n","protected":false},"excerpt":{"rendered":"
The problem Anyone familiar with computer science algorithms knows about bubble sort. In this algorithm, you sort a list of things in “bubbles” by going […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_eb_attr":"","slim_seo":{"canonical":"https:\/\/www.mrericsir.com\/blog\/technology\/bubblewrap-sort\/","title":"Bubblewrap sort - MrEricSir.com","description":"The problem Anyone familiar with computer science algorithms knows about bubble sort . In this algorithm, you sort a list of things in \"bubbles\" by going over i"},"autoblue_enabled":true,"autoblue_custom_message":"","autoblue_shares":[],"autoblue_post_url":"","autoblue_publish_document":false,"footnotes":""},"categories":[3],"tags":[15,29,1052],"class_list":["post-10662","post","type-post","status-publish","format-standard","hentry","category-technology","tag-humor","tag-programming","tag-software"],"_links":{"self":[{"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/posts\/10662","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/comments?post=10662"}],"version-history":[{"count":8,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/posts\/10662\/revisions"}],"predecessor-version":[{"id":10670,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/posts\/10662\/revisions\/10670"}],"wp:attachment":[{"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/media?parent=10662"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/categories?post=10662"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mrericsir.com\/blog\/wp-json\/wp\/v2\/tags?post=10662"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}