Why is BubbleSort considered so important? I'd say it's the last failed algorithm you should know.
Important ones would be:
InsertionSort and it's efficient variations ShellSort and HeapSort. Because it has a O(N) best case behavior (when already sorted).
QuickSort, because in it's randomized version illustrates the power of random, and it's simplicity and raw speed.
MergeSort because of it's stability and usefulness in parallel algorithms, distributed algorithms, and databases (ie. Merge join)
RadixSoft because it's not a comparison algorithm and takes time O(n lg u) (which is MUCH faster than Quicksort). Van Embde Boas if you want to get really performant with these concepts with time O(n lg lg u).
BitonicSort because it's a basic parallel sorting algorithm and also used in the more sophisticated theoretical efficient sorting algorithms.
TimSort: because it's the one that's actually implemented in Python and Java so it's a good case study of a real world sorting algorithm.
But I think you can safely forget BubbleSort ever existed. I think SelectionSort is way more intuitive anyway.
Actually, BubbleSort IS an important sort, and anybody calling him or herself a Software engineer needs to understand how it works.
Reason? Well, you can't understand the concept of Light completely without understanding what the Darkness is. I know it's toooo dramatic but believe me, you need to know what bad algorithms are in order to understand the good ones.
Why is BubbleSort considered so important? I'd say it's the last failed algorithm you should know.
Important ones would be:
InsertionSort and it's efficient variations ShellSort and HeapSort. Because it has a O(N) best case behavior (when already sorted).
QuickSort, because in it's randomized version illustrates the power of random, and it's simplicity and raw speed.
MergeSort because of it's stability and usefulness in parallel algorithms, distributed algorithms, and databases (ie. Merge join)
RadixSoft because it's not a comparison algorithm and takes time O(n lg u) (which is MUCH faster than Quicksort). Van Embde Boas if you want to get really performant with these concepts with time O(n lg lg u).
BitonicSort because it's a basic parallel sorting algorithm and also used in the more sophisticated theoretical efficient sorting algorithms.
TimSort: because it's the one that's actually implemented in Python and Java so it's a good case study of a real world sorting algorithm.
But I think you can safely forget BubbleSort ever existed. I think SelectionSort is way more intuitive anyway.
Thanks for the answer. I will look to add TimSort to the article.
sorry I didn't mean to sound so dogmatic..
but wanted to share an alternative set of "essential" algorithms
Actually, BubbleSort IS an important sort, and anybody calling him or herself a Software engineer needs to understand how it works.
Reason? Well, you can't understand the concept of Light completely without understanding what the Darkness is. I know it's toooo dramatic but believe me, you need to know what bad algorithms are in order to understand the good ones.
sure.. though selection sort is sufficient to represent naive sorting..
but I'll grant that you have a point