sort/search algorithms

[Det. Bart Lasiter]

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]

Is this endeavour part of a school project jmac, or an extremely nerdy bet ?

 

mtfbwya

[Ray Jones]

Quicksort is fastest, end of debate.

[Det. Bart Lasiter]

Is this endeavour part of a school project jmac, or an extremely nerdy bet ?

 

mtfbwya

no 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]

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]

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...