Array list: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(20 intermediate revisions by one other user not shown)
Line 1: Line 1:
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}}
'''Algorithmic problem:''' [[Ordered sequence#Remove|Ordered sequence: remove]]
'''Algorithmic problem:''' [[Ordered sequence#Remove|Ordered sequence: remove]]


Line 31: Line 33:
### Set first.A<math>[</math>first.n<math>]:=</math>void.
### Set first.A<math>[</math>first.n<math>]:=</math>void.
### Set first.n:=first.n<math>-1</math>.
### Set first.n:=first.n<math>-1</math>.
## Terminate the algorithm and return <math>true</math>.
## Terminate the algorithm and return '''true'''.
# Otherwise (that is, <math>first /ne void</math> and <math>K \notin\{</math>first.A <math>[1],...,first.a[first.n]\}</math>), set  <math>p:=</math>first.
# Otherwise (that is, first<math>\neq</math>void and <math>K \notin\{</math>first.A <math>[1],...,</math>first.A[first.n]<math>\}</math>), set  <math>p:=</math>first.


'''Proof:''' If <math>p</math>.first<math>=</math>void or <math>K \notin\{</math>first.A<math>[1],...,</math>first.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>first \ne void</math> and <math>K \in \{first.A[1],...,first.A[first.n]\}</math>.  
'''Proof:''' If <math>p</math>.first<math>=</math>void or <math>K \notin\{</math>first.A<math>[1],...,</math>first.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that first<math>\neq</math>void and <math>K \in \{</math>first.A[1],...,first.A[first.n]<math>\}</math>.  
If first.n<math>=1</math>, the array would be empty after removing <math>K</math>, so the first list item is decoupled from the list in Step 2.1. Otherwise, <math>K</math> is removed and the array is rearranged accordingly in Steps 2.2.2-2.2.4.
If first.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple the first list item from the list. Otherwise (that is, first.n<math>>1</math>), <math>K</math> is removed and the array is rearranged accordingly in Steps 2.2.2-2.2.4.


==Induction step==
==Induction step==


'''Abstract view:''' If <math>p</math> has reached the end of the array list, the algorithm terminates. Otherwise, if the key to be removed is in the current array, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).
'''Abstract view:''' If <math>p</math> has reached the [[Sets and sequences#Ordered and sorted sequences|tail]] of the array list, the algorithm terminates. Otherwise, if the key to be removed is in the array of the very next array list item, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).


'''Implementation:'''
'''Implementation:'''
# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .
# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return '''false'''.
# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,<math>p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
## If <math>p</math>.next.n<math>=1</math>, set .<math>p</math>next<math>p:=</math>.next.next.
## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.
## Otherwise:
## Otherwise:
### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.
### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.
### For <math>h=j,..,p</math>.next.n<math>-1</math> (in this order): Set <math>p</math>.next.A<math>[h]:=p</math>.next.A<math>[h+1]</math>.
### For <math>h=j,..,p</math>.next.n<math>-1</math> (in this order): Set <math>p</math>.next.A<math>[h]:=p</math>.next.A<math>[h+1]</math>.
### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.
### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.
### Set <math>p</math>.next.n<math>:=p</math>.next.n<math>-1</math>.
### Set <math>p</math>.next.n<math>:=p</math>.next.n <math>-1</math>.
## Terminate the algorithm and return <math>true</math>.
## Terminate the algorithm and return '''true'''.
# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set  <math>p:=p</math>.next.
# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set  <math>p:=p</math>.next.


'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.  
'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>.next.n]<math>\}</math>.  
If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so this list item is decoupled from the list in Step 2.1. Otherwise, it is removed and the array is rearranged accordingly in Steps 2.2.2-2.2.4.
If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, <math>K</math> is overwritten and the array is rearranged accordingly in Step 2.2.


== Complexity ==
== Complexity ==

Latest revision as of 23:11, 19 June 2015

Algorithmic problem: Ordered sequence: remove

Prerequisites:

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to array list item of type [math]\displaystyle{ \mathcal{K} }[/math]".


Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The pointer [math]\displaystyle{ p }[/math] points to the array list item at position [math]\displaystyle{ i+1 }[/math] (or is void if no such item exists).
  2. None of the arrays at positions [math]\displaystyle{ 1,...,i+1 }[/math] contains [math]\displaystyle{ K }[/math].

Variant: The pointer [math]\displaystyle{ p }[/math] is moved one step forward to the next array list item.

Break condition: Either it is [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void or, otherwise, it is [math]\displaystyle{ K=p }[/math].next.A[math]\displaystyle{ [j] }[/math] for some [math]\displaystyle{ j \in \{1,...,p }[/math].next.n [math]\displaystyle{ \} }[/math].

Induction basis

Abstract view: If the list is empty, the algorithm terminates. Otherwise, if the key to be removed is in the first array, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).

Implementation:

  1. If first[math]\displaystyle{ = }[/math]void, terminate the algorithm and return false.
  2. Otherwise, if [math]\displaystyle{ K \in \{ }[/math]first.A [math]\displaystyle{ [1],..., }[/math]first.A[first.n] [math]\displaystyle{ \} }[/math]:
    1. If first.n[math]\displaystyle{ =1 }[/math], set first[math]\displaystyle{ = }[/math]first.next.
    2. Otherwise:
      1. Let [math]\displaystyle{ j \in\{1,..., }[/math]first.n [math]\displaystyle{ \} }[/math] such that first.A[math]\displaystyle{ [j]=K }[/math].
      2. For [math]\displaystyle{ h=j,..., }[/math]first.n[math]\displaystyle{ -1 }[/math] (in this order): Set first.A [math]\displaystyle{ [h]:= }[/math]first.A[math]\displaystyle{ [h+1] }[/math].
      3. Set first.A[math]\displaystyle{ [ }[/math]first.n[math]\displaystyle{ ]:= }[/math]void.
      4. Set first.n:=first.n[math]\displaystyle{ -1 }[/math].
    3. Terminate the algorithm and return true.
  3. Otherwise (that is, first[math]\displaystyle{ \neq }[/math]void and [math]\displaystyle{ K \notin\{ }[/math]first.A [math]\displaystyle{ [1],..., }[/math]first.A[first.n][math]\displaystyle{ \} }[/math]), set [math]\displaystyle{ p:= }[/math]first.

Proof: If [math]\displaystyle{ p }[/math].first[math]\displaystyle{ = }[/math]void or [math]\displaystyle{ K \notin\{ }[/math]first.A[math]\displaystyle{ [1],..., }[/math]first.A[first.n][math]\displaystyle{ \} }[/math], correctness is obvious. So consider the case that first[math]\displaystyle{ \neq }[/math]void and [math]\displaystyle{ K \in \{ }[/math]first.A[1],...,first.A[first.n][math]\displaystyle{ \} }[/math]. If first.n[math]\displaystyle{ =1 }[/math], the array would be empty after removing [math]\displaystyle{ K }[/math], so Step 2.1 is right to decouple the first list item from the list. Otherwise (that is, first.n[math]\displaystyle{ \gt 1 }[/math]), [math]\displaystyle{ K }[/math] is removed and the array is rearranged accordingly in Steps 2.2.2-2.2.4.

Induction step

Abstract view: If [math]\displaystyle{ p }[/math] has reached the tail of the array list, the algorithm terminates. Otherwise, if the key to be removed is in the array of the very next array list item, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).

Implementation:

  1. If [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void, terminate the algorithm and return false.
  2. Otherwise, if [math]\displaystyle{ K \in \{p }[/math].next.A[[math]\displaystyle{ 1 }[/math]],...,[math]\displaystyle{ p }[/math].A.next.A[[math]\displaystyle{ p }[/math].next.n][math]\displaystyle{ \} }[/math]:
    1. If [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ =1 }[/math], set [math]\displaystyle{ p }[/math].next[math]\displaystyle{ := }[/math].next.next.
    2. Otherwise:
      1. Let [math]\displaystyle{ j \in \{1,...,p }[/math].next.n[math]\displaystyle{ \} }[/math] such that [math]\displaystyle{ p }[/math].next.A.[math]\displaystyle{ [j]=K }[/math].
      2. For [math]\displaystyle{ h=j,..,p }[/math].next.n[math]\displaystyle{ -1 }[/math] (in this order): Set [math]\displaystyle{ p }[/math].next.A[math]\displaystyle{ [h]:=p }[/math].next.A[math]\displaystyle{ [h+1] }[/math].
      3. Set [math]\displaystyle{ p }[/math].next.A[math]\displaystyle{ [p }[/math].next.n[math]\displaystyle{ ]:= }[/math]void.
      4. Set [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ :=p }[/math].next.n [math]\displaystyle{ -1 }[/math].
    3. Terminate the algorithm and return true.
  3. Otherwise (that is, [math]\displaystyle{ p }[/math].next[math]\displaystyle{ \ne }[/math]void and [math]\displaystyle{ K\notin\{p }[/math].next.A[math]\displaystyle{ [1],..., }[/math].next.A[p.next.n][math]\displaystyle{ \} }[/math]), set [math]\displaystyle{ p:=p }[/math].next.

Correctness: If [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void or [math]\displaystyle{ K\notin\{p }[/math].next.A[math]\displaystyle{ [1],...,p }[/math].next.A[first.n][math]\displaystyle{ \} }[/math], correctness is obvious. So consider the case that [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void and [math]\displaystyle{ K\in\{p }[/math].next.A[math]\displaystyle{ [1],...,p }[/math].next.A[[math]\displaystyle{ p }[/math].next.n][math]\displaystyle{ \} }[/math]. If [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ =1 }[/math], the array would be empty after removing [math]\displaystyle{ K }[/math], so Step 2.1 is right to decouple this list item from the list. Otherwise, [math]\displaystyle{ K }[/math] is overwritten and the array is rearranged accordingly in Step 2.2.

Complexity

Statement: Linear in the length of the sequence in the worst case.

Proof: Obvious.

Further information