Pivot partitioning by scanning: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 42: Line 42:
'''Proof:''' Obvious.
'''Proof:''' Obvious.


==Induction step==


'''Abstract view:'''
# Move each of <math>i_1,i_2</math>, and <math>i_3</math> forward as long as the invariant is not violated.
# If the algorithm is not done yet, identify two out of the three index pointers <math>i_1,i_2</math>, and <math>i_3</math>such that at least one of these two can be moved one step forward after a swap of the elements at these two positions.


'''Abstract view:''' <math>\forall v,w \in V</math> we set
'''Implementation:'''  
# <math>M(v,v):=0, \forall v \in V</math>
# If <math>i_1=m_1</math> and <math>i_2=m_2</math>  and <math>i_3=n+1</math>, terminate the algorithm and return <math>m_1,m_2-1</math>.
# <math>M(v,w):=l(v,w), (v,w) \in A</math>
# If <math>i_1<m_1</math> :
# <math>M(v,w):= +\infty</math>, otherwise
## If <math>S[i_1]=p</math> :
### Swap <math>S[i_1]</math> and <math>S[i_2]</math>.
### Set <math>i_2:=i_2+1</math> until <math>i_2=m_2</math> or else <math>S[i_2] \ne p</math>.
## Otherwise (that is, ):
### Swap  and .
###Set  until  or else .
## While  and , set .
# Otherwise (that is, ):
## Swap  and .
## Set  until  or else .
## Set  until  or else .
Correctness: Due to the various "otherwise" clauses, all possible cases are covered. Therefore, it remains to show that the invariants are maintained in each of the considered cases.
As the values of  and  are never changed after initialization, all three parts of the first invariant are trivially maintained. Since  (resp., , ) is only increased in case  (resp., , ), Invariant 2.1 is maintained as well. So, we will focus on Invariants 2.2-2.4.
If Step 2 applies, maintenance of Invariants 2.2-2.4 might be obvious. So consider Step 3. If Step 3 applies, we know that , but  or  (or both). Due to , all elements less than  are correctly placed at the positions . Therefore, both cases, the case  and  and the case  and  are impossible, because there cannot be exactly one wrongly placed element. In other words, it is  and  in Step 3. Again due to , it is  and . Steps 2.1.2 and 2.2.2 ensure  and , so we have  and . This observation justifies the procedure of Step 3.


'''Implementation:''' Obvious.
.
 
'''Proof:''' Nothing to show.
 
==Induction basis==
 
 
== Induction step ==
'''Abstract view:'''
 
'''Implementation:'''
 
'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[internal nodes]] are taken from <math>\{u_1, \ldots, u_n \}</math>.
# If <math>p</math> does not contain <math>u_i</math>, <math>p</math> is even a shortest <math>(v,w)</math>-path such that all internal nodes are taken from <math>\{u_1, \ldots , u_{i-1} \}</math>. In this case, the induction hypothesis implies that the value of <math>M(v,w)</math> immediately before the i-th iteration equals the length of <math>p</math>. Clearly, the i-th iteration does not change the value of <math>M(v,w)</math> in this case.
# On the other hand, suppose <math>p</math> does contain <math>u_i</math>. Due to the [[prefix property]], the segment of <math>p</math> from <math>v</math> to <math>u_i</math> and from <math>u_i</math> to <math>w</math> are a shortest <math>(v,u_i)</math>-path and a shortest <math>(u_i,w)</math>-path, respectively, subject to the constraint that all internal nodes are from <math>\{u_1, \ldots , u_{i-1} \}</math>. The induction hypothesis implies that tehese lengths equal the values <math>M(v,u_i)</math> and <math>M(u_i, w)</math>, respectively.
 
== Complexity ==
'''Statement:''' <math>\mathcal{O}(n^3)</math>
 
'''Proof:''' The overall loop has <math>n</math> iterations. In each iteration, we update all <math>n^2</math> matrix entities. Each update requires a constant number of steps.

Revision as of 17:10, 15 January 2015

Algorithmic problem: Pivot partioning by scanning

Prerequisites: None

Type of algorithm: loop

Auxiliary data: Five index pointers, [math]\displaystyle{ m_1,m_2,i_1,i_2,i_3 \in \mathbb N. }[/math]


Abstract View

Invariant:

  1. The values of [math]\displaystyle{ m_1 }[/math] and [math]\displaystyle{ m_2 }[/math] only depend on the input sequence and are, hence, constant throughout the loop. More specifically, in there are
    1. [math]\displaystyle{ m_1-1 }[/math] elements less than [math]\displaystyle{ p }[/math],
    2. [math]\displaystyle{ m_1-m_2 }[/math] elements equal to [math]\displaystyle{ p }[/math], and
    3. [math]\displaystyle{ n - m_2 }[/math]greater than [math]\displaystyle{ p }[/math].
  2. Before and after each iteration, it is:
    1. [math]\displaystyle{ 1 \le i_2 \le m_1 \le m_2 \le i_3 \le i_3 \le n+1 }[/math];
    2. [math]\displaystyle{ S[j] \lt p }[/math] for [math]\displaystyle{ j \in {1,...,i_1-1} }[/math]; if [math]\displaystyle{ i_1 \lt m_1 }[/math], it is [math]\displaystyle{ S[i_1] \nless p }[/math];
    3. [math]\displaystyle{ S[j] =p }[/math] for [math]\displaystyle{ j \in {m_1,...,i_2-1} }[/math]; if [math]\displaystyle{ i_2 \lt m_2 }[/math], it is [math]\displaystyle{ S[i_2] \ne p }[/math];
    4. [math]\displaystyle{ S[j] \gt p }[/math]for [math]\displaystyle{ j \in {m_2,...,i_3-1} }[/math]; if [math]\displaystyle{ i_3 \le m_1 }[/math], it is [math]\displaystyle{ S[i_3] \ngtr p }[/math].

Variant: At least one of [math]\displaystyle{ i_1,i_2 }[/math], and [math]\displaystyle{ i_3 }[/math] is increased by at least [math]\displaystyle{ 1 }[/math], none of them is decreased.

Break condition: It is [math]\displaystyle{ i_1=m_1, i_2=m_2 }[/math] and [math]\displaystyle{ i_3 = n+1 }[/math]

Induction basis

Abstract view:

  1. Set [math]\displaystyle{ m_1 }[/math] and [math]\displaystyle{ m_2 }[/math] according to the loop invariant.
  2. Initialize [math]\displaystyle{ i_1,i_2 }[/math] and [math]\displaystyle{ i_3 }[/math].

Implementation:

  1. Set [math]\displaystyle{ m_1:=1 }[/math] .
  2. For [math]\displaystyle{ j \in {1,...,n} }[/math]: If [math]\displaystyle{ S[j]\lt p }[/math] increase [math]\displaystyle{ m_1 }[/math] by [math]\displaystyle{ 1 }[/math].
  3. Set [math]\displaystyle{ m_2:m_1 }[/math]
  4. For [math]\displaystyle{ j \in {1,...,n} }[/math]: If [math]\displaystyle{ S[j]=p }[/math] increase [math]\displaystyle{ m_2 }[/math] by [math]\displaystyle{ 1 }[/math].
  5. [math]\displaystyle{ i_1:=1 }[/math].
  6. [math]\displaystyle{ i_2:=m_1 }[/math].
  7. [math]\displaystyle{ i_3:=m_2 }[/math].
  8. While [math]\displaystyle{ i_1\lt m_1 }[/math] and [math]\displaystyle{ S[j]\lt p }[/math], set [math]\displaystyle{ i_1:=i_1+1 }[/math].
  9. While [math]\displaystyle{ i_2\lt m_2 }[/math] and [math]\displaystyle{ S[j]=p }[/math] , set [math]\displaystyle{ i_2:=i_2+1 }[/math].
  10. While [math]\displaystyle{ i_3\lt n }[/math] and [math]\displaystyle{ S[j]\gt p }[/math], set [math]\displaystyle{ i_3:=i_3+1 }[/math] .

Proof: Obvious.

Induction step

Abstract view:

  1. Move each of [math]\displaystyle{ i_1,i_2 }[/math], and [math]\displaystyle{ i_3 }[/math] forward as long as the invariant is not violated.
  2. If the algorithm is not done yet, identify two out of the three index pointers [math]\displaystyle{ i_1,i_2 }[/math], and [math]\displaystyle{ i_3 }[/math]such that at least one of these two can be moved one step forward after a swap of the elements at these two positions.

Implementation:

  1. If [math]\displaystyle{ i_1=m_1 }[/math] and [math]\displaystyle{ i_2=m_2 }[/math] and [math]\displaystyle{ i_3=n+1 }[/math], terminate the algorithm and return [math]\displaystyle{ m_1,m_2-1 }[/math].
  2. If [math]\displaystyle{ i_1\lt m_1 }[/math] :
    1. If [math]\displaystyle{ S[i_1]=p }[/math] :
      1. Swap [math]\displaystyle{ S[i_1] }[/math] and [math]\displaystyle{ S[i_2] }[/math].
      2. Set [math]\displaystyle{ i_2:=i_2+1 }[/math] until [math]\displaystyle{ i_2=m_2 }[/math] or else [math]\displaystyle{ S[i_2] \ne p }[/math].
    2. Otherwise (that is, ):
      1. Swap and .
      2. Set until or else .
    3. While and , set .
  3. Otherwise (that is, ):
    1. Swap and .
    2. Set until or else .
    3. Set until or else .

Correctness: Due to the various "otherwise" clauses, all possible cases are covered. Therefore, it remains to show that the invariants are maintained in each of the considered cases. As the values of and are never changed after initialization, all three parts of the first invariant are trivially maintained. Since (resp., , ) is only increased in case (resp., , ), Invariant 2.1 is maintained as well. So, we will focus on Invariants 2.2-2.4. If Step 2 applies, maintenance of Invariants 2.2-2.4 might be obvious. So consider Step 3. If Step 3 applies, we know that , but or (or both). Due to , all elements less than are correctly placed at the positions . Therefore, both cases, the case and and the case and are impossible, because there cannot be exactly one wrongly placed element. In other words, it is and in Step 3. Again due to , it is and . Steps 2.1.2 and 2.2.2 ensure and , so we have and . This observation justifies the procedure of Step 3.

.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Pivot_partitioning_by_scanning&oldid=2756"