Author |
Topic: Bubble Sort Vs. Quick Sort (Read 1607 times) |
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Bubble Sort Vs. Quick Sort
« on: Jan 27th, 2010, 8:14pm » |
Quote 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:
Posts: 250
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #1 on: Jan 27th, 2010, 11:16pm » |
Quote 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:
Posts: 7526
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #2 on: Jan 28th, 2010, 9:55am » |
Quote 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:
Posts: 55
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #3 on: Jan 28th, 2010, 6:46pm » |
Quote 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:
Posts: 250
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #4 on: Jan 28th, 2010, 8:54pm » |
Quote 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 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:
Posts: 7526
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #6 on: Jan 29th, 2010, 1:16am » |
Quote 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:
Posts: 60
|
|
Re: Bubble Sort Vs. Quick Sort
« Reply #7 on: Jan 29th, 2010, 8:07am » |
Quote 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 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 |
|
|
|
|