"bubble sorting", "selective sorting" and the function "sort()"

when should we use “bubble sorting”, “selective sorting” and the function “sort()” and what is the difference between them?

Never.

(Silly 10 char minimum… There’s really nothing more to say about that.)

2 Likes

Bubble sort and selection sort take time proportional to the square of the number of elements being sorted, N*N, where N is the number of elements being sorted.

sort() uses Timsort, one of many algorithms that uses time proportional to N * log(N).

For example, if you were sorting a thousand elements, bubble sort would typically take on the order of a million operations, but sort() would use on the order of 10,000 operations(*), one hundred times as fast, and it only gets worse as you get bigger collections.

Always use sort() and in fact, always use the built-in algorithms in preference to your own code.

The only reason they teach you bubble sort in class is because it’s easy, not because anyone ever uses it.

(* - the actual truth is a bit more complicated but doesn’t change the big picture…)

3 Likes

I think the bigger reason people teach it is that people have taught it. It’s a virus.

See this and this (I only dislike the postponements of discussions of optimized versions).

2 Likes

thanks for the informative and short answer.

1 Like

good article ,thanks!

To add some nuance to this: It’s very common to, in data structures and algorithms courses, point out that merge sort is O(n log n) average, worst, and best cases, but what Timsort shines at isn’t just the numbers in random tests, but real-world work. It actually can achieve significantly better asymptotic complexitty on many real-world sorting tasks (up to O(n) on already-sorted lists, but unlike bubble sort, scaling smoothly towards that with nearly-sorted lists), AND it has very good short-list performance, which is where Big O notation doesn’t really tell you anything.

In fact, Timsort switches to an O(n²) algorithm for short lists or short sections of lists, because at that point, the Big O value tells you very little. It’s an algorithm that’s proven so good in Python that it’s been adopted by a number of others too!

3 Likes

This is a fun read read about the subtleties of python’s current sorting algorithm.

1 Like