Ex_2_1_07.md

title	date	draft	tags	categories
Algorithm4 Java Solution 2.1.07	2019-08-30 23:38:31 +0800	false	JAVA	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