Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 5

1.1.1 Analysis of Selection Sort
To find the smallest of k items, we make k -1 comparisons. On the first pass, we make n -1 comparisons to find the
smallest of n items. On the second pass, we make n -2 comparisons to find the smallest of n -1 items. And so on, until
the last pass where we make one comparison to find the smaller of two items. In general, on the j th pass, we make n-j
comparisons to find the smallest of n-j +1 items. Hence, we have this:
total number of comparisons = 1 + 2 + …+ n -1 = ½ n ( n -1) » ½ n 2
We say selection sort is of order O( n 2 ) (“big O n squared”). The constant ½ is not important in “big O” notation
since, as n gets very big, the constant becomes insignificant.
On each pass, we swap two items using three assignments. Since we make n -1 passes, we make 3( n -1)
assignments in all. Using “big O” notation, we say that the number of assignments is O( n ). The constants 3 and 1 are
not important as n gets large.
Does selection sort perform any better if there is order in the data? No. One way to find out is to give it a sorted list
and see what it does. If you work through the algorithm, you will see that the method is oblivious to order in the data.
It will make the same number of comparisons every time, regardless of the data.
As we will see, some sorting methods (mergesort and quicksort; see Chapters 5 and 9) require extra array storage to
implement them. Note that selection sort is performed “in place” in the given array and does not require additional storage.
As an exercise, modify the programming code so that it counts the number of comparisons and assignments
made in sorting a list using selection sort.
1.2 Sorting an Array: Insertion Sort
Consider the same array as before:
Now, think of the numbers as cards on a table that are picked up one at a time in the order they appear in the
array. Thus, we first pick up 57 , then 48 , then 79 , and so on, until we pick up 52 . However, as we pick up each new
number, we add it to our hand in such a way that the numbers in our hand are all sorted.
When we pick up 57 , we have just one number in our hand. We consider one number to be sorted.
When we pick up 48 , we add it in front of 57 so our hand contains the following:
48 57
When we pick up 79 , we place it after 57 so our hand contains this:
48 57 79
When we pick up 65 , we place it after 57 so our hand contains this:
48 57 65 79
At this stage, four numbers have been picked up, and our hand contains them in sorted order.
When we pick up 15 , we place it before 48 so our hand contains this:
15 48 57 65 79
When we pick up 33 , we place it after 15 so our hand contains this:
15 33 48 57 65 79
Finally, when we pick up 52 , we place it after 48 so our hand contains this:
15 33 48 52 57 65 79