Move Maximum

tags: linear-scan adjacent-comparison swap

Move the maximum element to the last location in the input array.

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

def move_max(a)
  n = a.size
  
  for i in (0..n-2)
    if a[i] > a[i+1]
      a[i], a[i+1] = a[i+1], a[i]
    end
  end
end

a = [4,3,2,9,2,0]
move_max(a)

p a[a.size-1]

A common mistake is going out of bounds when scanning the linear array. The upper bound for the index is NOT the last element but the element before the last element.

An alternative way is to compare the value of the current element with the preceding value.

1
2
3
4
5
6
7
8
9

def move_max(a)
  n = a.size
  
  for i in (1..n-1)
    if a[i-1] > a[i]
      a[i-1], a[i] = a[i], a[i-1]
    end
  end
end

In this case the upper bound stops at the last element. But the initial value of the index starts from 1.