If the size of the array fits entirely in cache and the "collation error" is sufficiently small Bubble Sort may be faster than Insertion Sort, Shell Sort, and similar. It doesn't even depend on how big or small the array is either.Īctually, the big/small condition is important, but not actually in terms of elements so much as size in bytes.
#Selection sort vs bubble sort vs insertion sort code
Since I'm feeling generous, here's a version of some of the C++ code I have, converted to C, to illustrate the idea: rather than inserting via repeated swapping, just do it via insertion as you would with Insertion Sort.
Shell Sort is, as you know, doing insertions, i.e. Then if you call it with k=1 you get a regular insertion sort, or if you call, it from within a Shell Sort skeleton function, then you get a Shell Sort.
You can simply write your insertion sort such that instead of using ++, -, -1, +1, or 1, that you instead use += k, -= k, -k, +k, and k, where k is another parameter. The Incerpj-Sedgewick gap-table variation is far superior.Ģ. Shell Sort, as per how Donald Shell wrote it (with gap sizes that halve each time), is actually a very poor choice of gaps. Not just in terms of big-oh notation either, but in terms of actual CPU instructions executed.ġ. If the array is actually sorted, then for a good implementation the amount of work it does is equal to the amount of work required to determine if the array is sorted. It doesn't even depend on how big or small the array is either. Insertion sort is the fastest algorithm for an almost sorted array (depending on your exact definition of "almost"). If the array is large enough, then a "natural" bottom up merge sort would be fast, but it uses a second array for temporary storage, and could require a final copy array step if the the result has to be in the original array (as opposed to the second array).Actually, johnmerlino is right.
0 kommentar(er)
