Selection Sort
Algorithm description
Selection sort is a sorting algorithm that is simple to describe. Let’s start with an array of n numbers. Goal: Sort the elements in increasing order.
1. Scan the array to find the smallest element in the array. Move it to the first position by swapping it with the element that is already in the first position.
2. Then move on to the second element of the array. Scan the array for the smallest remaining element. Swap it with the element in the second position.
3. Repeat this process for each element of the array out to the (n–1)st element.
4. Now the largest element will be in the last position in the array.
Consider this example.
3 / 1 / 4 / 5 / 9 / 2 / ® / 1 / 3 / 4 / 5 / 9 / 2 / ® / 1 / 2 / 4 / 5 / 9 / 31 / 2 / 3 / 5 / 9 / 4 / ® / 1 / 2 / 3 / 4 / 9 / 5 / ® / 1 / 2 / 3 / 4 / 5 / 9
Pseudocode for ints stored in an array named a (array is kept sorted up to position j)
for i = 1 to length(a) - 1
{
k = j such that a[j] < a[i], j = i to n
swap(a[i], a[k]);
} //go get next one
Real code
package selection;
/**
* This class sorts an array, using the selection-sort algorithm
* @author Cay Horstmann
*/
public class SelectionSorter {
private int[] a;
/**
* Constructs a selection sorter
* @param anArray -- the array to sort
*/
public SelectionSorter(int[] anArray) {
a = anArray;
}
/**
* Sorts the array managed by this selection sorter
*/
public void sort() {
for (int i = 0; i < a.length - 1; i++) {
int minPos = minimumPosition(i);
swap(minPos, i);
}
}
/**
* Finds the samllest element in a tail range of the array
* @param from -- the first person in a to compare
* @return -- the position of the samllest element in the
* range a[from] ... a[a.length-1]
*/
private int minimumPosition(int from) {
int minPos = from;
for (int i = from + 1; i < a.length; i++)
if (a[i] < a[minPos]) minPos = i;
return minPos;
}
/**
* Swaps two entries of the array
* @param i -- the first position to swap
* @param j -- the second position to swap
*/
private void swap(int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Running time
The running time of selection sort rises rapidly as the number of elements increases. It rises proportionally to the square of the number of elements.
The following table is given in the text. What trend would you expect in ms./element? ms./element2?
n / ms. / ms./elt. / n2 / ms/elt.210000 / 772 / 0.0772 / 1E+08 / 7.72E-06
20000 / 3051 / 0.1523 / 4E+08 / 7.63E-06
30000 / 6846 / 0.2282 / 9E+08 / 7.61E-06
40000 / 12188 / 0.3047 / 1.6E+09 / 7.62E-06
50000 / 19015 / 0.3803 / 2.5E+09 / 7.61E-06
60000 / 27359 / 0.4559 / 3.6E+09 / 7.60E-06
In §19.3, Horstmann goes through an analysis to show that the running time is proportional to n2. There is an easier way to see that.
3 / 1 / 4 / 5 / 9 / 2 / ® / 1 / 3 / 4 / 5 / 9 / 2 / ® / 1 / 2 / 4 / 5 / 9 / 31 / 2 / 3 / 5 / 9 / 4 / ® / 1 / 2 / 3 / 4 / 9 / 5 / ® / 1 / 2 / 3 / 4 / 5 / 9
How many times did we look for the smallest element in the rest of the array?
n–1
In looking for the smallest element, how many items did we need to examine?
6, 5, 4, 3, and 2. On average n/2.
So, how many times did we have to look at an element? (n–1)×n/2 ~= n2/2.
The amount of work rises proportional to
Insertion Sort
Algorithm description
Insertion sort is an efficient algorithm for sorting small lists. One way to understand sort is to think about how someone might sort a hand of cards.
Start with all the cards on the table. Goal: Sort n cards by number with smallest to the left and largest to the right.
1. Pick up a card from the table if one exists.
2. Scan cards already in your hand from right to left looking for one smaller than the one you just picked up.
3. If you find one smaller then insert the new card after it (to its right) ; otherwise insert it as the leftmost card.
4. Go to step 1.
Pseudocode for ints stored in an array named a (array is kept sorted up to position j)
for j = 1 to length(a) - 1
{
key = a[j]
i = j - 1
while (i >=0 and a[i] > key ) {
a[i+1] = a[i]
i--
}
a[i+1] = key
} //go get next one
Real code — Iterative
public static void main(String[] args) {
int[] A = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int key;
for (int j = 1; j < 10 ; j++) {
key = A[j];
int i = j - 1;
while ((i >=0 ) & (A[i] > key)) {
A[i+1] = A[i];
i--;
}
A[i+1] = key;
//display array each time j moves over one position
for (i = 0; i < 10; i++)
System.out.print(A[i]+" ");
System.out.println();
}
}
}
Output:
8 9 7 6 5 4 3 2 1 0
7 8 9 6 5 4 3 2 1 0
6 7 8 9 5 4 3 2 1 0
5 6 7 8 9 4 3 2 1 0
4 5 6 7 8 9 3 2 1 0
3 4 5 6 7 8 9 2 1 0
2 3 4 5 6 7 8 9 1 0
1 2 3 4 5 6 7 8 9 0
0 1 2 3 4 5 6 7 8 9
Recursive algorithms
The recursive algorithms provided with these notes were developed by Dr. Matt Stallmann. They recognize that all of the sorting algorithms are closely related.
Both insertion and selection rely on decomposing the list into a single item and the rest ("tail") of the list.
For the insertion sort, the list is decomposed into "first" and "all but first."
Applying this decomposition of the list recursively, we reach a list of a one item.
"Backing up" through the recursion, we recursively insert each "first" item into a growing sublist until a complete, sorted list is reached.
Recursive code
The code uses the List and Node classes discussed in the text and in lecture.
Insertion sort: Easy decomposition of input. No need to do "shifting"—just unlink and insert, e.g.
The pertinent Java code follows.
Note: The code is written so that all nodes are reused and no new nodes are created.
// Implementation of insertion sort for linked lists
// written 4/9/97 by Matt Stallmann, Java translation 11/30/06 by
// Ed Gehringer
(in class Node)
public Node insert(Node n) {
// PRE: n!=null & n.next==null & this is sorted in ascending order
// POST: retval == the nodes of n and this rearranged so that
// the node’s data are in ascending order
Node retval = null;
if ((Integer) n.data <= (Integer) data) { // Node n goes at
n.next = this; // beginning of list
retval = n; // Return p, which is now at start of list
}
else if (next == null) { // End of list reached,
next = n; // so n must go at end of list.
retval = this; // Return pointer to original list, since the
} // same node is still at head of list.
else { // Pass the insert request on to tail of list.
next = next.insert(n); // next now points to the tail
retval = this; // of the list, with n inserted at the
} // proper place.
return retval;
}
public Node sort() {
Node retval = null;
if (next == null) retval = this; // If only one node,
// list is already sorted.
else {
Node tail = unlink(); // tail = all of list but head node.
retval = tail.sort().insert(this); // Sort tail
} // of list and then insert this node in proper place.
return retval;
}
public Node unlink() {
// Lop front node off of list and return ptr. to tail of list
Node retval = next;
next = null;
return retval;
}
(in class LinkedList)
public void insertionSort() {
if (first == null) return;
head = first.sort();
}
Example: Suppose we want to sort this list:
These operations are performed:
Matthias Stallmann() Update by Edward F. Gehringer.
Lecture 25 Programming Concepts—Java XXX