Re: Whats the best language to learn...

Jean-Claude Arbaut wrote:
Juha Nieminen wrote:
cr88192 wrote:
(Besides, what's your fixation with this "coctail sort". Insertion
sort is the most efficient way of speeding up quicksort.)
actually, heapsort is the best way of speeding up quicksort, but it
is complicated.

No, it isn't. Sorting a partition of less than about 20 elements with
heapsort is a LOT slower than sorting it with insertion sort.

And ? What about 200 elements ? 2000 ? More ?

The question was about speeding up quicksort. What I meant with this
is the classical "stop partitioning partitions smaller than n, and
instead sort them with a fast O(n^2) algorithm".

For 20 elements a bubble sort will be perfect, btw.

No, it won't. Bubble sort is probably the worst possible choice to
sort such a small array.
Insertion sort is one of the best possible O(n^2) algorithm for that
situation.

Not convinced? Let's assume we have an array of 20 elements which is
otherwise already sorted, except that the last element is the smallest
one. How many operations will insertion sort perform?

First insertion sort will traverse the array from the beginning to the
end, each time making a comparison between pairs of elements. That makes
20-2=18 comparisons (not counting the last pair comparison, which is
counted next). Then it finds the smallest element and starts moving it
towards the beginning (by moving all the elements one step towards the
end). This requires 20-1=19 comparisons and 20+1=21 element assignments
(first we assign that last element to a temporary, after which we move
all elements one step towards the end, thus a total of 19 assignments,
and then we assign the temporary to the first element). Then the
algorithm ends, because it has reached the end of the array.

Thus a total of 37 comparisons and 21 assignments.

Now bubble sort: The first pass performs 20-1=19 comparisons and one
swap (ie. three assignments). The next pass performs 19-1=18 comparisons
and one swap. The next one 18-1=17 comparisons and one swap. And so on.
The total number of such passes will be 19, and thus the total number of
comparisons will be 19+18+17+...+1 = 190. The number of swaps will be
the same as the number of passes (because at each pass one swap is
performed), ie. 19. Because a swap consists of three assignments, that
makes a total of 57 assignments.

Thus bubble sort performs 190 comparisons and 57 assignments.

Compare that to the 37 comparisons and 21 assignments of insertion sort.

Bubble sort is "perfect"? Bull***.

As far as I can tell, there exist no cases where bubble sort would be
more efficient than insertion sort. At most it could be equally
efficient, and even those cases are extremely rare.

Why does this matter? Because when you are using this kind of O(n^2)
algorithm to speed up quicksort, you need to potentially run it
hundreds, if not thousands of times for all those small partitions, and
any additional comparison/assignment counts with respect to speed.
.

Quantcast