PDA

View Full Version : sort/search algorithms


Det. Bart Lasiter
08-06-2008, 06:28 AM
While there is much debate over which method is the fastest, I've noticed that there isn't much debate or even competition to create the worst possible algorithm to search through or sort data. To this end, I decided to create this thread to see just how long searching or sorting data can take.

Anyway,

int randomfind(int tofind, int[] pants) {
srand(time(NULL));
int i = rand();
if(pants[i] == tofind) { return pants[i]; }
else { randomfind(tofind, pants); }
}

I think it's important to note that this function does not keep track of which elements it has already checked, does no bounds checking, and calls itself without narrowing its search at all.

Astrotoy7
08-07-2008, 11:05 AM
Is this endeavour part of a school project jmac, or an extremely nerdy bet ? :p

mtfbwya

Ray Jones
08-08-2008, 04:43 PM
Quicksort is fastest, end of debate.

Det. Bart Lasiter
08-09-2008, 11:29 PM
Is this endeavour part of a school project jmac, or an extremely nerdy bet ? :p

mtfbwyano to both, i just was up for too long and came up with it when i saw a thread on sa

Quicksort is fastest, end of debate.that's not the question and it's not the fastest 100% of the time >:|

tk102
08-10-2008, 12:33 AM
Here's one for Perl
sub luckysort {
my @arr_to_sort = @_;
#####
# lets put these in random order and see if we got lucky
#####
my $num_of_elements = scalar @arr_to_sort;
my %element_order;
my $random_index;
my $ix = 0;
my $out_of_order=1;
my %reversed_hash;
my @resulting_array;
my $number_of_iterations;
while ($out_of_order) {
$number_of_iterations++;
%element_order=();
$ix=0;
while ($ix < $num_of_elements) {
$random_index = int(rand($num_of_elements));
if (! exists $element_order{$random_index}) {
$element_order{$random_index}=++$ix;
}
}
%reversed_hash = reverse %element_order;
#####
#okay we have a random order, but is it sorted?
#####
$out_of_order=0;
my $previous_element=-1;
@resulting_array=();
for ($ix=0; $ix < $num_of_elements; $ix++) {
$this_element = $arr_to_sort[$reversed_hash{$ix+1}];
if ($this_element<$previous_element) {
$out_of_order = 1; # :-(
}
else {
$previous_element=$this_element;
push @resulting_array,$this_element;
}
}
}
print "took $number_of_iterations iterations\n";
return @resulting_array;
}


The average number of iterations required will be n!/2

Ray Jones
08-10-2008, 05:25 PM
Sorry jay, I just wanted to rule out quicksort that way. I'm on using my mobile again (and it won't let me browse to rd2 ;_; ) so I'm not gonna post code.


However, this is my sort algorithm:

Go through each element of an array and if it's more than the next one switch it with the last element if less with the first. Repeat until no elements were switched.

Will do nothing on an already sortet list, and should suffer some special cases, but I did not want to use random numbers etc. I hope this is even working...