Unique and Complicated Sorting

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Unique and Complicated Sorting

Postby Why Two Kay » Fri Apr 03, 2009 2:11 am UTC

My computer science class, which is really just a Data Structures with Java class, is working on sorting and searching right now, and I am required to research some different methods of sorting. I have already run though the major O(N2) sorts like Insertion, Bubble, and Selection, and many of the O(NlogN) sorts such as Merge, Heap, and Quick. Additionally we have covered Radix sort.

In addition to these rather standard sorts, we are required to research (or write) one of our own sorts and present it. I don't want to just grab one off of wikipedia, since the rest of my class will most likely do the same. I've already looked into Bozo sort, Stooge sort, Random-swap sorts, and permutations-until-you-get-a-sorted-one sorts. Those are always fun to research and look into, as inefficient sorts can be rather clever (and painful to watch run!).

But what I'm looking for are really unique sorting methods that have (somewhat) good running times. Anything below O(N2) should work quite fine, as we are required to sort a list of 1 million elements with it. So obviously any O(N!) are out of the question. [Before I knew this requirement, I began work on a O(2^(N!)), but gave up after sorting 10+ elements became untestable.]

I want to do something cool with this assignment and not just cover "just another sort" that we happened to not cover in class.

What unique or overly-complicated sorts, with decent run times, are your favorite/do you know?
tl;dr - I said nothing important.
User avatar
Why Two Kay
 
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX

Re: Unique and Complicated Sorting

Postby Berengal » Fri Apr 03, 2009 3:07 am UTC

Bitonic sort, O(n log(n)^2). The sequence of comparisons isn't data-dependant so it's highly parallelizable (think GPGPU), making it bleeding fast.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
User avatar
Berengal
Superabacus Mystic of the First Rank
 
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

Re: Unique and Complicated Sorting

Postby Unparallelogram » Fri Apr 03, 2009 5:31 am UTC

There's lots of clever ways to reinterpret stuff like insertion sort. For example, gnome sort is equivalent in some sense to insertion sort.
Unparallelogram
 
Posts: 338
Joined: Mon Jul 28, 2008 4:16 am UTC

Re: Unique and Complicated Sorting

Postby Berengal » Fri Apr 03, 2009 9:25 am UTC

Out of curiosity, what's the slowest sort known which doesn't rely on randomness but where each iteration of the algorithm is guaranteed to bring it closer to the sorted state? I'm thinking permutations, but is there a slower one? Or one with a guaranteed best case of more than O(n)?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
User avatar
Berengal
Superabacus Mystic of the First Rank
 
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

Re: Unique and Complicated Sorting

Postby psykx » Fri Apr 03, 2009 12:37 pm UTC

without data that is partially sorted in a known way there is no way of beating O(n). Quick sort is probably worth covering it might not be unique but it is quick and very common.
Berengal wrote:Only if they're killer robots. Legos are happy robots. Besides, even if they were killer robots it wouldn't stop me. You can't stop science and all that.
User avatar
psykx
 
Posts: 404
Joined: Sat Feb 23, 2008 11:24 pm UTC
Location: England

Re: Unique and Complicated Sorting

Postby plams » Fri Apr 03, 2009 12:56 pm UTC

Berengal wrote:Out of curiosity, what's the slowest sort known which doesn't rely on randomness but where each iteration of the algorithm is guaranteed to bring it closer to the sorted state? I'm thinking permutations, but is there a slower one? Or one with a guaranteed best case of more than O(n)?


Hanoi sort might not be the slowest non-random sort, but it IS slow and also fun.
plams
 
Posts: 35
Joined: Fri Oct 13, 2006 12:08 am UTC
Location: denmark

Re: Unique and Complicated Sorting

Postby headprogrammingczar » Fri Apr 03, 2009 1:54 pm UTC

How about [url=en.wikipedia.org/wiki/shors_algorithm]Shor's Algorithm[/url].

Wait a minute...
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
User avatar
headprogrammingczar
 
Posts: 3023
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Unique and Complicated Sorting

Postby gometro33 » Fri Apr 03, 2009 9:21 pm UTC

My favorites are counting sort, bucket (bin) sort, topological sort, and heap sort. Depending on what you're sorting, how much you know about the data (distribution, range, etc.), and what you want to do with the sorted data each can be used very effectively.
gometro33
 
Posts: 1
Joined: Fri Apr 03, 2009 9:16 pm UTC

Re: Unique and Complicated Sorting

Postby PM 2Ring » Sat Apr 04, 2009 10:44 am UTC

plams wrote:
Berengal wrote:Out of curiosity, what's the slowest sort known which doesn't rely on randomness but where each iteration of the algorithm is guaranteed to bring it closer to the sorted state? I'm thinking permutations, but is there a slower one? Or one with a guaranteed best case of more than O(n)?


Hanoi sort might not be the slowest non-random sort, but it IS slow and also fun.

Hanoi sort is cute. Freecell sort is probably a bit faster, but more entertaining. :)
Towers of Hanoi trivia: in the general case (going from any legal configuration to any other), there are often multiple distinct solutions.

Slow sorting algorithms do have a use: they can make entertaining screen savers. Eg, choose a column (or row) at random & sort it.

...

FWIW, the first computer sorting algorithm I learned was radix sort. I learned it several years before I learned about bubble sort, insertion sort, etc. Radix sort was very handy, back in the days of punched cards.

I see that nobody's mentioned Shell Sort yet.

My favourite approach is to use Quicksort on large data sets, insertion or selection sort on smallish data sets, and a sorting network for the smallest data sets.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unique and Complicated Sorting

Postby Likpok » Sun Apr 12, 2009 4:43 am UTC

Look up Dijkstra's Smoothsort. It's a modified heapsort that takes advantage of sortedness in the incoming data. It's very fast (nlogn worst, n best), however it is quite complicated. Compared to the quicksort 5-10 liner, it is not quite so easy.
There's an art to cooking toast
Never try to guess
Cook it till it's smoking
Then twenty seconds less.
User avatar
Likpok
 
Posts: 471
Joined: Tue Feb 20, 2007 6:21 am UTC
Location: :noitacoL

Re: Unique and Complicated Sorting

Postby Yakk » Sun Apr 12, 2009 5:45 pm UTC

Balanced-tree algorithms produce a sort. Sometimes this sort is quite interesting in how it works. :-)

You could try implementing a sort inspired by something like skip lists, or R-B trees, or ...

Another interesting approach might be to try it from an alphabetical-type perspective.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10370
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unique and Complicated Sorting

Postby deconvoluted » Thu Apr 30, 2009 9:27 pm UTC

Actually, the "Shor's algorithm" quip might not be a bad idea.

I think you might be able to design an extremely inefficient quantum bubble sort using repeated applications of Grover's search operator.

Oooh, or you might be the first person to make the Deutsch-Josza Algorithm actually do anything! (It finds whether a function is balanced).
Pick an oracle that decides whether the items of a list are larger or smaller than than a random list element. Put the list through the algorithm: if the oracle is balanced, then you have the middle element of the list.
Remove that element, do it again. Get the next middle element that comes out, compare it with the first "middle", and put it above or below respectively.
Keep doing that til you've sorted the list :)

Non-quantum: What about a genetic sort? The fitness function is probably O(n), so you're looking at something worse than O(n^2), but it has a cool name.
deconvoluted
 
Posts: 94
Joined: Fri Dec 19, 2008 4:40 pm UTC

Re: Unique and Complicated Sorting

Postby Yakk » Thu Apr 30, 2009 10:28 pm UTC

deconvoluted wrote:Actually, the "Shor's algorithm" quip might not be a bad idea.

I think you might be able to design an extremely inefficient quantum bubble sort using repeated applications of Grover's search operator.

Oooh, or you might be the first person to make the Deutsch-Josza Algorithm actually do anything! (It finds whether a function is balanced).
Pick an oracle that decides whether the items of a list are larger or smaller than than a random list element. Put the list through the algorithm: if the oracle is balanced, then you have the middle element of the list.

For non-middle elements, the function is not constant. Thus the DJ algorithm isn't guaranteed to work.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10370
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unique and Complicated Sorting

Postby deconvoluted » Thu Apr 30, 2009 10:39 pm UTC

Darnit, you're right. I didn't think that through long enough.
deconvoluted
 
Posts: 94
Joined: Fri Dec 19, 2008 4:40 pm UTC

Re: Unique and Complicated Sorting

Postby Amnesiasoft » Tue May 05, 2009 12:10 pm UTC

Shear Sort is a parallel algorithm, with an worst case time of O(n1/2 log n), running on n processors. Its absolute speed up is O(n1/2), so its efficiency is O(1/n1/2).

I quite like Shear Sort.
User avatar
Amnesiasoft
 
Posts: 2575
Joined: Tue May 15, 2007 4:28 am UTC
Location: Colorado


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 7 guests