Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unconventional Sorting Algorithms

codingkaiser.blog

Post reply on HN
Print view View original

51–60 of 60 posts

Re: Unconventional Sorting Algorithms

#51

Post by robotresearcher »

cratermoon wrote: post #22
nayuki wrote: post #19

My favorite is still slowsort. https://en.wikipedia.org/wiki/Slowsort > It is a reluctant algorithm based on the principle of multiply and surrender. It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis. https://www.mipmip.org/tidbits/pasa.pdf > The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the…

My favorite is SleepSort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

SleepSort is a subject of the posted article.

Re: Unconventional Sorting Algorithms

#53

Post by kjeetgill »

Sohcahtoa82 wrote: post #38

I like Intelligent Design sort: > The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally sorted in some way that transcends our naïve mortal understan…

Ohhhhhh... fascinating! Is there a good metric for how well sorted a list is? Maybe for every pair of elements, how many are in the correct order?

Given a random shuffle of a list, what are the chances that another shuffle would be more sorted? There's a life lesson in here, I know it...

Re: Unconventional Sorting Algorithms

#54

Post by pedrosorio »

kjeetgill wrote: post #53
Sohcahtoa82 wrote: post #38

I like Intelligent Design sort: > The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally sorted in some way that transcends our naïve mortal understan…

Ohhhhhh... fascinating! Is there a good metric for how well sorted a list is? Maybe for every pair of elements, how many are in the correct order? Given a random shuffle of a list, what are the chances that another shuffle would be more sorted ? There's a life lesson in here, I know it...

https://www.baeldung.com/cs/counting-inversions-array

Re: Unconventional Sorting Algorithms

#55

Post by lifthrasiir » 

    import ctypes
    
    def mutation_sort(a):
        for i, v in enumerate(a):
            ctypes.c_int.from_address(id(v) + 24).value = i # for x86-64, adjust the offset for your platform
        return a
    
    def is_sorted(a):
        prev = None
        for v in a:
            if prev is not None and prev > v: return False
            prev = v
        return True
    
    is_sorted(mutation_sort([3000, 1000, 7000, 8000, 2000])) # prints True

Re: Unconventional Sorting Algorithms

#56

Post by [deleted] »

cevi wrote: post #50
michaelmior wrote: post #14

Quantum bogosort is probably my personal favorite. Randomly permute the input using a quantum source of entropy. If the input is not sorted, destroy the universe. The only universe remaining is one where the input was already sorted. Runs in O(n) time.

Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?

[deleted]

Re: Unconventional Sorting Algorithms

#58

Post by nickcw »

Here is my offering

https://gist.github.com/ncw/5419af0e255d2fb62b98

It's a Go channel based quicksort. It sorts a channel of ints using O(n) go routines! Interestingly it doesn't need to know how many ints are in the channel at the start.

Not a practical sort method but fun to see the Go concurrency primitives in use.

Re: Unconventional Sorting Algorithms

#59

Post by dfox »

dmurray wrote: post #36
dfox wrote: post #9

Earlier quoted context omitted.

It is if you ignore how the underlying OS implements multitasking and sleep() in particular. And the kernel-side implementation usually involves some kind of priority queue of sleeping threads. So taken as a whole sleep-sort is just an convoluted implementation of heap-sort that outsources the actual sorting to OS.

The kernel could use a different implementation of multitasking, e.g. keep the threads in a circular doubly linked list instead of a priority queue. This wouldn't be optimal for a general-purpose OS, but works for our custom O(n) sorting machine.

Then the resulting complexity would be O(n^2). With some kind of heap-like priority queue as used in typical general purpose OS you get O(n*log(n)) or something close to that.

Re: Unconventional Sorting Algorithms

#60

Post by michaelmior »

cevi wrote: post #50
michaelmior wrote: post #14

Quantum bogosort is probably my personal favorite. Randomly permute the input using a quantum source of entropy. If the input is not sorted, destroy the universe. The only universe remaining is one where the input was already sorted. Runs in O(n) time.

Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?

This is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.
Post reply on HN