Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

cone3d

The most SLOWEST sort algoritm ever?

This topic is 5963 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?
---
cone3d
http://cone3d.gamedev.net
My software never has any bugs - it just generates random featureshello?

Share this post


Link to post
Share on other sites
Advertisement
A friend of mine once created a random sort.

Pseudocode/VBish implementation

function Sorted(A array of Integer) Boolean
dim I as Integer
dim Result as Boolean
Result = True
for I= Low(A) to High(A)-1
if A(I)>A(I+1) then Result=False
next I
Sorted = Result
end function

sub DoSort(A array of Integer)
dim Index1,Index2 as Integer
dim Temp as Integer
repeat
Index1=Random(Low(A),High(A))
Index2=Random(Low(A),High(A))
Temp=A(Index1)
A(Index1)=A(Index2)
A(Index2)=Temp
until Sorted(A)
end sub

Share this post


Link to post
Share on other sites
Premature de-optimisation is the root of all evil! Get the functionality right first and then, if it''s too fast, you need to profile to find the fastest execution paths. Once you have found which parts are doing their job efficiently, you can strategically select an inappropriate algorithm for the job. You could try a selection of algorithms for profiling against your sample input data, to help find which is the slowest. The slowness will depend on the organisation of the data you expect your application to handle.


[C++ FAQ Lite | ACCU | Boost | Learning C++]

Share this post


Link to post
Share on other sites
Bubble Sort; though it isn''t the slowest algorithm that get''s an array sorted, it''s kind of the naiv implementation of a sorting algorithm. On an array of 50 elements it takes Bubblesort 1225 compare and round about 600 (+-10-20% depending on inputdata) exchange operations... The algorithm cone3d mentioned will probably be slower but it will use up a huge amount of memory in comparison *grin*.

Just out of curiosity, why are you looking for the slowest possible algorithm?

------------------------------------------------------------
"To a computer, chaos is just another kind of order."

Share this post


Link to post
Share on other sites
Your right. My implementation has way to many optimizations.
Change the array from integer to strings, then insert StrToInt and IntToStr functions to convert back and forth every time a read or write occurs. For further de-optimization place the record in a dBase database on a network/internet server, and request each record individually.

I''m sure there are more optimizations I''ve made by accident. Anyone see them?

Share this post


Link to post
Share on other sites
nah, that algorithm won''t take up much more memory, it just needs 2 arrays: the original and one to store temporary data.

Anyway, can anyone improve the algorithm I presented to make it even slower? And NO randomness!

Actually, I don''t really need the algorithm for anything. Just for fun


---
cone3d
http://cone3d.gamedev.net
My software never has any bugs - it just generates random featureshello?

Share this post


Link to post
Share on other sites
quote:
Original post by Michalson
Your right. My implementation has way to many optimizations.
Change the array from integer to strings, then insert StrToInt and IntToStr functions to convert back and forth every time a read or write occurs. For further de-optimization place the record in a dBase database on a network/internet server, and request each record individually.

I''m sure there are more optimizations I''ve made by accident. Anyone see them?


those are good ideas!!! any more?


---
cone3d
http://cone3d.gamedev.net
My software never has any bugs - it just generates random featureshello?

Share this post


Link to post
Share on other sites
Take the array. Try out each combination, until you get the sorted one. If the array is big enough, this universe is doomed long before you finish searching

Forever trusting who we are
And nothing else matters
- Metallica

Share this post


Link to post
Share on other sites
Yes, you used a compiled language (Pascal) instead of an interpreted one (GWBasic ?).

Alternatively you could use this code, written in INTERCAL by Louis Howell (see there:


  
DO WRITE IN .2
DO ,1 <- .2

PLEASE NOTE INITIAL SEQUENCE INPUT
DO .1 <- .2
DO (110) NEXT
(110) DO FORGET #1
DO WRITE IN ,1 SUB .1
DO (111) NEXT
(112) DO (2010) NEXT
DO FORGET #2
DO (110) NEXT
(111) DO (112) NEXT
DO FORGET #1

PLEASE NOTE CALLING SORT ROUTINE INDIRECTLY
DO .1 <- .2
DO (500) NEXT

PLEASE NOTE SORTED SEQUENCE OUTPUT
DO .1 <- .2
DO (210) NEXT
(210) DO FORGET #1
DO READ OUT ,1 SUB .1
DO (211) NEXT
(212) DO (2010) NEXT
DO FORGET #2
DO (210) NEXT
(211) DO (212) NEXT
DO FORGET #1

PLEASE GIVE UP

PLEASE NOTE COMPARE AND EXCHANGE ROUTINE
(500) PLEASE ABSTAIN FROM (502)
DO (3000) NEXT
DO (501) NEXT
(501) DO FORGET #1
(502) DO (3010) NEXT
PLEASE REINSTATE (502)
DO .3 <- ''?",1SUB.1"$,1SUB.2''~''#0$#65535''
DO .3 <- ''?"''& "''",1SUB.1"~.3''~''"?''?.3~.3''$#32768"~"#0$#65535"''" $
"
.3~.3"''~#1" $
#1''~#3
DO (503) NEXT
DO .3 <- ,1 SUB .1
DO ,1 SUB .1 <- ,1 SUB .2
DO ,1 SUB .2 <- .3
DO (501) NEXT
(504) PLEASE RESUME .3
(503) DO (504) NEXT
DO FORGET #1
DO (501) NEXT


PLEASE NOTE BUBBLE SORT ROUTINE
PLEASE NOTE THAT EXCHANGE ROUTINE SHOULD NOT CHANGE .1 OR .2
(3000) PLEASE STASH .1 + .2
DO .2 <- .1
DO (2000) NEXT
DO (3001) NEXT
(3001) DO FORGET #1
DO RESUME #1
(3011) DO (2010) NEXT
DO FORGET #1
DO (3001) NEXT
(3010) DO (3011) NEXT
DO (3012) NEXT
(3013) DO .1 <- .2
DO (2010) NEXT
DO FORGET #2
DO .2 <- .1
DO (3010) NEXT
DO RESUME #1
(3012) DO (3013) NEXT
PLEASE RETRIEVE .1 + .2
DO RESUME #4

(2010) PLEASE ABSTAIN FROM (2004)
(2000) PLEASE STASH .2
DO .2 <- #1
DO (2001) NEXT
(2001) DO FORGET #1
DO .1 <- ''?.1$.2''~''#0$#65535''
DO (2002) NEXT
DO .2 <- !2$#0''~''#32767$#1''
DO (2001) NEXT
(2003) PLEASE RESUME "?!1~.2''$#1"~#3
(2002) DO (2003) NEXT
PLEASE RETRIEVE .2
(2004) PLEASE RESUME #2
PLEASE DO REINSTATE (2004)
PLEASE RESUME ''?"!1~.1''~#1"$#2''~#6
[source]

Please note however that this code may have actually been optimized.


[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites
quote:
Original post by Gabriel Fleseriu
Take the array. Try out each combination, until you get the sorted one. If the array is big enough, this universe is doomed long before you finish searching

Forever trusting who we are
And nothing else matters
- Metallica



umm, that''s exactly what I''m doing in the first post in this thread.



---
cone3d
http://cone3d.gamedev.net
My software never has any bugs - it just generates random featureshello?

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!