Ex_2_1_07.md

title	Algorithm4 Java Solution 2.1.07
date	2019-08-30 23:38:31 +0800
draft	false
tags	JAVA
categories	TECH archives

2.1.07

Problem:

Which method runs faster for an array in reverse order, selection sort or inser- tion sort?

Solution：

we count array access times.

for selection sort: N^2

for insertion sort: (4+2)*N^2 = 3N^2

so, insertion sort is roughly 3 times slower than selection, when input is reverse order array.

code:

Ex_2_1_07.java