Is selection sort an efficient algorithm?

Question

I know it's a quadratric time algorithm, but how does it compare to other sorting algorithms, such as QuickSort or Bubble Sort?

Answer 1

Sorting algorithms generally vary based on the nature of data you have.

However, while bubble sort and selection sort are easy to understand (and implement) sorting algorithms their run time is O(n^2) i.e the worst time that you can possibly get.

As far as quick sort is concerned on an avergage it takes O(n log n) time hence it is an excellent sort. However, it too can take O(n ^ 2) in certain cases.

Answer 2

Quadratic time algorithms, depending the size of your data set, can be unbelievably slower.

n = 10e78 (about the number of atoms in the universe)

For a quadratic algorithm, that's n*(10e78). For an nlog(n) algorithm, like quicksort or mergesort, that's n*262. That's a huge difference.

But if your dataset is relatively small (< 1000 items, say), then the performance difference probably isn't going to be noticeable (unless, perhaps, the sort is being done repeatedly). In these cases it's usually best to use the simplest algorithm, and optimize later if it turns out to be too slow.

"Premature optimization is the root of all evil." -Sir Tony Hoare, popularized by Donald Knuth

Answer 3

Wikipedia knows all.

Selection sort pretty much sucks.

Answer 4

If the data you have consists of only positive integers you may want to look at Bucket Sort. The algorithm can have a linear running time O(n) in the right conditions.