I know it's a quadratric time algorithm, but how does it compare to other sorting algorithms, such as QuickSort or Bubble Sort?
Pretty much yes, but you could be a bit more descriptive in your criticism :)
Sune Rievers
2009-12-03 23:38:42
+2
A:
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.
anirudhgarg
2009-12-03 23:26:16
You could always visit all the permutations of the list and return the first one that happens to be sorted (O(n!)) :)
wrang-wrang
2009-12-03 23:39:30
+1
A:
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
Ian Henry
2009-12-03 23:31:50
That's a silly example. No-one will ever try to sort 10e78 items. "640K items should be enough for anyone" - Bill Gates
Mark Byers
2009-12-03 23:37:42
I agree with the first part of your post, but I don't think choosing a proper/fast sorting algorithm is premature optimization. Besides, as long as the system's components are loosely coupled, the sorting algorithm should be fairly easy to replace in later optimization.
Sune Rievers
2009-12-03 23:42:29
BTW, I love examples with "number of atoms in the universe", puts everything in perspective :)
Sune Rievers
2009-12-03 23:43:26
The example is one an old CS professor loved when demonstrating the unbelievable tininess of the log operator, I believe when discussing about log(n) access time. You'd never be accessing anywhere near that much data, but even if you were, it's only O(262)!
Ian Henry
2009-12-04 05:37:58
A:
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.
Greycrow
2009-12-03 23:38:49