## Unique and Complicated Sorting

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

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Why Two Kay
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX
Contact:

### Unique and Complicated Sorting

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.

Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

### Re: Unique and Complicated Sorting

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.

Unparallelogram
Posts: 336
Joined: Mon Jul 28, 2008 4:16 am UTC

### Re: Unique and Complicated Sorting

There's lots of clever ways to reinterpret stuff like insertion sort. For example, gnome sort is equivalent in some sense to insertion sort.

Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

### Re: Unique and Complicated Sorting

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.

psykx
Posts: 408
Joined: Sat Feb 23, 2008 11:24 pm UTC
Location: England
Contact:

### Re: Unique and Complicated Sorting

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.

plams
Posts: 35
Joined: Fri Oct 13, 2006 12:08 am UTC
Location: denmark

### Re: Unique and Complicated Sorting

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.

Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

### Re: Unique and Complicated Sorting

Wait a minute...
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Cheese> I love you

gometro33
Posts: 1
Joined: Fri Apr 03, 2009 9:16 pm UTC

### Re: Unique and Complicated Sorting

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.

PM 2Ring
Posts: 3618
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: Unique and Complicated Sorting

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.

Likpok
Posts: 471
Joined: Tue Feb 20, 2007 6:21 am UTC
Location: :noitacoL
Contact:

### Re: Unique and Complicated Sorting

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.

Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Unique and Complicated Sorting

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.

deconvoluted
Posts: 94
Joined: Fri Dec 19, 2008 4:40 pm UTC

### Re: Unique and Complicated Sorting

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.

Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Unique and Complicated Sorting

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.

deconvoluted
Posts: 94
Joined: Fri Dec 19, 2008 4:40 pm UTC

### Re: Unique and Complicated Sorting

Darnit, you're right. I didn't think that through long enough.

Amnesiasoft
Posts: 2573
Joined: Tue May 15, 2007 4:28 am UTC
Contact:

### Re: Unique and Complicated Sorting

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.