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
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Amelio Vazquez-Reina Apr 4 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$ – Amelio Vazquez-Reina Apr 4 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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