Array: Part-two

Posted by
Continue from Array : Part-one

INSERT

Insertion refers to insert a new element at given index.To insert a new element  We can shift elements from given index to last index one position forward and then update value at given index.Here we will  Break the process into two parts

  1. Shifting
  2. Update

Shifting:

Example-4->  Consider following  Array with size of ten  elements in which five elements already added we will represent it with  N = 5, now let’s insert new element 100 at index 2.

Notice that we need to insert new element at index 2 so shifting index must be greater than or equal to 2 but less than N.i.e. 2<=shifting Index<N ,starting from last index and it will increase number of elements in Array by one. Let’s take a variable shiftingIndex and set it to last index.

i.e  shiftingIndex  = N -1   = 4.

now perform following two operations until required condition is true.

  1. Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ]
  2. shiftingIndex   =  shiftingIndex  – 1
  • At shiftingIndex  = 4
    • Array shiftingIndex  +  1  = Array [ shiftingIndex  ] = Array [ 5 ] = Array [ 4 ]
    • shiftingIndex  = shiftingIndex  – 1 = 3
  • At shiftingIndex  = 3
    • Array shiftingIndex  +  1   =  Array [ shiftingIndex  ] =  Array [ 4 ] = Array [ 3 ]
    • shiftingIndex  = shiftingIndex  – 1 = 2
  • At shiftingIndex  = 2
    • Array shiftingIndex  +  1   =  Array [ shiftingIndex  ] = Array[ 3 ] = Array [ 2 ]
    • shiftingIndex  = shiftingIndex  – 1 = 1
  • Now required condition 2<=shifting Index<N becomes false and we stop here further shifting.

Update

Now perform update operation at given index with new value

i.e set Array[2] = 100  , so finally array will look like


Algorithm

  1. T = total elements in array
  2. N = number of elements already added.
  3. index = where new value to be inserted.
  4. shiftingIndex = index of element currently considering for shifting.
  5. newValue  = value to be inserted.
  6. Set shiftingIndex = N-1.
  7. while ( shiftingIndex >=index ) repeat step 8 to 9.
  8. Array [ shiftingIndex  + 1 ] = Array [ shiftingIndex ].
  9. shiftingIndex = shiftingIndex – 1.
  10. Array  [index ] = newValue.
  11. N = N + 1
  12. Exit.

DELETE

Delete operation removes element from array at given index. So to delete an element from array we can shift elements from next to given index to last index one position backward and then remove reference of last element.

Example-5-> Consider Array

Let’s delete item 45 at index 1.Shift all elements from index 2 to 4 one position backward. Keep reference of current shifting which satisfy the condition  1<= Index<N-1. and perform following two operations at each step.

  1. Array [ index ] = Array [ index + 1 ]
  2. index = index + 1
  • At index = 1
    • Array [ 1 ] = Array [ 2 ]
    • index = index + 1 = 2
  • At index = 2
    • Array [ 2 ] = Array [ 3 ]
    • index = index + 1 = 3
  • At index = 3
    • Array [ 3 ] = Array [ 4 ]
    • index = index + 1 = 4
  • At index = 4 , required condition false thus we set memory reference in index = 4 null ( indication item not exits ). and decrease number of elements from array set N = N – 1.
    • Array [ 4 ] = null
    • N =  N – 1 

Algorithm

  1.  N = number of elements in array
  2. index = position of element to be deleted.
  3. while ( index < N – 1 ) repeat step 4 to 5.
  4. Array [ index ] = Array [ index + 1 ].
  5. index = index + 1
  6. Array [ index ] = null.
  7. N = N – 1.
  8. Exit.

SEARCH

Searching has many applications like to check an element exist or not in a collection, find the place of element in a collection etc.

Here we will see how to get position on an element if it exist in collection otherwise we will set it to -1 or ‘not found’ something like that to indicate absence of element.

Example-6-> Consider Array

Let’s find the position of element 2 which exits at index 3.Compare each element from starting until we not find an element which is equal to element to be searched,if find such element we simply return current index otherwise return -1. perform following three operation, at initially index = 0.

  1.  temp = Array  [ index ]
  2. compare temp and given element
  3. index = index + 1
  • At index = 0
    • temp = Array [ 0 ] = 78
    • now 78 not equal to 2
    • index = index + 1 = 1
  • At index = 1
    • temp = Array [ 1 ] = 65
    • now 65 not equal to 2
    • index = index + 1 = 2
  • At index = 2
    • temp = Array [ 2 ] = 65
    • now 65 not equal to 2
    • index = index + 1 = 3
  • At index = 3
    • temp = Array [ 3 ] = 2
    • now 2  equal to 2, so we return index 3 and exit.

Algorithm

  1. N = number of elements in array.
  2. element = element to be searched.
  3. temp = element at current observing index
  4. Set index = 0
  5. while ( index < N ) repeat step 5 to 9
  6. temp = Array [ index ].
  7. if temp == element.
  8. return index.
  9. index = index + 1.
  10. return -1
  11. Exit.

 

Leave a Reply