wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Bubble Sort Vs. Quick Sort
        
(Message started by: jpk2009 on Jan 27^th, 2010, 8:14pm)

Title: Bubble Sort Vs. Quick Sort
Post by jpk2009 on Jan 27^th, 2010, 8:14pm

I would like to ask if there are any specific instances where bubble sort would be a better sorting method over quick sort?

Thanks.

Title: Re: Bubble Sort Vs. Quick Sort
Post by birbal on Jan 27^th, 2010, 11:16pm

on 01/27/10 at 20:14:46, jpk2009 wrote:

I would like to ask if there are any specific instances where bubble sort would be a better sorting method over quick sort?

Thanks.

there can be specific examples where you have to make less number of comparisons/swaps in bubble sort than in qsort.

Title: Re: Bubble Sort Vs. Quick Sort
Post by Grimbal on Jan 28^th, 2010, 9:55am

When the data is already sorted.

Bubble sort would see that the array is sorted in O(n). Quick sort would see that piecewise and recursively in O(n log n).

Title: Re: Bubble Sort Vs. Quick Sort
Post by bmudiam on Jan 28^th, 2010, 6:46pm

on 01/28/10 at 09:55:48, Grimbal wrote:

When the data is already sorted.

Bubble sort would see that the array is sorted in O(n). Quick sort would see that piecewise and recursively in O(n log n).

Using last element as the pivot, quick sort takes O(n^2) for already sorted list.

Title: Re: Bubble Sort Vs. Quick Sort
Post by birbal on Jan 28^th, 2010, 8:54pm

on 01/28/10 at 18:46:42, bmudiam wrote:

Using last element as the pivot, quick sort takes O(n^2) for already sorted list.

well its not customary to choose the last element as pivot. If you select a random pivot, you will end up with a O(n lg n) amortized time.

Title: Re: Bubble Sort Vs. Quick Sort
Post by mistaken_id on Jan 28^th, 2010, 9:05pm

on 01/28/10 at 20:54:57, birbal wrote:

well its not customary to choose the last element as pivot. If you select a random pivot, you will end up with a O(n lg n) amortized time.

I think it is O(nlgn) expected time and not amortized

Title: Re: Bubble Sort Vs. Quick Sort
Post by Grimbal on Jan 29^th, 2010, 1:16am

A good implementation of quicksort would pick a pivot near the middle of the array to protect against nearly-sorted data. Or it would sample elements from all over the array and use the median as a pivot. This would guarantee (or make very likely) that the pivot splits the array in roughly equal parts.

Title: Re: Bubble Sort Vs. Quick Sort
Post by jpk2009 on Jan 29^th, 2010, 8:07am

Thanks all!

Title: Re: Bubble Sort Vs. Quick Sort
Post by JohanC on Jan 30^th, 2010, 2:12am

Drawbacks of quicksort when compared to bubblesort (or its variations):
- quicksort isn't stable; it doesn't preserve the order of seemingly equivallent elements, so it isn't fit when sorting elements in multiple passes over different keys
- quicksort is recursive, needing free space on the stack; this makes it not fit when you're working on a limited system (e.g. mobile phone, hardware device, ...) and you don't won't to worry about a horrible stack overflow
- quicksort's code is larger and more complicated; if you're working in assembler on limited hardware, you could prefer a short sure code over a faster one