Pivot partioning: Difference between revisions
Jump to navigation
Jump to search
(→Input) |
(→Output) |
||
Line 7: | Line 7: | ||
A permutation of <math>S</math> and <math>m_1,\,m_2\in\{1,\ldots,n+1\}</math> such that <math>m_1\le m_2</math> and | A permutation of <math>S</math> and <math>m_1,\,m_2\in\{1,\ldots,n+1\}</math> such that <math>m_1\le m_2</math> and | ||
# <math>S[i]<p</math> for <math>i\in\{1,\ldots,m_1-1\}</math>; | # <math>S[i]<p</math> for <math>i\in\{1,\ldots,m_1-1\}</math>; | ||
# <math>S[i]=p</math> for <math>i\in\{ | # <math>S[i]=p</math> for <math>i\in\{m_1,\ldots,m_2-1\}</math>; | ||
# <math>S[i]>p</math> for <math>i\in\{m_2,\ldots,n\}</math>. | # <math>S[i]>p</math> for <math>i\in\{m_2,\ldots,n\}</math>. | ||
Latest revision as of 13:34, 5 May 2015
Input
- An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math].
- A definition of comparison on the component type of [math]\displaystyle{ S }[/math].
- A pivot value of the component type of [math]\displaystyle{ S }[/math].
Output
A permutation of [math]\displaystyle{ S }[/math] and [math]\displaystyle{ m_1,\,m_2\in\{1,\ldots,n+1\} }[/math] such that [math]\displaystyle{ m_1\le m_2 }[/math] and
- [math]\displaystyle{ S[i]\lt p }[/math] for [math]\displaystyle{ i\in\{1,\ldots,m_1-1\} }[/math];
- [math]\displaystyle{ S[i]=p }[/math] for [math]\displaystyle{ i\in\{m_1,\ldots,m_2-1\} }[/math];
- [math]\displaystyle{ S[i]\gt p }[/math] for [math]\displaystyle{ i\in\{m_2,\ldots,n\} }[/math].
Objective
N/A
Complexity
Polynomial.