0
$\begingroup$

Are there any known / efficient dynamic programming solutions to sorting?

I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal substructure, but I wonder if there are transformations and representations of the sorting problem where these conditions are met, and even better, where doing so may actually be useful.

$\endgroup$

2 Answers 2

2
$\begingroup$

Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.

Let $A[1:n]$ be the array to sort, assume for simplicity that all its elements are distinct, and define $OPT[i]$ as the sorted array containing the smallest $i$ elements of $A$.

According to this definition $OPT[0]$ is the empty array and, if you solve the subproblems in increasing order of $i$, you can recombine them as follows:

$$\displaystyle \forall i=1,\dots,n \quad\quad OPT[i] = OPT[i-1] \circ \min_{x \in A \setminus OPT[i-1]} x,$$

where $\circ$ denotes concatenation. The optimal solution is in $OPT[n]$. Computing any $OPT[i]$ requires $O(n)$ time, therefore the total time needed is $O(n^2)$. At any point in time, you only need to store one $OPT[i]$, so the space complexity is $O(n)$.

This is essentially an ugly way to describe selection sort.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks - correct me if I'm wrong but while your formulation of insertion sort displays optimal substructure it does not seem to display the property of overlapping subproblems, i.e. subproblems (in plural) that share subsubproblems and where you can compute their solutions only once and reuse them. $\endgroup$ Apr 4, 2020 at 17:15
  • 1
    $\begingroup$ Ok - can you share references of the algorithm that you mentioned that does not have this property and where the authors claim it's a DP algorithm? $\endgroup$ Apr 4, 2020 at 19:51
0
$\begingroup$

You can always reduce sorting to another problem. Moreover, sorting is in P, so it can be reduced in polynomial time to any other problem in P. There are countless problems that can be solved via dynamic programming in P, so the answer is yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.