Back to General and Gameplay Programming

The most SLOWEST sort algoritm ever?

cone3d · 2002-04-24T01:07:56

What''s the MOST SLOWEST sort algoritm ever? The algorithm CAN''T have built-in slow-down factors, it MUST do something that that leads it to the goal every step of the way. The algorithn I have at the moment looks sorta like this (pseudocode): int array[COUNT]; 1) generate all possible different variations of array, using a very unoptimal method (suppose the array is {1,2}, the method would create these arrays: {1,1}, {1,2}, {2,1}, {2,2} ) 2) when each variation is generated, loop through the array and check whether it contains all the elements in the original array, preferrably using recursion. 3.1) If it doesn''t go on to the next variation 3.2) If it does, loop through all the elements in the array, checking whether the previous one is smaller than the current one. If not, then check the next variation. Any suggestions on how to slow it down even more? ---cone3dhttp://cone3d.gamedev.netMy software never has any bugs - it just generates random featureshello?

General and Gameplay Programming Programming

Started by cone3d April 17, 2002 11:15 AM

67 comments, last by cone3d 21 years, 12 months ago

Beer Hunter

712

April 22, 2002 03:15 AM

quote:Original post by DrPizza
Place the pasta on a table, thin ends down. Then pick the tallest piece of pasta (constant time). Continue picking the tallest piece of pasta until you have them all in order (linear time).

Hmmm. It is indeed similar to the selection sort.

I don''t think it''s a fair assumption that choosing the longest piece of pasta is O(1); what if you have a 100-km long line of strands?

quote:Original post by benjamin bunny
I didn''t know a radix sort could be that flexible. Still, it eats a huge amount of memory.

Compared to other sorting algorithms, it does use a lot of memory, but I don''t think it''s "huge".

For sorting arrays, the implementation I use allocates an equally-sized array, plus 256 ints.

For linked lists, I think it requires 512 pointers and nothing more.

quote:Original post by benjamin bunny
My method (superSort) combines that with a bubble sort to improve the speed.

Look through these for the "fast quicksort". Same idea, but it uses the insertion sort instead of the bubblesort.

DrPizza

160

April 22, 2002 08:28 AM

quote:
I don''t think it''s a fair assumption that choosing the longest piece of pasta is O(1); what if you have a 100-km long line of strands?

Picking the longest is still independent of the number of pieces of spaghetti. You get a plate or similar and rest it on top of the pieces of spaghetti; the piece it touches is the longest.

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

davidsporn

126

April 22, 2002 08:53 AM

Hi,

Why not use a genetic algorithm to find the lowest or the heighest element, with very restricted population ?

I love the distributed computation methods.... if all connection are RTC, it''s better.

----
David Sporn AKA Sporniket

----David Sporn AKA SporniketThe blog of the Sporniket(in French) | Sporniket-Studio.com, my gallery of poster (via zazzle.com) | Sanctuaire Tokugawa, free Japanese lesson (in French)

Sand_Hawk

108

April 22, 2002 09:11 AM

Why not converting all the numbers to binary before checking if one is higher then the other? You take 2 numbers, convert them to binary, check, convert back to decimal and write them to the array. It sures slows down...

Sand Hawk

----------------(Inspired by Pouya)

benjamin bunny

838

April 22, 2002 09:32 AM

um, they''ll be in binary anyway.

____________________________________________________________
www.elf-stone.com

____________________________________________________________www.elf-stone.com | Automated GL Extension Loading: GLee 5.00 for Win32 and Linux

Anonymous

April 22, 2002 07:46 PM

Sorry to dissapoint you guys, but Radix Sort is, and always has been, O(n*ln(n)). Here''s my proof:

Let''s assume that you have k buckets. Every pass, you''ll go through the whole list/array/whatever, and place it in one of the k buckets. That''s O(n) operation. So the question is, how many passes will you need to sort? Well, if you have k buckets, you''ll divide the set in k every pass. Thus, the number of passes is log(n) in base k (just try it in your head if you don''t beleive me).

But since O(log(n,k)) == O(ln(n)), we have O(n * ln(n)) for the radix sort.

Now I do admit, the radix sort has a very low coefficient, making it very attractive in some circumstances.

Beer Hunter

712

April 22, 2002 09:05 PM

quote:Original post by DrPizza
Picking the longest is still independent of the number of pieces of spaghetti. You get a plate or similar and rest it on top of the pieces of spaghetti; the piece it touches is the longest.

Hence the

I put after the question. I didn''t really mean it...

quote:Original post by Anonymous Poster
Well, if you have k buckets, you''ll divide the set in k every pass. Thus, the number of passes is log(n) in base k

Your argument makes no sense. The number of passes depends only on the length of the data element being used to sort and the radix size. For example, to sort a 32-bit integer array with an 8-bit radix requires four passes. There will only be four passes whether you''re sorting 10 or 1,000,000,000 integers.

Beer Hunter

712

April 23, 2002 07:00 AM

Here''s an idea...

I''ve been reading up on the "binary tree sort". It works by creating a binary tree, sending all elements into the tree, then reading them out in the proper order.

In the tree, any element to the left of x is less than x, and any element to the right of x is greater than x.

It''s clear that the worst case is O(n2). But I thought of something: it''s possible to rotate a binary tree left or right in O(1) time. By keeping the binary tree balanced, O(log n) insertion time is guaranteed.

This appears to ensure O(n log n) time for the binary tree sort. I''ll try implementing it tomorrow.

DrPizza

160

April 23, 2002 07:47 AM

quote:Original post by Anonymous Poster
Sorry to dissapoint you guys, but Radix Sort is, and always has been, O(n*ln(n)). Here''s my proof:
Let''s assume that you have k buckets. Every pass, you''ll go through the whole list/array/whatever, and place it in one of the k buckets. That''s O(n) operation. So the question is, how many passes will you need to sort? Well, if you have k buckets, you''ll divide the set in k every pass.

No, you won''t. This is not how radix sort works.

It doesn''t divide the set, it works on each element individually. It divides each *element* into k digits of base b, not the set.

quote:Thus, the number of passes is log(n) in base k (just try it in your head if you don''t beleive me).

Radix sorting is performed on a set where each number is in the range [0, bk), where k is some constant. Each element to be sorted is a k digit base b number.

k is independent of n. The number of passes through the set is a function of k. You will need one pass through the set for each digit.

If k were allowed to vary with n, then it would degenerate to O(n logn), but it doesn''t.

quote:Now I do admit, the radix sort has a very low coefficient, making it very attractive in some circumstances.

The radix sort has linear complexity, not logarithmic, which it achieves through not being a comparison sort.

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

The most SLOWEST sort algoritm ever?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

The most SLOWEST sort algoritm ever?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines