As others have said this is not stated precisely. There are lots of
sorting algorithms that have O(n) behavior on nearly sorted
data.Quicksort and mergesort can both be implemented to get this
behavior. However if you are very confident that elements are not very
far from their correct sorted location, the insertion sort approach
works well. In general if items are no more than T locations out of
order, then the run time is O(nT). In your example,
p = 1; // next item to be scanned for correct order
while (a[p] > a[p-1]) {
// p is out of order; insert it at correct location
tmp = a[p];
q = p;
while (q > 0 && tmp < a[q-1]) {
a[q] = a[q-1];
q = q - 1;
}
a[q] = tmp;
}
In some applications, items get bumped a little bit out of order as a
bigger algorithm runs, and you know exactly which ones. In this case
you often want to restore the bumped item to sorted order immediately.
One example of this is some scan conversion/fill algorithms for
polygons. When edges cross, the list of active edges goes a bit out
of order and can be quickly restored by moving only the relevant
edges. Run time here is just O(T).
On Oct 16, 11:00 am, Siddharth Pipriya <sid....@gmail.com> wrote:
> Question: If given string with sorted order with some disorder in
> between for example
> "abcfedghi" you need to make it as "abcdefghi" with no extra space
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
