Yet another fun puzzle! Antonio, do you create these yourself?
Obvious answer is to take a second sorted copy of the list and find the first entry which does not match the unsorted list.. that's the index of the start of the "needs to be sorted" range. Similarly for the end. But that's the lazy answer using O(N) extra storage and ugly O(NlogN) sorting. A much more practical algorithm uses O(1) storage. Answer below..
Go down your unsorted list. Maintain a single tentative "best-s-so-far" index, initialized to the index of the first unsorted entry which is greater than its successor. Continue one at time down the list after that, if the next entry value is less than v[s], your s is still too high.. do a binary search between [0,s] to find a new, smaller, s(where the current value would go when sorted.). Repeat until the end of the list, this is your final s. A similar symmetric bottom up test will find e.
Yet another fun puzzle! Antonio, do you create these yourself?
ReplyDeleteObvious answer is to take a second sorted copy of the list and find the first entry which does not match the unsorted list.. that's the index of the start of the "needs to be sorted" range. Similarly for the end. But that's the lazy answer using O(N) extra storage and ugly O(NlogN) sorting. A much more practical algorithm uses O(1) storage. Answer below..
Go down your unsorted list. Maintain a single tentative "best-s-so-far" index, initialized to the index of the first unsorted entry which is greater than its successor. Continue one at time down the list after that, if the next entry value is less than v[s], your s is still too high.. do a binary search between [0,s] to find a new, smaller, s(where the current value would go when sorted.). Repeat until the end of the list, this is your final s. A similar symmetric bottom up test will find e.
Nice problem!
I know this one! Run Time Type Information! ;)
ReplyDelete