Array list: insert at position - Revision history

Weihe: /* Induction step */

2015-09-18T12:57:38Z

Induction step

← Older revision		Revision as of 12:57, 18 September 2015
Line 41:		Line 41:
	###Set <math>p'</math>.next<math>=p</math>.next.		###Set <math>p'</math>.next<math>=p</math>.next.
	###Set <math>p</math>.next<math>:=p'</math>.		###Set <math>p</math>.next<math>:=p'</math>.
	###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil j \rceil]:=p.A[\lceil p.n/2+j ~~\rceil~~]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.		###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil j \rceil]:=p.A[\lceil p.n/2 \rceil + j ]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.
	###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.		###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.
	## If <math>l - </math>sum<math> > p.n</math>:		## If <math>l - </math>sum<math> > p.n</math>:

Weihe: /* Induction step */

2015-09-18T12:56:59Z

Induction step

← Older revision		Revision as of 12:56, 18 September 2015
Line 41:		Line 41:
	###Set <math>p'</math>.next<math>=p</math>.next.		###Set <math>p'</math>.next<math>=p</math>.next.
	###Set <math>p</math>.next<math>:=p'</math>.		###Set <math>p</math>.next<math>:=p'</math>.
	###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil ~~+ j~~]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.		###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil j \rceil]:=p.A[\lceil p.n/2+j \rceil]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.
	###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.		###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.
	## If <math>l - </math>sum<math> > p.n</math>:		## If <math>l - </math>sum<math> > p.n</math>:

Luedecke at 23:10, 19 June 2015

2015-06-19T23:10:17Z

← Older revision		Revision as of 23:10, 19 June 2015
Line 1:		Line 1:
			[[Category:Videos]]
			{{#ev:youtube\|https://www.youtube.com/watch?v=uYTck0kDvl4\|500\|right\|\|frame}}
	'''Algorithmic problem:''' [[Ordered sequence#Insert at position\|Ordered sequence: insert at position]]		'''Algorithmic problem:''' [[Ordered sequence#Insert at position\|Ordered sequence: insert at position]]

Weihe: /* Induction step */

2015-05-17T11:17:19Z

Induction step

← Older revision		Revision as of 11:17, 17 May 2015
Line 30:		Line 30:

	'''Implementation:'''		'''Implementation:'''
			# If <math>p=</math> void, terminate the algorithm and return '''false'''.
	# If sum<math>+ p.n < \ell</math>:		# If sum<math>+ p.n < \ell</math>:
	## Set sum<math>:=</math>sum<math>+ p.n</math>.		## Set sum<math>:=</math>sum<math>+ p.n</math>.
Line 45:		Line 46:
	## Otherwise, set <math>m:=l -</math>sum<math>+ 1</math>.		## Otherwise, set <math>m:=l -</math>sum<math>+ 1</math>.
	## For <math>j=p.n, \ldots, m</math> (in this order), set <math>p.A[j+1]:=p.A[j]</math>.		## For <math>j=p.n, \ldots, m</math> (in this order), set <math>p.A[j+1]:=p.A[j]</math>.
			## Set <math>p.A[m]:=K</math>.
			# Return '''true'''.

	'''Correctness:''' Note that, in an implementation of [[Ordered sequence#Insert at position\|Ordered sequence: insert at position]], we may assume <math>l \leq</math>number(). Therefore, we do not have to care about the end of the list. In the case sum<math>+ p.n < l</math>, we simply have to update sum and <math>p</math>, which is obviously done correctly. So consider the case sum<math>+ p.n \ge l</math>, which means that the position where <math>K</math> has to be inserted is in the array list item to which <math>p</math> currently points. If that array is full, new space must be allocated. Step 2.1 does that and distributes the elements roughly equally over both items. Steps 2.2 - 2.3 ensure that <math>p</math> points to the array where to insert <math>K</math> and <math>m</math> identifies the correct insert position. Step 2.4 empties the array component where to insert the new element by moving, exactly one position forward, the value at the position and the values at all later position (which is possible because the array is not full in any case).		'''Correctness:''' Note that, in an implementation of [[Ordered sequence#Insert at position\|Ordered sequence: insert at position]], we may assume <math>l \leq</math>number(). Therefore, we do not have to care about the end of the list. In the case sum<math>+ p.n < l</math>, we simply have to update sum and <math>p</math>, which is obviously done correctly. So consider the case sum<math>+ p.n \ge l</math>, which means that the position where <math>K</math> has to be inserted is in the array list item to which <math>p</math> currently points. If that array is full, new space must be allocated. Step 2.1 does that and distributes the elements roughly equally over both items. Steps 2.2 - 2.3 ensure that <math>p</math> points to the array where to insert <math>K</math> and <math>m</math> identifies the correct insert position. Step 2.4 empties the array component where to insert the new element by moving, exactly one position forward, the value at the position and the values at all later position (which is possible because the array is not full in any case).

Weihe: /* Induction step */

2015-05-17T11:14:49Z

Induction step

← Older revision		Revision as of 11:14, 17 May 2015
Line 27:		Line 27:
	==Induction step==		==Induction step==

	'''Abstract view:''' If the position <math>l</math> is in the current array, insert <math>K</math> (if the array is full, split it first).		'''Abstract view:''' If the position <math>\ell</math> is in the current array, insert <math>K</math> (if the array is full, split it first).

	'''Implementation:'''		'''Implementation:'''
	# If sum<math>+ p.n < l</math>:		# If sum<math>+ p.n < \ell</math>:
	## Set sum<math>:=</math>sum<math>+ p.n</math>.		## Set sum<math>:=</math>sum<math>+ p.n</math>.
	## Set <math>p:=p</math>.next.		## Set <math>p:=p</math>.next.

Weihe: /* Abstract view */

2015-05-17T11:14:21Z

Abstract view

← Older revision		Revision as of 11:14, 17 May 2015
Line 15:		Line 15:
	'''Variant:''' The pointer <math>p</math> is moved one step forward to the next array.		'''Variant:''' The pointer <math>p</math> is moved one step forward to the next array.

	'''Break condition:''' It is sum <math>+ p.n \ge l</math>.		'''Break condition:''' It is sum <math>+ p.n \ge\ell</math>.

	==Induction basis==		==Induction basis==

Weihe: /* Induction step */

2015-05-17T11:12:00Z

Induction step

← Older revision		Revision as of 11:12, 17 May 2015
Line 32:		Line 32:
	# If sum<math>+ p.n < l</math>:		# If sum<math>+ p.n < l</math>:
	## Set sum<math>:=</math>sum<math>+ p.n</math>.		## Set sum<math>:=</math>sum<math>+ p.n</math>.
	## Set <math>p:=p~~.next~~</math>.		## Set <math>p:=p</math>.next.
	#Otherwise:		#Otherwise:
	##If <math>p.n=N</math>:		##If <math>p.n=N</math>:

Weihe: /* Induction step */

2015-05-17T11:11:41Z

Induction step

← Older revision		Revision as of 11:11, 17 May 2015
Line 36:		Line 36:
	##If <math>p.n=N</math>:		##If <math>p.n=N</math>:
	###Create a new array list item and let <math>p'</math> point to this new list item.		###Create a new array list item and let <math>p'</math> point to this new list item.
	###Set <math>p'</math>.next=p</math>.next.		###Set <math>p'</math>.next<math>=p</math>.next.
	###Set <math>p</math>.next<math>:=p'</math>.		###Set <math>p</math>.next<math>:=p'</math>.
	###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.		###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.

Weihe: /* Induction step */

2015-05-17T11:11:18Z

Induction step

← Older revision		Revision as of 11:11, 17 May 2015
Line 36:		Line 36:
	##If <math>p.n=N</math>:		##If <math>p.n=N</math>:
	###Create a new array list item and let <math>p'</math> point to this new list item.		###Create a new array list item and let <math>p'</math> point to this new list item.
	###Set <math>p'.next=p~~.next~~</math>.		###Set <math>p'</math>.next=p</math>.next.
	###Set <math>p.next:=p'</math>.		###Set <math>p</math>.next<math>:=p'</math>.
	###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.		###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.
	###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.		###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.

Weihe: /* Induction step */

2015-05-17T11:08:24Z

Induction step

← Older revision		Revision as of 11:08, 17 May 2015
Line 40:		Line 40:
	###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.		###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.
	###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.		###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.
	## If <math>l -</math>sum<math> > p.n</math>:		## If <math>l - </math>sum<math> > p.n</math>:
	### Set <math>m:=l -</math>sum<math> - p.n + 1</math>.		### Set <math>m:=l -</math> sum <math> - p.n + 1</math>.
	### Set <math>p:=p'</math>.		### Set <math>p:=p'</math>.
	## Otherwise, set <math>m:=l -</math>sum<math>+ 1</math>.		## Otherwise, set <math>m:=l -</math>sum<math>+ 1</math>.