in reply to Funky sorting

for sorting on a small list, say 10 elements or so, wouldn't bubble sort have a lot smaller overhead than a quck sort?

I would run some tests, but I care more about typing less in my programs than a small speed improvement :)

Replies are listed 'Best First'.
Re: Re: Funky sorting
by cacharbe (Curate) on Nov 11, 2001 at 09:30 UTC
    As a general response to this question, here's the time reference table for the different sorts:

    Sort Worst Case Average Case
    Selection Sort N2 N2
    Bubble Sort N2 N2
    Insertion Sort N2 N2
    Mergesort N*Log2N N*Log2N
    Quicksort N2 N*Log2N
    Radix Sort N N
    Tree Sort N2 N*Log2N
    Heap Sort N*Log2N N*Log2N

    It really depends on how well the data is presorted.

    If it is sorted, bubble sort can be as efficient as O(N), but it is usually O(N2).

    The worst case for a quick sort is just the opposite. If the data is already sorted and the smallest item is chosen as the pivot, time can be O(N2), but for most data sets it's (NlogN).

    C-.

[reply]

In Section Seekers of Perl Wisdom