Author |
Topic: Sorting Geometrically-distributed values (Read 552 times) |
|
KWillets
Junior Member
Posts: 84
|
 |
Sorting Geometrically-distributed values
« on: Oct 28th, 2014, 11:02am » |
 Quote  Modify
|
Hello, it's been a while since I've posted here, but this question seems like it belongs here.
I need to sort integers with a geometric distribution (eg P(1)=.5, P(2)=.25, .125...), but I'm having trouble finding references on the problem.
It seems like o(n). I tried something like Quicksort where it splits between == min and > min, and recurses on the >min part. I'm experimenting with doing one pass and resetting the min as lower values are encountered.
The recurrence is something like C(n)=P*n + C((1-P)n), i.e. fairly easy to get o(n).
It seems like a simple algo, but I can't find any mention of it. The only examples I've found are Groupsort and some kind of counting sort where the highest bin is all the remaining values; these seem needlessly complicated and data-dependent.
Has anybody seen this problem?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Sorting Geometrically-distributed values
« Reply #1 on: Oct 28th, 2014, 2:11pm » |
Quote Modify
|
I haven't seen the problem before. But I agree that it seems solvable in O(n); for P=1/2 a very skewed binary tree comes to mind. For smaller P there's probably smarter choices, but it doesn't seem to get worse than O(n/P).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Sorting Geometrically-distributed values
« Reply #2 on: Oct 28th, 2014, 3:32pm » |
Quote Modify
|
It's funny, because I've since found benchmarks of quicksort on various distributions (I searched for "exponential distribution" instead of geometric) and found linear times, but no discussion of it.
Quicksort works for this if it happens to pick the median equal to the minimum; that's how I found this before trying an explicit min. However 2-way quicksort can run into problems in one direction, eg splitting < and >=, since it will fail to split out the min in that case. Ternary will work with pivot = either min or max.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print