Pathologically Eclectic Rubbish Lister | |
PerlMonks |
Re: My best attempt at sorting. Kindly suggest improvements/modifications.by Laurent_R (Canon) |
on Jan 30, 2018 at 00:54 UTC ( [id://1208089]=note: print w/replies, xml ) | Need Help?? |
This is inefficient for a number of reasons.
To start with, suppose you want to sort only 3 numbers, all of them fairly large, say all positive, with 9 digits, and pretty close together. For example: 999,999,998, 999,999,997 and 999,999,999. None of these numbers will be smaller than 0, so that $smallest_so_far will be 0, although 0 is not one of your numbers. This means that your big list will contain all numbers between 0 and 999,999,999, so almost a billion numbers, although if you had used a correct method to find the smallest number so far, it would contain only three numbers. It depends of course on your hardware, but it is likely that Perl might not be able to create such a large array. And, even if it can, it will take ages to iterate over that huge array, and this is of course not necessary with just three numbers so close together. The same argument goes the other way around for $biggest_so_far if all numbers are hugely negative. The correction is that, at the very least, you should initialize $biggest_so_far and $smallest_so_far with a number belonging to the list. Correcting this error will still not save your day. Your algorithm will be very inefficient if you try to sort just two numbers that are very far apart, say 999,999,999 and -999,999,999. You would build an even larger list (almost two billion candidates), although you really need to sort just two numbers. For such a dataset, even bogosort (see https://en.wikipedia.org/wiki/Bogosort) is extremely likely to be more efficient. I could go on with other inefficiencies for quite a while. Computer science has spent a huge number of man-years studying sorting algorithms. It is extremely unlikely that you'll come up with something better on your first try (of course, if you do, you might end up with a Turing Award, but, again, this is extremely unlikely). So I would suggest that you take the time to study the known sorting algorithms (see, for example, https://en.wikipedia.org/wiki/Sorting_algorithm for a start, you might want to look at Robert Sedgewick's writings if you want to go deeper into the matter). Just for fun, this is a simple Perl implementation of quicksort, an algorithm invented by Tony Hoare in 1959: For data which is already almost sorted, this implementation will be somewhat inefficient (merge sort is better in that case); for random data, it is one of the best known algorithms. A couple of small changes will make it efficient in all cases.
In Section
Seekers of Perl Wisdom
|
|