Array Basics

excerpt: Find, Minimum, Maximum, Average, Median, Insert and Remove tags: linear-scan value-comparison pairwise-comparison

In an unsorted array, finding an item requires performing a linear search or exhautive search. Look at every element in the array until the target item is either found or conclude that it is not in the array.

Finding Items

The index method searches for the target item by searching through all the elements in the array, it returns the index of the target if it is found otherwise, it returns -1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def index(array, target)
  for i in (0...array.size)
    if array[i] == target
      return i
    end  
  end
  
  return -1
end

input = [3,5,2,8,9,1]

p index(input, 1)

In the worst case, the target item may be the last item in the array. The time complexity is O(N). The wors case also occurs if the target item is not in the array.

Minimum, Maximum and Average

Calculating the minimum, maximum and average requires us to traverse the entire array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def minimum(array)
  min = array[0]
  
  for i in (1...array.size)
    if array[i] < min
      min = array[i]
    end
  end
  
  return min
end

input = [3,5,2,8,9,1]
p minimum(input)

Calculating the maximum in an array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def maximum(array)
  max = array[0]
  
  for i in (1...array.size)
    if array[i] > max
      max = array[i]
    end
  end
  
  return max
end

input = [3,5,2,8,9,1]
p maximum(input)

Caculcating the average in an array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def average(array)
  n = array.size
  sum = 0
  
  for i in (0...n)
    sum += array[i]
  end
  
  return sum/(n*1.0)
end

input = [3,5,2,8,9,1]
p average(input)

The length of the array is multipled by 1.0 to prevent rounding errors.

Median

The median is the value that lies in the middle of the values when the array is sorted. For example, the median of 1,3,4,7,8,8,9 is 7 because there three smaller values (1,3,4) and three larger values (8,8,9).

A single pass through the array does not give us all the information we need to calculate the median, because we need more global information about the values to find the median.

One approach is to think about each value in the list. For each test value, reconsider all the values and keep track of those that are larger and smaller than the test value. If a test value is found to have equal number of smaller and larger entries, the test value is the median.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def median(array)
  for i in (0..array.size - 1)
    larger = 0
    smaller = 0
    
    for j in (0..array.size - 1)
      if array[j] < array[i]
        smaller = smaller + 1
      end
      if array[j] > array[i]
        larger = larger + 1
      end
    end
    
    if smaller == larger
      return array[i]
    end
  end
end

input = [1,3,4,7,8,8,9]
p median(input) 

This implementation does not handle the case in which multiple items have the same value, as in 1,2,3,3,4. It also does not handle arrays with an even number of items, which have no item in the middle. If an array has an even number of items, its median is defined as the average of the two middlemost items. For example, the median of 1,4,6,9 is 4+6/2 = 5. The time complexity is quadratic.

A much faster algorithm is to first sort the array and then find the median directly by looking at the values in the sorted array. Sorting takes O(n log n) time which is a lot faster than quadratic time.

Inserting Elements

Inserting an element at the end of an array is easy if the programming language can extend the array by one item. Inserting an element anywhere else is not easy. The insert method inserts a new item at location position in an array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def insert(array, position, value)
  # Resize the array to add 1 item at the end
  array << array.last
  
  # Move down the items after the target position
  # to make room for the new element
  (array.size-1).downto(position+1) do |i|
    array[i] = array[i-1]
  end
  
  # insert the new element
  array[position] = value
end

input = [3,5,2,8,9,1]

insert(input, 3, 20)
p input

The array size is increased by one by appending the last element to the end of the array. The elements that are after the position index are shifted once to the right and the new element is inserted in the index value of the position.

The loop starts at the end of the array and moves toward the beginning. The elements are copied to the next location that is on the right of its previous position. The loop executes n - position times where n is the size of the array. In the worst case, adding an item to the beginning of the array, position = 0, the loop executes n times, so the time complexity is O(N).

Inserting elements is not common, but the technique of shifting elements in an array to make room for a new one is useful in other algorithms.

Removing Items

The elements that come after the position k moves one position closer to the beginning of the array. The array is resized to remove the final unused entry.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def remove(array, position)
  n = array.size
  start = position + 1
  
  # from the position of the value to be deleted
  # shift elements to the left by one
  for i in (start...n)
    array[i-1] = array[i]
  end
  
  # discard the last unused element
  array.pop
end

input = [3,5,2,8,9,1]

remove(input, 3)
p input

In the worst case, removing the first item from the array, all the items must be moved in the array. In this case, the time complexity is O(N).