Some correction for Insertion Sort

[Haidong (Haydon) Xue]

Hi all,

1. The insertion sort I implemented in the class is not the same as the one in textbook, and the one in textbook is more efficient. 

When doing the insertion, the standard one (the one in textbook) uses a constant (1) extra memory to record the current element, and only moves the elements in the sorted array instead of exchanging. 

Also, in my implementation, the first swap can be removed since the current element will always at the position right after the tail sorted array.

I have just implemented the textbook one (InsertionSort_Textbook_Haydon.java), and improved the one I implemented in class (InsertionSort_Haydon.java). They are all posted on our class website, please check. You will see that the one from textbook has the same comparisons as the one I implemented in class but less moves. 

I also updated Sort.java and SortingTester.java to more specifically record the number of moves ( one exchange is equal to 3 moves). 

It is very helpful for you to run the SortingTester.java and study all the code. 

2. In the quizzes or tests of this class, both the insertion methods are considered as correct. However, in other situation, when you are asked what the Insertion Sort is, please answer the one from textbook because is the standard one and more efficient.  

If you have any further questions, please let me know.

--
Haidong(Haydon) Xue
Ph.D Candidate
Research Assistant, Teaching Instructor
Department of Computer Science
Georgia State University

http://www.cs.gsu.edu/~hxue1