[algogeeks] Re: Sorting a array which is already sorted but has some disorder
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.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
Insertion sort is pretty good for this. I've seen a case where we were maintaining a list of items sorted by rank. The ranks changed occasionally, but usually only by +/- 5 at the most, in a list of several million. Insertion sort was much faster at putting them back in order compared to quicksort, in this one special case. Don On Oct 16, 11:17 am, sravanreddy001 sravanreddy...@gmail.com wrote: OK.. what is expected? its again sort problem, unless the amount of distortion is constant, in which a Binary search or Insertion sort can be employed to do in O(n) time. Didn't give a programmatic thought. But, if the the amount of distortion is of order n, then sort in O(n lg n) -- 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.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
Yes.. And the reason is best case of insertion sort is in the order of n. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_OJfijjiFVoJ. 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.
Re: [algogeeks] Re: Sorting a array which is already sorted but has some disorder
But still it will depend on the number of distortions.If the number of distortions are large enuf(=n/2) then its better to resort in the most generic case.Even insertion sort would cost o(n^2) in that case. On Tue, Oct 18, 2011 at 3:57 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes.. And the reason is best case of insertion sort is in the order of n. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_OJfijjiFVoJ. 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
We can just keep swapping characters, until it gets in order. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/3VFwJUGRGS0J. 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.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
OK.. what is expected? its again sort problem, unless the amount of distortion is constant, in which a Binary search or Insertion sort can be employed to do in O(n) time. Didn't give a programmatic thought. But, if the the amount of distortion is of order n, then sort in O(n lg n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ttSTk3_w6qIJ. 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.
