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?
The most SLOWEST sort algoritm ever?
A friend of mine once created a random sort.
Pseudocode/VBish implementation
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 = Resultend functionsub 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
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++]
[C++ FAQ Lite | ACCU | Boost | Learning C++]
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."
Just out of curiosity, why are you looking for the slowest possible algorithm?
------------------------------------------------------------
"To a computer, chaos is just another kind of order."
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?
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?
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?
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?
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?
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
Forever trusting who we are
And nothing else matters - Metallica
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:
[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...
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...
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement