• Advertisement

Archived

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

The most SLOWEST sort algoritm ever?

This topic is 5782 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
"most slowest"?

"slowest" already means "most slow". "most slowest" means what? "most most slow"? As opposed to...?

Share this post


Link to post
Share on other sites
"umm, that''s exactly what I''m doing in the first post in this thread."
I guess I should read the posts more carefully...

Forever trusting who we are
And nothing else matters
- Metallica

Share this post


Link to post
Share on other sites
Your approach is far too methodical. Although generating every possible array has the nice feature of taking up huge amounts of memory, it removes the possibility of searching the same array candidate twice, and thus garauntees that the algorithm will, at some point, actually finish.

A better approach would be to fill an array with completely random data, then check to see if that data a)matches the original and b)is sorted. This way, the chances of the algorithm ever finding a match decreases dramatically as the size of the array and datatype increases.

Share this post


Link to post
Share on other sites
quote:
Original post by cone3d
the algorithm can''t use randomness and must finish sometimes.



Damn. I''d even coded it for you.

Oh well, just in case anyone else needs a sorting algorithm:

  
void ImprobabilitySort(const int* const src, int* dst, int size)
{
// check data in destination to ensure data matches:

int* indexLookup = new int[size];

for(int i = 0;i<size;i++)
{
int data = src[i]; // current element we are looking for

bool found = false;
for(int j = 0;j<size;j++)
{
// look for the first occurence of data in the dst array

if(dst[j] == data)
{
// check that we havent already found this match, by searching the index lookup table for j

bool jNotFound = true;
for(int k = 0;k<size;k++)
{
if(indexLookup[k] == j)
{
jNotFound = false;
}
}
if(jNotFound)
{
indexLookup[i] = j;
found = true;
}
}
}
if(!found)
{
goto hell;
}
}
// the arrays contain the same data. Is the dst array sorted though?

{ // this brace stops a compiler error caused by careless use of goto. Neat, huh?

for(int l = 1;l<size;l++)
{
if(dst[l] < dst[l-1])
{
// oh no - they are not sorted!!

goto hell;
}
}
}
return;

hell:
// oh no! the array is wrong. Must generate a new one.

for(int m = 0;m<size;m++)
{
dst[m] = rand(); // ideally you''d use a better randomizer, but I can''t be arsed to write one now.

}
ImprobabilitySort(src,dst,size);
delete[] indexLookup; // do this before you call ImprobabilitySort to minimize the chance of the program crashing before it finds a solution


}

(untested)

Share this post


Link to post
Share on other sites
If it can't do anythin random, why not trying something like a 'brute force' sorting algorithm like one would use for 'key cracking'. For example, if you are sorting the array {65535, 1, 9461}
you first try {0, 0, 0} and test if it is sorted. It is, so THEN (and only then) you check if it has all the same data as the original. It does not, so you go to {0, 0, 1}. Again, it passes the first test but not the second. You repeat that until the last number is the maximum number the data type can store, and increment the number before it and set it to 0, so after a long time you get {0, 1, 0}, then {0, 1, 1} etc all the way up to the array that is both sorted (which is checked first to make it more slow) and has all the data the original array had. You could probably find a lot of room to slow down the test for being sorted and being the same data also, but even if they were hand optimized assembly, this algo would take a LONG LONG LONG time on any array larger than only a few elements.

This algorithm uses no random number generator and DOES finish, assuming the computer doesnt turn to dust first.

[edited by - Extrarius on April 17, 2002 2:35:06 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Extrarius
If it can''t do anythin random, why not trying something like a ''brute force'' sorting algorithm like one would use for ''key cracking''. For example, if you are sorting the array {65535, 1, 9461}
you first try {0, 0, 0} and test if it is sorted. It is, so THEN (and only then) you check if it has all the same data as the original. It does not, so you go to {0, 0, 1}. Again, it passes the first test but not the second. You repeat that until the last number is the maximum number the data type can store, and increment the number before it and set it to 0, so after a long time you get {0, 1, 0}, then {0, 1, 1} etc all the way up to the array that is both sorted (which is checked first to make it more slow) and has all the data the original array had. You could probably find a lot of room to slow down the test for being sorted and being the same data also, but even if they were hand optimized assembly, this algo would take a LONG LONG LONG time on any array larger than only a few elements.

This algorithm uses no random number generator and DOES finish, assuming the computer doesnt turn to dust first.

[edited by - Extrarius on April 17, 2002 2:35:06 PM]



Sweet. Maybe we could have a mini-contest: Write the fastest sorting program that uses this algorithm (only implementaion differing)

Share this post


Link to post
Share on other sites
quote:
Original post by Extrarius
If it can''t do anythin random, why not trying something like a ''brute force'' sorting algorithm like one would use for ''key cracking''. For example, if you are sorting the array {65535, 1, 9461}
you first try {0, 0, 0} and test if it is sorted. It is, so THEN (and only then) you check if it has all the same data as the original. It does not, so you go to {0, 0, 1}. Again, it passes the first test but not the second. You repeat that until the last number is the maximum number the data type can store, and increment the number before it and set it to 0, so after a long time you get {0, 1, 0}, then {0, 1, 1} etc all the way up to the array that is both sorted (which is checked first to make it more slow) and has all the data the original array had. You could probably find a lot of room to slow down the test for being sorted and being the same data also, but even if they were hand optimized assembly, this algo would take a LONG LONG LONG time on any array larger than only a few elements.

This algorithm uses no random number generator and DOES finish, assuming the computer doesnt turn to dust first.

[edited by - Extrarius on April 17, 2002 2:35:06 PM]


that''s simply brilliant!!!
of course it should have string to int and int to string convertions in it as well...


---
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 DrPizza
"most slowest"?

"slowest" already means "most slow". "most slowest" means what? "most most slow"? As opposed to...?




isn''t the progression obvious? slow, slower, slowest, more slowest, most slowest, mostest slowest...

ewen

Share this post


Link to post
Share on other sites

  
#include <iostream.h>

void Show(unsigned long long array[], unsigned long long size)
{
cout << "array = {";
for(unsigned long long pos = 0ull; pos < size; pos += 1ull)
{
cout << array[pos];
if(pos != size-1)
cout << ", ";
}

cout << "};" << endl;
}

unsigned long long last_offset = 0ull;

void Resort(unsigned long long array[], unsigned long long size)
{
last_offset += 1ull;

for(unsigned long long pass = 0ull; pass <= last_offset%1000ull; pass += 1ull)
{
unsigned long long temp = array[0ull];

for(unsigned long long pos = 0ull; pos < size-1ull; pos += 1ull)
array[pos] = array[pos+1ull];

array[size-1] = temp;
}

unsigned long long temp;
temp = array[(unsigned long long)((sin((double)last_offset)+1.0)*(double)size/2.0)];
array[(unsigned long long)((sin((double)last_offset)+1.0)*(double)size/2.0)] = array[(unsigned long long)((cos((double)last_offset)+1.0)*(double)size/2.0)];
array[(unsigned long long)((cos((double)last_offset)+1.0)*(double)size/2.0)] = temp;

}

void Sort(unsigned long long array[], unsigned long long size)
{
unsigned long long okay;

if(!array || size < 2)
return;

do
{
okay = true;

Resort(array, size);
for(unsigned long long pos = 0ull; pos < size-1; pos += 1ull)
{
if(array[pos] > array[pos+1])
okay = false;
}
}
while(okay == false);
}

int main(void)
{
unsigned long long array_size;
cout << "Number of items: ";
cin >> array_size;

unsigned long long *array = new unsigned long long[array_size];

for(unsigned long long pos = 0ull; pos < array_size; ++pos)
{
cout << "Item " << pos+1 << ": ";
cin >> array[pos];
}

cout << endl << "Started with: ";
Show(array, array_size);

Sort(array, array_size);

cout << "Ended with: ";
Show(array, array_size);

delete array;

return 0;
}



It''s very slow, but I think it will find a solution eventually. You can modify it to store the numbers as strings if you want, I don''t have time.

Share this post


Link to post
Share on other sites
Of course you could just implement it in pure VB and let the compiler take care of the de-optimization.

(Don''t flame, I''ve just been irritated at VB for the last few weeks due to the many ''features'' present in the language. If anyone really wants to start an argument about it I''ll post a full list of reasons but until then I don''t want a headache)




Share this post


Link to post
Share on other sites
quote:
Original post by Extrarius
If it can''t do anythin random, why not trying something like a ''brute force'' sorting algorithm like one would use for ''key cracking''. For example, if you are sorting the array {65535, 1, 9461}
you first try {0, 0, 0} and test if it is sorted. It is, so THEN (and only then) you check if it has all the same data as the original. It does not, so you go to {0, 0, 1}. Again, it passes the first test but not the second. You repeat that until the last number is the maximum number the data type can store, and increment the number before it and set it to 0, so after a long time you get {0, 1, 0}, then {0, 1, 1} etc all the way up to the array that is both sorted (which is checked first to make it more slow) and has all the data the original array had. You could probably find a lot of room to slow down the test for being sorted and being the same data also, but even if they were hand optimized assembly, this algo would take a LONG LONG LONG time on any array larger than only a few elements.

This algorithm uses no random number generator and DOES finish, assuming the computer doesnt turn to dust first.

[edited by - Extrarius on April 17, 2002 2:35:06 PM]


HAHAHAHAHA!!! That''s great! It made me chuckle just reading it here at work!

Share this post


Link to post
Share on other sites
This is an interesting (in spite of it being useless) post I don''t think it gets much slower than the brute force sort cracking without adding any excessive steps just to slow it down, such as storing everything on the hard drive or a network or something.

Share this post


Link to post
Share on other sites
btw, generating data that is not the original data set IS using excessive steps to avoid doing the sort. quite silly really, generating every possible array, then comparing to see if its even your array let alone sorted. also for the brute force method, using the same element twice is also wrong and using excessive steps since you have to compare to the original to see if your even attempting to sort or just looking at random data that has NOTHING to do with your original data.

a true brute force method would be to sytematically rearrange the data without reusing elements because checking to see if the data you have is actually data and not random garbage is an excessive step. (and that is a runon sentence)

Share this post


Link to post
Share on other sites

  • Advertisement