Bubble Sort

[Mathhead200]

Why do people start with bubble sort? I personally see it as a convoluted sort compared to its relativity easy alternatives. Apart from that, it's considered one of the slowest sorts available (queue crappy sorting algorithms.)

I'm not just ranting by the way. A few years back I was working on a program and I needed to find a way to sort an array. I sat there, thought about it, and came up with something to the effect of

template <typename T>
void sort(T array[], int length) {
	for( int rPos = 1; rPos < length; rPos++ ) {
		T ele = array[rPos];
		for( int lPos = 0; lPos < rPos; lPos++ )
			if( ele < array[lPos] ) { //ascending order
				for( int i = rPos; i > lPos; i-- )
					array[i] = array[i - 1];
				array[lPos] = ele;
				break;
			}
	}
}
//I wrote it in Java originally, but it looked about like this (with out the use of templates/generics) 

It was written to mimic how I would sort a set of card (or something like that) in real life. I think that a student might be better off figuring out how to sort something in C++ mainly by himself. It's something that we already know how to do, so we are really just translating it into code.

[z05DSL3A]

Bubble sort has a very simple algorithm. I far as I have seen, it is used to give students the opportunity to implement an algorithm and then to discuss its shortcomings, leading to analysing and designing other algorithms. I have never seen it taught as a viable sorting method, just as a stepping stone to bigger and better things.

[Mathhead200]

Grey Wolf wrote:

Bubble sort has a very simple algorithm.

I disagree on this point. I find it very unintuitive compared to the other sorting algorithms. Just because something has fewer lines of code doesn't make it simpler in my opinion.

As for your other point, I feel your assuming that people are learning about sorting from a structured lesson plan. As you can see, at one point I knew how to implement the sort I wrote above, but had never learned or even seen a formal sorting algorithm before.

Gray Wolf wrote:

I have never seen it taught as a viable sorting method ...

That's kind of my point. Why bother when the alternatives are more intuitive?

[xander333]

I agree with mathhead here. I've not ever used a bubble sort in my life. I designed my own algorithms. When I tried to read up on searching algorithms a few months back, I always found Bubble Sort being marked as *the easiest*. It's counter-intuitive IMO.

[z05DSL3A]

I disagree on this point. I find it very unintuitive compared to the other sorting algorithms.

Simplicity and intuitiveness don't always go hand in hand.

I feel your assuming that people are learning about sorting from a structured lesson plan. As you can see, at one point I knew how to implement the sort I wrote above, but had never learned or even seen a formal sorting algorithm before.

Most of the time, yes. but also you said 'I think that a student might be better off figuring out how to sort something in C++ mainly by himself.' which also gets you a bent to talking about structured lesson plan. I'm not talking about specifically being taught it, quite often it it used when students are learning about arrays or liked lists as it is something handy to do.

Why bother when the alternatives are more intuitive?

As above, Simplicity and intuitiveness don't go hand in hand. It's a simple algorithm, simple to implement and doesn't have to be intuitive because you are given it.

If I asked you if a number was odd or even, what you would do intuitively to answer the question would likely turn into a complicated algorithm to implement in a program.

[moorecm]

Why do people start with bubble sort? I personally see it as a convoluted sort compared to its relativity easy alternatives. Apart from that, it's considered one of the slowest sorts available (queue crappy sorting algorithms.)

People start with it because it is the simplest to implement (great for academia). You disagree? Write a few more algorithms and post them. One of the slowest sorts for what? I suggest doing a bit more research. Try a bubble sort on a nearly sorted dataset, for example.

Additionally, it is also a nice algorithm to analyze Big O complexity. However, I'm not clear on why the bubble sort snippet above has three nested for loops. Bubble sorts are O(n²), or quadratic, which is only two nested loops...

[jsmith]

I think that if a newbie was to invent a sort by himself/herself knowing nothing of the sorts that are available, the selection sort would be the algorithm s/he comes up with first. I think it is relatively unlikely that s/he will spend enough time to re-invent any other sort algorithm, and there are plenty.

In considering all the sort algorithms available, when I was learning sort algorithms in college, bubble sort was perhaps the "simplest" to remember.

[Mathhead200]

moorecm wrote:

However, I'm not clear on why the bubble sort snippet above has three nested for loops.

Because that's not bubble sort. It's the sort I came up with (just about) before I know any formally taught ones. I think it's still O(n²) though. The inner-most loop is only to insert the element into the correct place. And on that alone I believe this is a form of insertion sort, but I'm not exactly sure. It did run faster then both bubble and selection on large randomly generated arrays (1000+ elements) when I tested it. But you all are free to post your results also. I agree that the sort above is a bit lengthy-er then bubble sort, but the point was it is likely that given the opportunity, someone's intuitively implemented sort could be faster, teach them about implementing a real-world algorithm in code, and allow them to really remember why the sort works.
Just FYI: my new version I use now uses a binary search instead of a linear search for the second loop, taking advantage of the fact that all the elements the the left of rPos are in order. And If you use this on a standard container like vector<T>, you can replace the inner insertion loop with methods like vec.insert( ... ) and vec.erase( ... )

jsmith wrote:

I think that if a newbie was to invent a sort by himself/herself knowing nothing of the sorts that are available, the selection sort would be the algorithm s/he comes up with first.

I agree. I also think that's a fine sort to start with.

jsmith wrote:

when I was learning sort algorithms in college, bubble sort was perhaps the "simplest" to remember.

I remember algorithms by how they work and what they accomplish, not by how to write the exact code. This may come from the fact that I'm strong in more then one programing language.

Gray Wolf wrote:

Simplicity and intuitiveness don't always go hand in hand.

[Bubble sort] doesn't have to be intuitive because you are given it.

True, but perhaps it is easier to learn and remember something that's intuitive then something that's a bit more foreign.

Also Gray Wolf I don't think that most people are learning about linked lists before they learn about sorting. Sorting is just needed more often.

[jsmith]

The algorithm in the original post is O(N^3).

The outer loop runs N-1 times.

The middle loop runs 1 time the first time, 2 times the next, 3 the next, up to N-2 times.
So the total number of times the middle loop runs is
1 + 2 + ... + N-2 = (N-2)(N-1)/2 = ( N^2 - 3N + 2 ) / 2 which is O( N^2).

Thus, N^2 is an upper bound on the number of times the inner loop runs. In the worst case, rPos = N - 1 and lPos = 0, meaning that the inner loop is O(N).

O(N^2) * O(N) = O(N^3).

[ne555]

template <typename T>
void sort(T array[], int length) {
	for( int rPos = 1; rPos < length; rPos++ ) { //loop A
		T ele = array[rPos];
		for( int lPos = 0; lPos < rPos; lPos++ ) //loop B
			if( ele < array[lPos] ) {
				for( int i = rPos; i > lPos; i-- ) //loop C
					array[i] = array[i - 1];
				array[lPos] = ele;
				break; // <---- look closely 
			}
	}
}

In the worst case the loops B and C will run trough rPos samples.
if the conditional is false, C is not executed, but if it is true B ends. O(n^2)
Looks like insertion sort

Selection Sort FTW. Intuitive, simple and (if the proper structure is used) optimum.

[S6k9GNh0]

Bubble sort is easy in thought even. Is the next element bigger than the current element? If so, switch. Is the next element bigger than the element after that? If so, switch. End of array? Go back to beginning and restart the process. How would you word this with a selection sort? It's almost like saying the square root of 4 is 2 is an easier concept to understand than 2 / 2 is 2.

[ne555]

That is a pseudocode, not a description. As it is it will never end, and it is not much clear how it works.
Another things, ¿what could happen if instead of looking for the next element choose a bigger gap? (or choose a variable gap)
¿or what if instead of restarting from the beginning, traverse in reverse order?

Insertion sort: Suppose you've got a sorted list. You want to add one element, so you look for the place where it should be and you insert it there. The list remains sorted.

Selection sort: You want to sort a list, it will be easy if you know the position that the elements will be in the sorted list. However you know something, the minimum element will be in the first position. The list shrank.

Merge sort: You've got two sorted lists, and want to make one sorted lists with its elements.
¿Who will go first? The minimum, of course. ¿where it is? it must be the first element of one of the lists.

It's almost like saying the square root of 4 is 2 is an easier concept to understand than 2 / 2 is 2.

Of course it is easier ;)

[Mathhead200]

ne555 wrote:

Looks like insertion sort

Insertion sort: Suppose you've got a sorted list. You want to add one element, so you look for the place where it should be and you insert it there. The list remains sorted.

That's how my sort above works, except everything at index >= rPos
is the input data, and everything at index < rPos is the current sorted list. It can sort in place in memory if written like above (still better on average with a binary search though.)

Mathhead200 wrote:

Just FYI: my new version I use now uses a binary search instead of a linear search for the second loop, taking advantage of the fact that all the elements the the left of rPos are in order. And If you use this on a standard container like vector<T>, you can replace the inner insertion loop with methods like vec.insert( ... ) and vec.erase( ... )

= O(n log₂n)

computerquip wrote:

Bubble sort is easy in thought even. Is the next element bigger than the current element? If so, switch. ... How would you word this with a selection sort?

Put the biggest (or smallest) element at the front; put the next biggest behind that; and so on...

[ne555]

@Mathhead200: The search could be faster, but the insertion remains linear. The order is still n².
However if you make a linear search starting from the end instead of the beginning, the total order will be n for an "almost sorted" list.