Menu
I have an array of values which is almost, but not quite sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently? (performance is absolutely crucial here and should be way faster than O(N)).
I know about smoothsort, but I can't find Java implementation. Does anyone know whether it is already implemented? Or what I can use for this task instead of smoothsort?
957
When the array is almost sorted, insertion sort can be preferred. When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well. When the array is sorted, insertion and bubble sort gives complexity of n but quick sort gives complexity of n^2.
Many sorting algorithms are available, but the one which is best suited for the almost sorted array is the insertion sort.
Insertion sort is the clear winner on this initial condition. Bubble sort is fast, but insertion sort has lower overhead. Shell sort is fast because it is based on insertion sort. Merge sort, heap sort, and quick sort do not adapt to nearly sorted data.
In Insertion sort only takes O(1) auxiliary space complexity. It sorts the entire array just by using an extra variable. Insertion Sort is preferred for fewer elements. It becomes fast when data is already sorted or nearly sorted because it skips the sorted values.
There are many good algorithms for this.
Smoothsort is my personal favorite... I actually worked all the math out here if you're curious why it works so well.
A fairly good algorithm for already-sorted data is natural mergesort, which is a bottom-up version of mergesort that works by treating the input as a sequence of sorted subranges, then making multiple passes over the range merging adjacent sorted ranges. It runs in O(n) time if the data is already sorted (because it can detect that there's only one sorted range), and O(n lg n) in the worst case. This algorithm works quite well if the data is "block sorted"; that is, it consists of a lot of sorted blocks placed right next to one another.
Straight insertion sort definitely works well for mostly-sorted data, but can degenerate very badly on a lot of inputs. Some really good sorts (like introsort) actually use this property of insertion sort to do a "cleanup step" on the input.
136
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
