Pivot partioning: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 2: Line 2:
# An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n</math>.
# An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n</math>.
# A definition of [[Genericity#Comparison|comparison]] on the component type of <math>S</math>.
# A definition of [[Genericity#Comparison|comparison]] on the component type of <math>S</math>.
# A '''pivot valiue''' of the component type of <math>S</math>.
# A '''pivot value''' of the component type of <math>S</math>.


==Output==
==Output==
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\{m_11,\ldots,m_2-1\}</math>;
# <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

  1. An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math].
  2. A definition of comparison on the component type of [math]\displaystyle{ S }[/math].
  3. 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

  1. [math]\displaystyle{ S[i]\lt p }[/math] for [math]\displaystyle{ i\in\{1,\ldots,m_1-1\} }[/math];
  2. [math]\displaystyle{ S[i]=p }[/math] for [math]\displaystyle{ i\in\{m_1,\ldots,m_2-1\} }[/math];
  3. [math]\displaystyle{ S[i]\gt p }[/math] for [math]\displaystyle{ i\in\{m_2,\ldots,n\} }[/math].

Objective

N/A

Complexity

Polynomial.

Known algorithms

  1. Pivot partitioning by scanning