+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.li/Forum-C-C-Obj-C)
+--- Thread: Bubble Sort Algorithm (/Thread-Bubble-Sort-Algorithm)
Pages:
1
2
RE: Bubble Sort Algorithm - invisal - 03-18-2014
@Deque
Quote:Selection sort is not stable. Bubblesort is.
Bubblesort performs much better on nearly sorted data than selection sort. So you might prefer it if you know that your data will be nearly sorted.
Bubblesort can be easier implemented with e.g. linked lists as you just operate with your pointer on two consecutive nodes.
Selection Sort can easily implemented in Linked List and you can also
make it stable. Insertion Sort is as fast as Bubble Sort if not faster than
on a nearly sorted data, and averagely perform better on random
ordered data.
This is a direct quote from "Art of Computer Programming - (Vol 3) - Sorting and Searching"
Quote:In short, the bubble sort seems to have nothing to recommend it, except a
catchy name
Even Barack Obama know Bubble Sort is a bad.
@ArkPhaze
Quote:It's completely relevant. Generics aren't all the greatest thing either, so to limit a method and point out that it doesn't work in a generic scenario with templates is not the greatest standpoint
So writing a Swap function that could work with larger number of data type
has little or no benefit over a Swap function that works only with small number
of data type with no performance benefit?
RE: Bubble Sort Algorithm - Deque - 03-18-2014
(03-18-2014, 09:21 AM)invisal Wrote: Selection Sort can easily implemented in Linked List
Yes.
(03-18-2014, 09:21 AM)invisal Wrote: you can also make it stable
That needs a data structure that allows efficient insertion. If you do that on an array, your performance will get pretty bad. So you might not want that.
(03-18-2014, 09:21 AM)invisal Wrote: Insertion Sort is as fast as Bubble Sort if not faster than
on a nearly sorted data, and averagely perform better on random
ordered data.
I agree that Insertion Sort is better than Bubblesort in most cases, this is also true compared to Selection Sort. So you could ask as well why not prefer Insertion Sort over Selection Sort in any cases?
The answer is the same as with Bubblesort: Because there are circumstances where it is better. E.g. Insertion Sort needs more write operations than Selection Sort, so if writing is costly, you might prefer the latter.
The specialty of Bubblesort is that it only compares two consecutive elements. So what if you have a datastructure or any hardware restrictions that enables only fast access or swapping for two consecutive elements? Or you work with threaded applications and want to lock as small parts as possible (e.g. fine-grained synchronized linked list).
Or if you know you have to sort small arrays very often and most of the time this array only has two elements.
Furthermore I don't see the problem with presenting a well analysed and simple basic algorithm in forums. This is also some kind of history, it is basic knowledge and a good basis for further analysis by students in order to learn. E.g. it's an easy algorithm to start learning about time complexity.
People here probably post this algorithm, because it was one of the first they learned. And I am sure that they also got told that Bubblesort usually has a bad performance.
In most of the cases, however, when you need some sorting, the performance doesn't even matter.
Edit: If you have the time, compare the speed of Selection Sort and Bubble Sort for 20 elements here: http://www.sorting-algorithms.com/
To sum it up:
- Bubblesort is adaptive, Selection Sort is not (usually adaptivity is seen as better)
- Bubblesort is stable, Selection Sort is (usually) not (stability is always better)
- Bubblesort only accesses and swaps two consecutive elements, Selection Sort doesn't (depends on the circumstances which is better)
- Both are easy to implement
- Both have a bad performance with a large number of elements
RE: Bubble Sort Algorithm - invisal - 03-18-2014
@Deque, the thing is it is okay to learn BubbleSort, but don't fall in love with it
just because it is simple with a catchy name?
RE: Bubble Sort Algorithm - Deque - 03-18-2014
(03-18-2014, 09:26 PM)invisal Wrote: @Deque, the thing is it is okay to learn BubbleSort, but don't fall in love with it
just because it is simple with a catchy name?
I don't know anyone who fell in love with it. :Crazy:
But yeah, I agree.
RE: Bubble Sort Algorithm - ArkPhaze - 03-19-2014
(03-18-2014, 09:21 AM)invisal Wrote: @Deque
Quote:Selection sort is not stable. Bubblesort is.
Bubblesort performs much better on nearly sorted data than selection sort. So you might prefer it if you know that your data will be nearly sorted.
Bubblesort can be easier implemented with e.g. linked lists as you just operate with your pointer on two consecutive nodes.
Selection Sort can easily implemented in Linked List and you can also
make it stable. Insertion Sort is as fast as Bubble Sort if not faster than
on a nearly sorted data, and averagely perform better on random
ordered data.
This is a direct quote from "Art of Computer Programming - (Vol 3) - Sorting and Searching"
Quote:In short, the bubble sort seems to have nothing to recommend it, except a
catchy name
Even Barack Obama know Bubble Sort is a bad.
@ArkPhaze
Quote:It's completely relevant. Generics aren't all the greatest thing either, so to limit a method and point out that it doesn't work in a generic scenario with templates is not the greatest standpoint
So writing a Swap function that could work with larger number of data type
has little or no benefit over a Swap function that works only with small number
of data type with no performance benefit?
I don't know where you're creating these assumptions based on what I'm saying, but I never compared benefits and nor was I recommending one over the other, I simply said that there's no need to completely disregard something just because a better alternative may exist, there's usually an odd case where the less common choice is both preferred and necessary, and I pointed out the cases stated in the same link you provided for your argument as to why XOR swapping is or can be still useful... The same argument Deque brought up with Bubble sort comparatively. Various sorting algorithms do NOT have a singular performance measurement all the time, it does depend on what kind of data you're sorting and what state that data is in, which is typically the reason why you see combinations of sorting algorithms in some libraries. Perhaps not in this particular case, depending on a few factors of course, which are outlined by your first post, but that's all I'm guilty of. As per my previous comment about overloading, if you don't understand the analogy I was trying to make, that doesn't make it void of relevance to the original discussion, just because you see it as something of a different topic.
RE: Bubble Sort Algorithm - invisal - 03-19-2014
@ArkPhaze
Quote:I don't know where you're creating these assumptions based on what I'm saying,
but I never compared benefits and nor was I recommending one over the other
I asked you why do you prefer XOR swap, and you said it is clean, easy, and fast.
I see it as an indirect recommendation. When you prefer something over something
and say it is clean, easy, and fast. It usually mean it is cleaner, easier, and
faster.
Quote:I simply said that there's no need to completely disregard something just because a
better alternative may exist
I don't discard the existence and useful of XOR swap in some rare cases (very rare cases).
But you make a minor change to @TheUninvited code from temporary variable swap to
XOR swap, which I believe might mislead him to think XOR swap is better.
Quote:The same argument Deque brought up with Bubble sort comparatively.
Various sorting algorithms do NOT have a singular performance measurement
all the time, it does depend on what kind of data you're sorting and what
state that data is in
I don't disagree, but what Bubble Sort can do and can do best can be done
with other algorithm with a better averagely running time which make the
existence of Bubble Sort almost pointless.
Quote:The specialty of Bubblesort is that it only compares two consecutive elements.
So what if you have a datastructure or any hardware restrictions that enables
only fast access or swapping for two consecutive elements
Deque made a valid point that BubbleSort might shine to certain hardware restriction,
but the it is hard to find such a restriction on any modern hardware.
To sum it up,
- I don't disagree that you should learn BubbleSort or XOR swap
- But, I wouldn't recommend it
RE: Bubble Sort Algorithm - Inori - 03-30-2014
This thread turned my brain into a bowl of jello. good job everyone.