Describe an algorithm finding the second largest integer in

Describe an algorithm.

finding the second largest integer in a sequence of distinct integers.

Find a big-O estimate of the number of comparison used by the algorithm.

Solution

Selection sort: In this technique, the first element is selected and compared with all other elements. If any other element is greater than the first element swapping should take place.By the end of this comparison, the greatest element most top position in the array. This is known as pass1. In pass II, the second element is selected and compared with all other elements. Swapping takes place if any other element is greater than selected element. This process continuous until array is sorted.

using Selection sort, in second pass we will get the second largest integer in a sequence of distinct integer.

for finding big-O estimate,

let suppose the no of distinct integer be =n

then in first pass,

no of comparision is=n-1

in second pass,

no of comparision is=n-2

so the big-O estimate is O(n²)