When we analyze the performance of the sorting algorithm, we interest primarily on the number of comparison and exchange.

Let E_{n} be the total average number of exchange to sort array of N element. E_{1} = 0 (we do not need any exchange for array with one element). The average number of exchange to sort N element array is the sum of average number of number of exchange to sort N-1 element array with the average exchange to insert the last element into N-1 element array.

Simplify the summation (arithmetic series)

Expands the term

Simplify the summation again (arithmetic series)

Let C_{n} be the total average number of comparison to sort array of N element. C_{1} = 0 (we do not need any comparison on one element array). The average number of comparison to sort N element array is the sum of average number of number of comparison to sort N-1 element array with the average comparison to insert the last element into N-1 element array. If last element is largest element, we need only one comparison, if the last element is the second smallest element, we need N-1 comparison. However, if last element is the smallest element, we do not need N comparison. We still only need N-1 comparison. That is why we remove 1/N in below equation.

Simplify the summation (arithmetic series)

Expand the term

Simplify the summation again (arithmetic series and harmonic number)

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow