CODEWITHSUNDEEP
algorithmdiscrete-mathematics
boastar
boastar

Reputation: 1

interpret this algorithm of discrete mathematics and its applications, Kenneth H. Rosen

Q. Describe an algorithm that inserts an integer x in the appropriate position into the list a_1, a_2, ... ,a_n of integers that are in increasing order.

A. 

procedure insert(x,a_1,a_2,...,a_n :integers)
{the list is in order: a_1<=a_2<=...<=a_n}
a_(n+1) := x+1
i :=1
while x>a_i
i :=i+1
for j:=0 to n-i
a_(n-j+1) := a_(n-j)
a_i=x
{x has been inserted into correct position}

my question. why a_(n+1) := x+1 ? and if the initial value i=n then j=0 to -1 ? do i exclude j=-1? sorry for bad speaking please interpret this algorithm

Upvotes: 0

Views: 672

Answers (1)

MBo
MBo

Reputation: 80277

why a_(n+1) := x+1 ?

This is sentinel node approach.

Using this stop-element, one can use the same method for inserting x into any position of the list. Otherwise one have to look for whether list is finished and append x at the end with special piece of code

if the initial value i=n then j=0 to -1 ?

It is implied that operator for for j:=0 to -1 is not executed (some languages have special kinds of for loop for reverse direction like for ..downto in Pascal or step argument in some others)

Upvotes: 1

Related Questions