insertion sort vs bubble sort vs quicksort algorithm

Question

I am working on a research in the class I tested bubble sort and insertion sort and quick sort , i did the test on random numbers. The results shows that insertion sort is more quicker than bubble sort and quick sort is the most slower one.

So I have the below ranking in terms of time

insertion sort (the fastest)
bubble sort (second score)
quick sort (the slowest)

Taking into account that insertion and bubble sort have a complexity of O(n2) while quick sort O(n log n) and O (n log n) should be faster !!!

Could anybody share with me explanations?

Thanks

(NSMutableArray *)quickSort:(NSMutableArray *)a
{
    // Log the contents of the incoming array
    NSLog(@"%@", a);

    // Create two temporary storage lists
    NSMutableArray *listOne = [[[NSMutableArray alloc]
    initWithCapacity:[a count]] autorelease];
    NSMutableArray *listTwo = [[[NSMutableArray alloc]
    initWithCapacity:[a count]] autorelease];
    int pivot = 4;

    // Divide the incoming array at the pivot
    for (int i = 0; i < [a count]; i++)
    {
        if ([[a objectAtIndex:i] intValue] < pivot)
        {
           [listOne addObject:[a objectAtIndex:i]];
        }
        else if ([[a objectAtIndex:i] intValue] > pivot)
        {
           [listTwo addObject:[a objectAtIndex:i]];
        }
    }

    // Sort each of the lesser and greater lists using a bubble sort
    listOne = [self bubbleSort:listOne];
    listTwo = [self bubbleSort:listTwo];

    // Merge pivot onto lesser list
    listOne addObject:[[NSNumber alloc] initWithInt:pivot]];

    // Merge greater list onto lesser list
    for (int i = 0; i < [listTwo count]; i++)
    {
        [listOne addObject:[listTwo objectAtIndex:i]];
    }

    // Log the contents of the outgoing array
    NSLog(@"%@", listOne);

    // Return array
    return listOne;
}

How big is your data you are testing on and are you using the same unsorted data for each algorithm? — alex, Oct 16 '12 at 11:08
You either implemented quicksort wrong or you did the test wrong. Post your implementations and your test. — IVlad, Oct 16 '12 at 11:08
With a small number of elements, insertion sort is the faster than quicksort because while O(N^2) it has a really small constant factor. For better result, try sorting arrays with lots of elements (e.g 1000, 1000000, 1000000000 elements). I don't know how bubblesort behaves for small arrays but I guess for only a few elements it may beat quicksort. — helpermethod, Oct 16 '12 at 11:08
i tested over several tranches 5000 , 10000 , 15000 and 20000 the same arrays are applied for all of the three algorthims — Oracle Oracle, Oct 16 '12 at 11:09
First question that springs to mind is: How much data did you use? Have you printed out the starting list and seen that the numbers are actually random? What is your algorithm in quicksort for finding the splitting value? — martiert, Oct 16 '12 at 11:10
what your implementations of Quicksort? Are you partitioning around first element or around the mean? — Roman Pekar, Oct 16 '12 at 11:11
Your so-called "quicksort" isn't a quicksort. It's one partition followed by two bubble sorts plus a merge. — Steve Jessop, Oct 16 '12 at 11:28

score 3 · Answer 1 · answered Oct 16 '12 at 11:08

3

well, quicksort depends on input heavily. You need to SHUFFLE input before make quicksort. If your input is sorted, quicksort can have complexity of O(n2)

insertion sort also can be faster for small arrays

answered Oct 16 '12 at 11:08

Roman Pekar

107,110
28
195
197

i tested over several tranches 5000 , 10000 , 15000 and 20000 the same arrays are applied for all of the three algorthims is that enough to make insertion sort faster – Oracle Oracle Oct 16 '12 at 11:12
Quicksort make partitioning around one element. To have O(n log n) you need to be sure that this element is close to mean. One way to do it is to shuffle input before quicksorting. – Roman Pekar Oct 16 '12 at 11:13
for example, if you have input sorted and make partitioning around first element, than you'll have 1/2 o(N2) complexity – Roman Pekar Oct 16 '12 at 11:14
if i hard codeded the pivot point as a middle number would that be OK ? i.e for 5000 is it fine to make the pivot 2500 ?? – Oracle Oracle Oct 16 '12 at 11:16
imho you need either shuffle whole array before applying quicksort or get median of array you want to partition. You can search in wikipedia about median of 3 method. I'd reccomend to do shuffle. – Roman Pekar Oct 16 '12 at 11:18
1

@OracleOracle For any strategy picking a fixed element as pivot, there are inputs that make quicksort O(n²). If the array is truly random (or a good approximation to that), those cases are very unlikely. If you choose the pivot per median-of-medians, it is guaranteed to be O(n*log n), but the constant factor is relatively large, on average it will be slower than a simpler pivot-choosing strategy. Median of 3 makes O(n²) behaviour very unlikely, so it's a good strategy. Choosing the middle element of the array is better than the first, but has more bad cases than median of 3. – Daniel Fischer Oct 16 '12 at 11:30
@Roman: is it better to shuffle the array than it is to select pivots randomly at each step? – Steve Jessop Oct 16 '12 at 14:05
you don't need to shuffle at each step, you need to shuffle just once, before first partitioning. – Roman Pekar Oct 16 '12 at 14:09
@Roman: that's not what I asked. I don't suggest shuffling at each step. I suggest at each step selecting the pivot randomly from the elements to be partitioned. I ask whether you feel this is worse than shuffling the whole array once at the start, since you say "imho you need either shuffle whole array ...". – Steve Jessop Oct 16 '12 at 14:41
@SteveJessop It doesn't really matter, they perform the same number of operations. The code is probably cleaner however, if there are no calls to rand() in the middle of the algorithm. – Dave Oct 16 '12 at 15:04

score 2 · Answer 2 · answered Oct 16 '12 at 11:12

2

It depends on the array size. On small arrays simple algorithms (such as insertion sort) will do pretty well, there is no need for better algorithms.

However, when n is large (say n=10000000), quicksort will generally do much much better than insertion (or bubble) sort.

answered Oct 16 '12 at 11:12

Dave

690
4
7
16

but i do not understnad why insertion sort is betther in samll number can you kindly futhur explain ? – Oracle Oracle Oct 16 '12 at 11:17
2

@OracleOracle: here's an example of something that's `O(n^2)`: `for (int = 0; i < n*n; ++i) printf("%d\n", i);`. Here's an example of something that's `O(n log n)`: `for (int i = 0; i < n * log(n); ++i) { for (int j = 0; j < 1000*1000; ++j) printf("%d\n", i); }`. Obviously, for small `n` the first code is faster than the second. So why shouldn't insertion sort be faster than quicksort for small `n` just because it has worse complexity? The reason it actually is faster is that quicksort has particular overhead (tracking partitions) that insertion sort doesn't. – Steve Jessop Oct 16 '12 at 11:22
Thanks again, what about bubble sort and insertion sort – Oracle Oracle Oct 16 '12 at 11:46
@OracleOracle: I think insertion sort tends to need fewer comparisons than bubble sort, maybe fewer copies as well. Certainly the worst case of bubble sort (where the smallest element starts at the end) requires `n*(n-1)` comparisons, whereas insertion sort requires at worst half that. With random data it is likely that there are smallish elements close to the end. They are called "turtles" and they hurt a simple bubble sort badly. – Steve Jessop Oct 16 '12 at 14:01

score 2 · Accepted Answer · edited May 23 '17 at 12:28

O(nlogn) is "faster" then O(n^2), but let's recall what the big O notation mean.

It means that if algorithm A has complexity of O(nlogn), for some constants N_1, and c1, for each n>N - the algorithm is "faster" then c1*n*log(n). If algorithm B has O(n^2), there are some constants N_2,c2 such that the algorithm is "faster" then c2 * n^2 * log(n) for n > N_2.

However - what happens before this N? and what is this constant C? We do not know. Algorithm B could still be "faster" then algorithm A for small inputs, but for large inputs - indeed, A will be faster (the asymptotic bound is better).

For example, let's take the case where algorithm A runs in T_1(n) = 10* nlog(n) ops, while algorithm B runs in T_2(n) = n^2. for n=3 - we get that T_1(3) = 10*3*2 = 60 (we tool the ceil for log(n)), and T_2(3) = 9 - thus algorithm B, though O(n^2) is faster then A for this input.

Regarding quick sort and insertion sort:
Quick sort is usually extremely fast, and decays into quadric time in very rare cases (the probability of this happening is slim if we chose a random element as a pivot).

However, the constant behind the big O notation in quicksort is greater then insertion sort. Thus - a possible optimization is: use quicksort until you get to a certain threshold (say 30 elements), and then sort this subarray with insertion sort rather then quicksort. This post discusses this optimization.

Bubble sort is (empirically) terrible for random arrays, but could be good if the array is almost sorted and the "out of place" elements are in its beginning.

insertion sort vs bubble sort vs quicksort algorithm

3 Answers3

Linked