This is conceptually easy.
Suppose that we have an array of size 10, and it currently only holds 4 integers.
Also assume that these are in sorted order. For example,
Array: 17 26 45 65 Position: 0 1 2 3 4 5 6 7 8 9
Now insert 33 (in order). The result is, of course
Array: 17 26 33 45 65 Position: 0 1 2 3 4 5 6 7 8 9
The 45 and 65 each were first moved one position to the right.
Then the 33 could be inserted at the free position
An array of existing values can be sorted using the insertion idea.
Consider an array of size 10 that already has 5 integers values stored, but is not sorted in order:
Array: 65 26 17 45 33 Position: 0 1 2 3 4 5 6 7 8 9
We can think of this array as consisting of two parts:
Initially, the sorted part is just the single value at position 0 and the remaining values are unexamined.
Array: 65 26 17 45 33 Position: 0 1 2 3 4 5 6 7 8 9
Now insert the first integer in the unexamined part in order into the first part.
Array: 65 26 17 45 33 Position: 0 1 2 3 4 5 6 7 8 9
The value 26 is smaller than 65, so 65 needs to be moved to the right.
But if we do this the wrong way we get
Array: 65 65 17 45 33 Position: 0 1 2 3 4 5 6 7 8 9
That is, the 26 that we are trying to insert is overwritten.
This can still work, but we need to have a temporary place to hold the value 26 until we can insert it.
Using a temp integer variable to hold the next value being inserted into the first part, 26 can be inserted like this:
tmp: -
Array: 65 26 17 45 33
Position: 0 1 2 3 4 5 6 7 8 9
tmp: 26
Array: 65 - 17 45 33
Position: 0 1 2 3 4 5 6 7 8 9
tmp: 26
Array: - 65 17 45 33
Position: 0 1 2 3 4 5 6 7 8 9
tmp: -
Array: 26 65 17 45 33
Position: 0 1 2 3 4 5 6 7 8 9
The next number to be inserted is the first one from the second unexamined part, 17:
tmp: -
Array: 26 65 17 45 33
Position: 0 1 2 3 4 5 6 7 8 9
The steps to insert 17 into the first sorted part are:
tmp: 17
Array: 26 65 - 45 33
Position: 0 1 2 3 4 5 6 7 8 9
tmp: -
Array: 17 26 65 45 33
Position: 0 1 2 3 4 5 6 7 8 9
How many insertions are required in Insertion Sort for an array with 5 integers?
The first integer doesn't have to be inserted into part 1; it's already there and part 2 consists of the remaining 5 - 1 integers.
So the answer is 5 - 1 = 4.
In general we will have to do n - 1 insertions to sort an array of n integers using the Insertion Sort algorithm.
For the array
Array: 22 8 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9
What would the array look like after the first insertion?
What would it look like after the second insertion?
What would it look like after the third insertion?
Answer:
Original array Array: 22 8 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9 After one iteration of inserting: Array: 8 22 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9 After two insertions Array: 8 22 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9 After three insertions Array: 8 10 22 35 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9
To translate the insertion and insertion sort into Java, let's first look at a single insertion in order.
That is, let's write a method, insert:
public static void insert(int[] arr, int cnt, int x)
Parameters
arr: an array of sorted integers
cnt: the number of integers stored in arr
x: a new integer to be inserted into arr in order
Description
The insert method should use the insertion method to insert x at
the proper place in the array arr so the at the result is still in
sorted order.
Precondition: The array arr should be large enought to hold one
more integer. That is, arr.length should be > cnt.
To insert another integer, x, into an array in order will usually require moving some of the values previously inserted.
An exception is the very first insertion.
Which items have to be moved? The ones greater than x.
How far does each of these have to be moved? Just to the next higher index.
The last element can be moved to the next higher index since that array position is not yet used.
Then we can move the next to last element, and so on, until we have moved all the elements bigger than x.
Here are some examples of inserting one element into a sorted array.
In each case a variable k is initialized to be the index of the last element in the sorted array.
Then the array element is moved over and k is decremented until the correct place is found for the insertion of the new value.
Round 0 inserting 26
Array: - - - - - - - -
Position: -1 0
k
Array: 26 - - - - - - -
Position: -1 0
k
26 inserted at position k + 1 = 0
Inserting 45
Array: 26 - - - - - - -
Position: -1 0 1
k
>
Array: 26 45 - - - - - -
Position: -1 0 1
k
45 inserted at position k + 1 = 1
A few more examples:
>
Inserting 17
Array: 26 45 - - - - - -
Position: -1 0 1 2
k
>
Array: 26 - 45 - - - - -
Position: -1 0 1 2
k
>
Array: - 26 45 - - - - -
Position: -1 0 1 2
k
>
Array: 17 26 45 - - - - -
Position: -1 0 1 2
k
17 inserted at position k + 1 = 0
Last insertion example:
Inserting 33
Array: 17 26 45 - - - - - -
Position: -1 0 1 2 3
k
Array: 17 26 - 45 - - - - -
Position: -1 0 1 2 3
k
Array: 17 26 33 45 - - - - -
Position: -1 0 1 2 3
k
33 inserted at position k + 1 = 2
public static void insert(int[] arr, int cnt, int x)
From the examples, we can note the following details for inserting x into arr:
(Note that initially, cnt = 0, so k would be -1 in this case.)
1 public static void insert(int[] arr, int cnt, int x)
2 {
3 if ( cnt >= arr.length ) {
4 throw new IllegalArgumentException();
5 }
6
7 int k = cnt - 1;
8 while( k >= 0 && arr[k] > x ) {
9 arr[k+1] = arr[k];
10 k--;
11 }
12 arr[k+1] = x;
13 }
Lines 3 - 5: Handle the precondition; there should be enough room in
the array for another element.
Line 7: Initialize k to be the position of the current last element
Line 8: Make sure k is not -1 before comparing x to arr[k]. If k is
-1, then this check will exit the loop and x will be inserted in
arr[k+1], that is, at arr[0]. If k is not -1, but x > arr[k], then
x should also be inserted in arr[k+1].
Line 9 - 10: If k is a valid index (k not -1) and x < arr[k], then
lines 9 - 10 move arr[k] to the "right" one position and decrement k.
Using the insert method above we can easily implement the Insertion Sorting algorithm to sort an array.
1 public static void insertionSort(int[] arr, int cnt)
2 {
3 for(int i = 1; i < cnt; i++) {
4 insert(arr, i, arr[i]);
5 }
6 }
Line 3: The for loop starts with i = 1. This is because considering
just 1 element at position 0, that part of the array is "sorted". To
sort the array, we must insert the remaining cnt - 1
elements. The loop executes cnt - 1 times, each time
inserting one more element into its proper sorted position.
Line 4: At this call, the first i elements of arr are already
sorted. They are in positions 0 to i-1. So the next item from the
second part of the array to be inserted is arr[i].
1 public static void insertionSort(int[] arr, int cnt)
2 {
3 for(int i = 1; i < cnt; i++) {
4 insert(arr, i, arr[i]);
5 }
6 }
To sort an entire array it isn't necessary to have the separate insert method which only inserts one item.
The call to insert at line 4 can be replaced by the code for insert with some minor modifications.
Here is the insert code:
1 public static void insert(int[] arr, int cnt, int x)
2 {
3 if ( cnt >= arr.length ) {
4 throw new IllegalArgumentException();
5 }
6
7 int k = cnt - 1;
8 while( k >= 0 && arr[k] > x ) {
9 arr[k+1] = arr[k];
10 k--;
11 }
12 arr[k+1] = x;
13
14 }
The call to insert in insertionSort passes i and i is < the number of elements in the array so the precondition check at lines 3 to 5 is not necessary.
The parameter x to insert is just arr[i].
So replacing parameter x by declaring it as a local variable x by setting it to arr[i] and removing the precondition check, we can replace the call to insert with the code from insert:
1 public static void insertionSort(int[] arr, int cnt)
2 {
3 for(int i = 1; i < cnt; i++) {
4 / * insert(arr, i, arr[i]); */
5 int x = arr[i];
6 int k = cnt - 1;
7 while( k >= 0 && arr[k] > x ) {
8 arr[k+1] = arr[k];
9 k--;
10 }
11 arr[k+1] = x;
12 }
13 }
We could also rewrite the inner while loop that does a single insertion using an equivalent for loop.
1 public static void insertionSort(int[] arr, int cnt)
2 {
3 for(int i = 1; i < cnt; i++) {
4 / * insert(arr, i, arr[i]); */
5 int x = arr[i];
6 for(int k = cnt - 1; k >= 0 && arr[k] > x; k--) {
7 arr[k+1] = arr[k];
8 }
9 arr[k+1] = x;
10 }
11 }
Bubble sort makes several passes over the elements of an array.
On each pass, bubble sort compares adjacent pairs of elements and swaps them if they are out of order from the first pair to the last pair.
On the first pass this results in the largest value being in the last array position.
So after the first pass, the largest value is in its correct sorted position and will be ignored from now on.
On each subsequent pass, bubble sort considers 1 fewer elements, ignoring the last one from the previous pass since it will also be in its correct sorted position.
After n-1 passes the array is sorted where n is the number of elements in the array.
An essential, but simple ingredient in bubble sort and several other sorting algorithms is the code to swap two elements.
A third temporary variable is needed to swap the values of two integers.
(A red glass contains regular milk; a blue glass, skim milk. How would you swap the contents of the two glasses?)
This code does not swap x and y.
int x = 5;
int y = 10;
x = y; // Now x and y are both 10
y = x; // The are both still 10
A correct way of swapping x and y using a temporary:
int x = 5; int y = 10; int tmp = x; // save x's value in tmp x = y; // Now x and y are both 10, but tmp is still 5 y = tmp; // x is 10 and y is 5
Here is code for one pass where k is the number of elements still being considered. The array elements at positions k, k+1, ... would already be in their correct sorted positions.
1 public static void pass(int[] a, int k)
2 {
3 for(int i = 0; i < k; i++) {
4 if ( a[i] > a[i+1] ) {
5 int tmp = a[i];
6 a[i] = a[i+1];
7 a[i+1] = tmp;
8 }
9 }
10 }
The code for one pass is not enough to sort an array; it only puts the largest value in the last position.
Here is bubble sort using the pass method:
1 public static void bubbleSort(int[] a, int cnt)
2 {
3 for(k = cnt; k > 1; k--) {
4 pass(a, k);
5 }
6 }
On the first call to pass, k is the number of elements stored in the array and pass will make one pass resulting in the largest value being put in possition the last position, a[k-1].
On each call to pass the number of elements decreases and the next largest value is put it its proper place.
If the number of elements considered in a pass is at least 2, there is something to do, but if the number of elements is just 1, then that element is already in its proper place.
So only cnt - 1 passes are needed (k = cnt, cnt - 1, ..., 2).
Just as for insertion sort, we can replace the call to pass with the actual code.
Doing so results in the usual code for bubble sort:
1 public static void bubbleSort(int[] a, int cnt)
2 {
3 for(k = cnt; k > 1; k--) {
4 / * pass(a, k); */
5 for(int i = 0; i < k; i++) {
6 if ( a[i] > a[i+1] ) {
7 int tmp = a[i];
8 a[i] = a[i+1];
9 a[i+1] = tmp;
10 }
11 }
12 }
13 }
For the array
Array: 22 8 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9
What would the array look like after the first pass?
What would it look like after the second pass?
What would it look like after the third pass?
Answer:
Original array Array: 22 8 35 10 19 23 16 Position: 0 1 2 3 4 5 6 7 8 9 After one pass: Array: 8 22 10 19 23 16 35 Position: 0 1 2 3 4 5 6 7 8 9 After two passes Array: 8 10 19 22 16 23 35 Position: 0 1 2 3 4 5 6 7 8 9 After three passes Array: 8 10 19 16 22 23 35 Position: 0 1 2 3 4 5 6 7 8 9
Insertion sort is not the fastest sorting algorithm, but it generally performs a bit better than bubble sort and a lot better if the array is nearly sorted.
One problem with bubble sort is all the swapping.
Minimum Selection Sort works somewhat similarly to bubble sort, but avoids doing so many swaps.
A key idea is to keep track of the position of the minimum value found on one pass, but only swap when all the elements for that pass have been examined.
That is, the key idea is that if you know the position of the minimum value in an array, you can get the minimum value, but not conversely. So you have more information if you know the minimum value's position.
On the first pass, minimum selection sort finds the position of the minimum value stored in the array.
Then, and only then, does minimum selection sort swap the value at this position with the value at position 0.
Now position 0 can be ignored. The correct smallest value is in its proper place.
On each pass, the position of the minimum value out of values not already placed is found.
If the k smallest values have already been placed, they will be at positions 0, 1, ... k-1.
So the next smallest value should go at position k.
For the array
Array: 22 23 35 19 10 8 16 Position: 0 1 2 3 4 5 6 7 8 9
What would the array look like after the first pass?
What would it look like after the second pass?
What would it look like after the third pass?
Answer:
The highlighted pair in each pass corresponds to the only swap in the pass.
Original array Array: 22 23 35 19 10 8 16 Position: 0 1 2 3 4 5 6 7 8 9 After one pass: Array: 8 23 35 19 10 22 16 Position: 0 1 2 3 4 5 6 7 8 9 After two passes Array: 8 10 35 19 23 22 Position: 0 1 2 3 4 5 6 7 8 9 After three passes Array: 8 10 19 35 23 22 Position: 0 1 2 3 4 5 6 7 8 9
Here is the code for minimum selection sort:
1 public static void minSelectionSort(int[] arr, int cnt)
2 {
3 for(int k = 0; k < cnt; k++) {
4 // Find minimum of a[k] ... a[cnt-1] and put it in a[k]
5 int minpos = k;
6 for(int i = k + 1; i < cnt; i++) {
7 if ( a[minpos] > a[i] ) {
8 minpos = i;
9 }
10 }
11 // Now swap once
12 int tmp = a[minpos];
13 a[minpos] = a[k];
14 a[k] = tmp;
15 }
Sorting arrays of Strings can use any of the sorting algorithms just discussed, except that comparisons must be done differently.
Instead of using the relational operators <, <=, etc. for integers, you must use the String method:
public int compareTo(String other)
String x, y;
x.compareTo(y) is < 0 if x comes before (is smaller than) y as Strings
x.compareTo(y) is 0 if x and y are equal as Strings
x.compareTo(y) is > 0 if x comes after (is bigger than) y as Strings
Also if swapping is required, the temporary variable should be of String type, not int.
If a class type has a compareTo method like that of String, then it determines an order on the instances of the class and the same code can be used to sort an array of that class type using that class's compareTo method.
This example uses maximum selection sort (instead of min selection sort).
Each pass of Max Selection Sort finds the position of the maximum value in the n items considered on that pass and then swaps the values at maxpos and n - 1, where the maximum belongs.
Then n is decremented and the process repeats until n is 1 and there is nothing left to do.
The String array used here is the array of strings passed on the command line.
1
2 public static void sort(String[] a, int cnt)
3 {
4 for(int n = cnt; n > 1; n--) {
5 int maxpos = 0;
6 for(int i = 1; i < n; i++) {
7 if ( a[i].compareTo(a[maxpos]) > 0 ) {
8 maxpos = i;
9 }
10 }
11 String tmp = a[maxpos];
12 a[maxpos] = a[n-1];
13 a[n-1] = tmp;
14 }
15 }
16
17 public static void main(String[] args)
18 {
19 sort(args, args.length);
20 for(int i = 0; i < args.length; i++) {
21 System.out.println(args[i]);
22 }
23 }
>java sortStrings bob betty fred dino bam-bam bam-bam betty bob dino fred
See the program 2 description on the hw page.