OPTSORT Problem - Observation That Makes Sense

The Only Observation, You Need To Solve The Problem
Let’s suppose you would Sort A[L…R],
Now, this Sort is only suitable if L to R contains every value that it should contain in the Sorted version and Obviously, A[L] and A[R] must not contain their actual sorted values because if they are in their correct sorted position, then messing up with them is just gonna increase your cost.
Why? Lets Discuss →

→ say you had decided to sort a segment from A[i…j] and calculated the minimum cost. And let’s say iterating further from j and now you are at “k” and you found a number A[k] whose position in the sorted array is “p” and surprisingly i < p < j

→ Now you see Does it make sense now to sort the section from A[p…k] just to move A[k] in the right position? Think about it :innocent:

Gave it a thought? Exactly! Now you can see if you perform the above thing then you would have gained extra cost ( How? you can figure it out yourself because one can understand this he/she tries)

KINDA PSEUDO CODE TO HELP YOU UNDERSTAND ( Not providing the whole solution link because I want you to try but it is assured it is part of my original submission so it works )
( Those DEB() were used to debug, Ignore that)

5 Likes

Thanks for the wonderful explanation !!

1 Like