#### Archived

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

# The most SLOWEST sort algoritm ever?

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

## 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 on other sites
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 = 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

##### 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 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 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 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 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 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 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 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?

• 40
• 15
• 10
• 23
• 19