wu :: forums
« wu :: forums - Bubble Sort Vs. Quick Sort »

Welcome, Guest. Please Login or Register.
Oct 17th, 2021, 3:21pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, towr, ThudnBlunder, Eigenray, william wu, SMQ, Grimbal)
   Bubble Sort Vs. Quick Sort
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Bubble Sort Vs. Quick Sort  (Read 1477 times)
jpk2009
Junior Member
**





   


Gender: female
Posts: 60
Bubble Sort Vs. Quick Sort  
« on: Jan 27th, 2010, 8:14pm »
Quote Quote Modify Modify

I would like to ask if there are any specific instances where bubble sort would be a better sorting method over quick sort?  
 
Thanks.
IP Logged
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: Bubble Sort Vs. Quick Sort  
« Reply #1 on: Jan 27th, 2010, 11:16pm »
Quote Quote Modify Modify

on Jan 27th, 2010, 8:14pm, 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.
IP Logged

The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7517
Re: Bubble Sort Vs. Quick Sort  
« Reply #2 on: Jan 28th, 2010, 9:55am »
Quote Quote Modify Modify

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).
IP Logged
bmudiam
Junior Member
**





   


Gender: male
Posts: 55
Re: Bubble Sort Vs. Quick Sort  
« Reply #3 on: Jan 28th, 2010, 6:46pm »
Quote Quote Modify Modify

on Jan 28th, 2010, 9:55am, 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.
IP Logged

“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: Bubble Sort Vs. Quick Sort  
« Reply #4 on: Jan 28th, 2010, 8:54pm »
Quote Quote Modify Modify

on Jan 28th, 2010, 6:46pm, 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.
IP Logged

The only thing we have to fear is fear itself!
mistaken_id
Junior Member
**





   


Posts: 132
Re: Bubble Sort Vs. Quick Sort  
« Reply #5 on: Jan 28th, 2010, 9:05pm »
Quote Quote Modify Modify

on Jan 28th, 2010, 8:54pm, 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
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7517
Re: Bubble Sort Vs. Quick Sort  
« Reply #6 on: Jan 29th, 2010, 1:16am »
Quote Quote Modify Modify

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.
IP Logged
jpk2009
Junior Member
**





   


Gender: female
Posts: 60
Re: Bubble Sort Vs. Quick Sort  
« Reply #7 on: Jan 29th, 2010, 8:07am »
Quote Quote Modify Modify

Thanks all!
IP Logged
JohanC
Senior Riddler
****





   


Posts: 460
Re: Bubble Sort Vs. Quick Sort  
« Reply #8 on: Jan 30th, 2010, 2:12am »
Quote Quote Modify Modify

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
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board