Merge: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 36: Line 36:


'''Correctness:''' Obvious.
'''Correctness:''' Obvious.
'''Remark:'''
Steps 2 and 3 append the elements of <math>S_2</math> and <math>S_1</math>, respectively, step-by-step. Alternatively, they could append the entire rest in one step.


== Complexity ==
== Complexity ==

Revision as of 16:42, 16 May 2015


General Information

Algorithmic problem: Merging two sorted sequences

Type of algorithm: loop

Auxiliary data: There are two current positions: [math]\displaystyle{ i_1 \in \{0,\dots,|S_1|\} }[/math] and [math]\displaystyle{ i_2 \in \{0,\dots,|S_2|\} }[/math] .

Abstract View

Invariant: Before and after each iteration:

  1. [math]\displaystyle{ S }[/math] consists exactly of all elements [math]\displaystyle{ S_1[1],\dots,S_1[i_1] }[/math] and [math]\displaystyle{ S_2[1],\dots,S_2[i_2] }[/math].
  2. [math]\displaystyle{ S }[/math] is sorted according to the comparison on [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math].

Variant: [math]\displaystyle{ i_1 + i_2 }[/math] increases by [math]\displaystyle{ 1 }[/math]; neither [math]\displaystyle{ i_1 }[/math] nor [math]\displaystyle{ i_2 }[/math] decreases.

Break condition: [math]\displaystyle{ i_1 = |S_1| }[/math] and [math]\displaystyle{ i_2 = |S_2| }[/math].

Induction Basis

Abstract view: [math]\displaystyle{ i_1 := 0 }[/math] and [math]\displaystyle{ i_2 := 0 }[/math].

Implementation: Obvious.

Proof: Nothing to show.

Induction Step

Abstract view:

  1. If [math]\displaystyle{ i_1 = |S_1| }[/math] and [math]\displaystyle{ i_2 = |S_2| }[/math], terminate the algorithm.
  2. Otherwise, if [math]\displaystyle{ i_1 = |S_1| }[/math], append [math]\displaystyle{ S_2[i_2 + 1] }[/math] at the end of [math]\displaystyle{ S }[/math] and increase [math]\displaystyle{ i_2 }[/math] by [math]\displaystyle{ 1 }[/math].
  3. Otherwise, if [math]\displaystyle{ i_2 = |S_2| }[/math], append [math]\displaystyle{ S_1[i_1 + 1] }[/math] at the end of [math]\displaystyle{ S }[/math] and increase [math]\displaystyle{ i_1 }[/math] by [math]\displaystyle{ 1 }[/math].
  4. Otherwise, if [math]\displaystyle{ S_1[i_1 +1] \lt S_2[i_2 +1] }[/math], append [math]\displaystyle{ S_1[i_1 +1] }[/math] at the of [math]\displaystyle{ S }[/math] and increase [math]\displaystyle{ i_1 }[/math] by [math]\displaystyle{ 1 }[/math].
  5. Otherwise, append [math]\displaystyle{ S_2[i_2 +1] }[/math] at the of [math]\displaystyle{ S }[/math] and increase [math]\displaystyle{ i_2 }[/math] by [math]\displaystyle{ 1 }[/math].

Implementation: Obvious.

Correctness: Obvious.

Remark: Steps 2 and 3 append the elements of [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ S_1 }[/math], respectively, step-by-step. Alternatively, they could append the entire rest in one step.

Complexity

Statement: [math]\displaystyle{ O(|S_1| + |S_2|) }[/math].

Proof: Obvious.