https://codingkaiser.blog/2021/10/20/most-bizzare-sorting-algorithms-you-will-ever-see/ Coding Kaiser Menu * Twitter * Homepage * Posts * About me * Contact Search Search for: [ ] [Search] Menu Search Coding Kaiser * Twitter Close Search for: [ ] [Search] * Twitter * Homepage * Posts * About me * Contact Algorithms Computer Science Unconventional Sorting Algorithms [2a0f574340fd2] by CodingKaiser October 20, 2021 Comments 2 [0__pmmiyuikdhok-vr] Sorting is a fundamental necessity in computer programming, but not all sorting algorithms were "created equal". You probably know that the best complexity for comparison-based sorting is O(NlogN), but today we are going to discuss some revolutionary sorting algorithms that you better avoid using in your own programs. --------------------------------------------------------------------- Hold on to your seats, here are the most ridiculous sorting algorithms that you ever heard of. Bogosort There are two versions for this algorithm, one is deterministic and the other is not -- which means there is no bound for its runtime. The pseudo-code for the algorithm is as follows: while not is_sorted(list): shuffle(list) This one above is the non-deterministic version, we basically shuffle our list until we get lucky. We can take advantage of the fact that a list of N elements has N! orderings, which means we can just check all of the possible orderings and report which is sorted. This deterministic version has an average performance of O((n+1)!). Code for the algorithm: def is_sorted(data): return all(a <= b for a, b in zip(data, data[1:])) def bogosort(data): while not is_sorted(data): shuffle(data) return data --------------------------------------------------------------------- Stalin Sort This one is one of my favorites, I even went as far as tweeting about it. Why use conventional sorting algorithms when you can use stalin-sort in O(n)? https://t.co/FyBdpO2ula-- Eliran (@CodingKaiser) October 06, 2021 This algorithm just forces the list to get ordered in a sorted manner. An element that's not in the right order is just thrown into the gulag. Stalin sort has an astonishing performance of O(n), highly recommend. In case you find it somehow useful here's the code in a copiable version def stalin_sort(arr): if arr == [] return arr max_val = arr[0] sorted_arr = [] for val in arr: if val >= max_val: sorted_arr.append(val) max_val = val else: print(f"{val} sent to Gulag") return sorted_arr --------------------------------------------------------------------- Sleep Sort Although this is far from an ideal sorting algorithm I find the idea pretty cool. Given a list [5,2,1,3] , we will dispatch 4 threads that will sleep for 5,2,1,3 seconds and print the time they slept for. import threading from time import sleep items = [5,2,1,3] def sleep_sort(i): sleep(i) print(i) threads = [] for i in items: thread = threading.Thread(target=sleep_sort, args=(i,)) threads.append(thread) thread.start() for t in threads: t.join() Sleep sort has the performance of O(max(input)+n) -- quite a revolution right here. --------------------------------------------------------------------- These 3 sorting algorithms are the ones that I found the most amusing and interesting to cover, but there are many more of them. Here's a few more from xkcd, which some I found to be painfully true. [50b7c-1gs-] Leave a comment with your favorite and amusing algorithms. --------------------------------------------------------------------- Here is my Twitter. Here are my other links. Share this: * Tweet * * More * * * * * Telegram * WhatsApp * * Email * Like this: Like Loading... TagsAlgorithms * sorting * sorting algorithms 2 comments on "Unconventional Sorting Algorithms" 1. [eb00626da1] Gary October 21, 2021 My current fave: for each element, 3d print a bar that long (in parallel, with lots of 3d printers). Then take the sheaf of bars, put it end-up on a counter, and pull out the top one, then the next top, etc. O(n) + O(n/printers), with a very large constant. LikeLike Reply + [2a0f574340] CodingKaiser October 21, 2021 Sounds like a Spaghetti-Sort (https://en.wikipedia.org/wiki/ Spaghetti_sort) with a budget LikeLike Reply Leave a Reply Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] WordPress.com Logo You are commenting using your WordPress.com account. ( Log Out / Change ) Google photo You are commenting using your Google account. ( Log Out / Change ) Twitter picture You are commenting using your Twitter account. ( Log Out / Change ) Facebook photo You are commenting using your Facebook account. ( Log Out / Change ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] Post navigation Previous Post Related Coding Kaiser Subscribe to Blog via Email Enter your email address to subscribe to this blog and receive notifications of new posts by email. Email Address: [ ] Subscribe * Twitter Website Powered by WordPress.com. Send to Email Address [ ] Your Name [ ] Your Email Address [ ] [ ] loading [Send Email] Cancel Post was not sent - check your email addresses! Email check failed, please try again Sorry, your blog cannot share posts by email. %d bloggers like this: [b]