Twitter Sort

#1

Post by ExPHAT » Tue, Jan 13, 2015, 11:56 PM UTC

Re: Twitter Sort

#2

Post by TrainedMonkey » Wed, Jan 14, 2015, 1:17 AM UTC

While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic which will complicate handling logic as you need to account for being forever alone without anyone to sort your numbers.

In short, I would advise against deploying this on production until technology is more mature.

Re: Twitter Sort

#3

Post by danvayn » Wed, Jan 14, 2015, 1:23 AM UTC

TrainedMonkey wrote: post #2

While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic w…

Thank you, TrainedMonkey.

Re: Twitter Sort

#4

Post by Mahn » Wed, Jan 14, 2015, 1:30 AM UTC

TrainedMonkey wrote: post #2

While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic w…

Regarding maximum input size, I'm sure it can be forked to implement a tweet-sharding approach.

Re: Twitter Sort

#5

Post by Mahn » Wed, Jan 14, 2015, 1:32 AM UTC

I wonder what's the efficiency of this algorithm in O notation on average.

Re: Twitter Sort

#6

Post by [deleted] » Wed, Jan 14, 2015, 1:41 AM UTC

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

[deleted]

Re: Twitter Sort

#7

Post by statusgraph » Wed, Jan 14, 2015, 1:44 AM UTC

[deleted] wrote: post #6

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

[deleted]

Not quite. Big-O creates an -upper bound-. It could be the upper bound of the best case, the average, or the worst case. (So, for example, one can say quicksort has worst case performance O(n^2) but an expected performance of O(n log n))

Re: Twitter Sort

#8

Post by gkoberger » Wed, Jan 14, 2015, 1:45 AM UTC

If that turns out to be a bit slow, there's always StackSort:

http://gkoberger.github.io/stacksort

Re: Twitter Sort

#9

Post by jayp » Wed, Jan 14, 2015, 1:45 AM UTC

Mahn wrote: post #4

TrainedMonkey wrote: post #2

While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic w…

Regarding maximum input size, I'm sure it can be forked to implement a tweet-sharding approach.

Sharding via a Tweet Storm(TM).

Re: Twitter Sort

#10

Post by coreyja » Wed, Jan 14, 2015, 1:52 AM UTC

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

As tansey said Big-O for the worst case would be O(inf), Best case is O(1), if n is the length of the list, because if the sort returns the speed is independent of the size of the list. The average case is a little harder, but based on the 140 character limit someone else mentioned, I would say that the average case would be O(inf) cause on average it probably wouldn't correctly sort the list.