Genetic Algorithm Improves Shellsort

gstover writes "As a personal programming project recently, I used a genetic algorithm to find a better sequence of increments for Shellsort. It found at least one sequence that out-performs the best previously known by about 5 percent. Here is an article about it (also here). I believe this is the first time a genetic algorithm has actually improved Shellsort."

Re:Nice and all

[jalet]

quicksort doesn't preserve the order of duplicate keys, IIRC

Re:Nice and all

[Pentagram]

Quicksort is slow if the data it is sorting are already almost sorted, a situation which (IIRC) shellshort is particularly efficient at dealing with.

Re:Nice and all

[Yokaze]

Bottom-up mergesort does.
Theta(n log(n)) instead of Theta(n^2) like the (standard) Quicksort.

(Shellsort has Theta(n log(n)^2), IIRC)

Actually this HAS beed done before

[stackdump]

One of my professors at Midwestern State University [mwsu.edu] (texas) has done this before [mwsu.edu]. Although it seems you may have improved on his solution. (but I couldnt find a copy of his paper)

"Faster Shellsort Sequences: A Genetic Algorithm Application", Proceedings of the International Society for Computers and Their Applications(ISCA), April 7-9, 1999. (With Shashidhar Yachavaram) Presented at the conference, Cancun Mexico.

Other sorting attempts using GA's

[Tablizer]

In Melanie Mitchell's wonderful book, "An Introduction to Genetic Algorithms", page 21-27, The author describes using genetic algorithms to find optimal patterns for "sorting networks". They are used for sorting chips (hardware) to sort in chunks of say 16 or 64 units. The order of comparisons is important. Using genetic algorithms, they were able to come very close to the best sequences found by humans. (I don't know if hardware sorting is still used. I had the impression that it is a mainframe thing.)

Thus, optimizing sorting algorithms with GA is not new in itself.

For those who cannot grok Lisp shell sort...

[Anonymous Coward]

Here's Sedgewick's Shell Sort implementation in C [princeton.edu]

Re:Nice and all

[Gumshoe]

I guess it's a nice thing that shellsort is getting improved, and I do realize that this is great for genetic research, but, pardon me for being an uneducated ignorant bastard, does it have any practical value, seeing as quicksort is much faster than shellsort? Or am I wrong?

You're generalising, which is an easy mistake. Quicksort is good but for many data sets, it is very likely suboptimal and another alogorithm would perform better. Shellsort is good for small data sets. In fact, a good quicksort implementation may use shellsort once the divisions get small enough.

Another example:, quicksort is poor at sorting strings. This is because you have to perform a full strcmp() (or equivalent) at each comparison. For this reason, a modified radix sort is often used.

Re:Impressive

[lsdino]

Speeding up shell sort is not very exciting and hardly useful. It's the slowest of the n^2 sorts [wku.edu]. I'm surprised no one has pointed this out. Where are the computer geeks?


Quoting from your own link: "Invented by Donald Shell in 1959, the shell sort is the most efficient of the O(n2) class of sorting algorithms. Of course, the shell sort is also the most complex of the O(n2) algorithms."

Which part of "shell sort is the most efficient of the O(n2) class of sorting algorithms" do you not understand?

Of course, why speed up an O(n2) sort - why not try to speed up an O(n log n) sort like quicksort? try and figure out the best way to choose the pivot point!

Re:Impressive

[pirap]

You should not look at genetic algorithms, but perhaps upon a newer "family" known as PSO (Particle Swarm Optimization). It's obviously very similar to GAs but takes care of cooperation as part of the development of solutions. This is the "weak" point of GAs as they only work through "battling" other solutions.

Swarms are a concept which was "invited" in 1995 I believe. Read some articles about it.

Re:Nice and all

[Anonymous Brave Guy]

It's quicksort n log(n) and shellsort n^2?

It depends on what you're measuring.

While Quicksort is O(nlogn) in typical use, its worst case performance is O(n), although most serious implementations would use a variation such as Introsort to limit the worst case behaviour.

Mergesort is O(nlogn) in all cases. However, the constant factor is usually significantly greater than Quicksort, making the latter preferable for most uses.

Shell sort is significantly slower for most situations, though IIRC it's pretty good with data that's already almost sorted.