Section 9.5. Array Algorithms: Sorting

As is apparent from the pseudocode, we have a nested for loop. The outer ( k ) loop, iterates through the array from 1 to N - 1. The inner loop iterates as many times as necessary, starting with the element just to the left of the k th element in order to insert the k th element into its correct position in the sorted portion. Note that the k th element is always removed from the array (and stored in the variable x ), to make room for elements that have to be moved to the right.

To see how this works, consider an integer array containing the ages of five friends :

21    20  27  24  19    x = 20
       k

For this five-element array, insertion sort initially will assume that the element at index 0 is in the correct position. The vertical line marks the boundary between the sorted and unsorted portions of the array. The outer loop will look at each of the remaining elements, one at a time, inserting it into its proper position in the sorted portion of the array. To insert 20, the number at index 1, the inner loop will move 21 to the right by one position. To do this, the algorithm will copy 20 from its location and store it in x. It will then move 21 one space to the right. Finally, it will insert 20, which is stored in x, at index 0, where it belongs relative to the other elements in the sorted part of the array. At this point, the sorted portion of the array consists of the first two elements, which are in the correct order relative to each other.

20  21    27  24  19    x = 27
           k

For the next element, 27, none of the elements in the sorted portion need to be moved, so the inner for loop will iterate zero times. This gives us:

20  21  27    24  19     x = 24
               k

For the fourth element, 24, only the previous element, 27, needs to be moved to the right, giving:

20  21  24  27    19     x = 19
                   k

At this point, the sorted part of the array consists of the first four elements, which are in the correct order relative to each other. Finally, for the last element, 19, all of the elements in the sorted part of the array need to be moved one space to the right. This will require four iterations of the inner loop. We show the state of the array after each iteration of the inner for loop:

k
20 21 24 27  19   Remove 19 and store it x = 19
20 21 24 27  27   Move 27 to the right
20 21 24 24  27   Move 24 to the right
20 21 21 24  27   Move 21 to the right
20 20 21 24  27   Move 20 to the right
19 20 21 24 27    Insert x=19 at index 0

The fact that so many elements may have to move on each iteration of the outer loop shows that insertion sort is not a very efficient algorithm.

The Sort class (Fig. 9.13) provides an implementation of the insertionSort() method. There are several points worth noting about this code. First, because it takes an int array as a parameter, the insertionSort() method will sort any array of integers, regardless of the array's length.

Figure 9.13. Source code for the insertionSort() method. Note in main() how an integer array is passed to the method.

public class

Sort {

public void

insertionSort(

int

arr[]) {

int

temp;

// Temporary variable for insertion


for

(

int

k = 1; k < arr.length; k++)  {
      temp = arr[k];

// Remove element from array


int

i;

// For larger preceding elements


for

(i = k-1; i >= 0 && arr[i] > temp; i--)
        arr[i+1] = arr[i];

// Move it right by one

arr[i+1] = temp;

// Insert the element

}
  }

// insertionSort()


public void

print(

int

arr[]) {

for

(

int

k = 0; k < arr.length; k++)

// For each integer

System.out.print( arr[k] + "  \t  ");

// Print it

System.out.println();
  }

// print()


public static void

main(String args[]) {
    int intArr[] = { 21, 20, 27, 24, 19 };
    Sort sorter =

new

Sort();
    sorter.print(intArr);
    sorter.insertionSort(intArr);

// Passing an array

sorter.print(intArr);
  }

// main()

}

// Sort class

Second, note how empty brackets ( [] ) are used to declare an array parameter. If the brackets were omitted, then arr would be indistinguishable from an ordinary int parameter. Using the brackets indicates that this method takes an array of integers as its parameter.

Array parameters

Debugging Tip: Array Parameter

When declaring an array parameter, empty brackets must be used either after the array name or after the type name to distinguish it from a nonarray parameter.

Third, note how an array of integers is passed to the insertionSort() method in the main() method:

sorter.insertionSort(intArr);

// Pass intArr to the method

That is, when passing an array to a method, you use just the name of the array, without brackets. Both of the following statements would cause syntax errors:

sorter.insertionSort(intArr[]);

// Err: Can't have brackets

sorter.insertionSort(intArr[5]);

// Err: passing an integer

In the first case, empty brackets are only used when you declare an array variable, not when you are passing the array to a method. In the second case, intArr[5] is an int , not an array, and cannot legally be passed to insertionSort() .

Debugging Tip: Passing an Array Argument

It is a syntax error to use empty brackets when passing an array argument to a method, where only the array's name should be used. Empty brackets are only used when declaring an array variable.

Finally, within the insertionSort() method itself, note that we declare the index for the inner for loop outside of the for statement. This is so that it can be used outside the scope of the for loop to insert temp at location arr[i+1] , its correct location. Note also that the index of its correct location is i+1 , rather than just i . This is because the inner loop might iterate past location 0, which would give i a value of -1 at that point.

9.5.2. Selection Sort

There are a large variety of array-sorting algorithms. Selection sort is different from, but comparable to, insertion sort in its overall performance. To illustrate the selection sort algorithm, suppose you want to sort a deck of 25 index cards, numbered from 1 to 25. Lay the 25 cards out on a table, one card next to the other. Starting with the first card, look through the deck and find the smallest card, the number 1 card, and exchange it with the card in the first location. Then go through the deck again starting at the second card, find the next-smallest card, the number 2 card, and exchange it with the card in the second location. Repeat this process 24 times.

Selection sort algorithm

Translating this strategy into pseudocode gives the following algorithm:

Selection sort of a 25-card deck from small to large
1. For count assigned 1 to 24                      // Outer loop
2.   smallestCard = count
3.   For currentCard assigned count+1 to 25        // Inner loop
4.     If deck[currentCard] < deck[smallestCard]
5.        smallestCard = currentCard
6.   If smallestCard != count                      // You need to swap
7.      Swap deck[count] and deck[smallestCard]

For a deck of 25 cards, you need to repeat the outer loop 24 times. In other words, you must select the smallest card and insert it in its proper location 24 times. The inner loop takes care of finding the smallest remaining card.

On each iteration of this outer loop, the algorithm assumes that the card specified by the outer loop variable, count , is the smallest card (line 2). It usually won't be, of course, but we have to start somewhere.

The inner loop then iterates through the remaining cards (from count+1 to 25) and compares each one with the card that is currently the smallest (lines 4 and 5). Whenever it finds a card that is smaller than the smallest card, it designates it as the smallest card (line 5). At the end of the loop, the smallestCard variable will remember where the smallest card is in the deck.

Finally, when the inner loop is finished, the algorithm swaps the smallest card with the card in the location designated by count .

9.5.3. Algorithm: Swapping Memory Elements

An important feature of the selection sort algorithm is its need to swap two array elements, or cards, to continue our example. Swapping two memory elements, whether they are array elements or not, requires the use of a temporary variable. For example, to swap the j th and k th elements in an int array named arr , you would use the following algorithm:

int temp = arr[j];

// Store the jth element in temp

arr[j] = arr[k];

// Move the kth element into j

arr[k] = temp;

// Move the jth element into k

Swapping algorithm

The temp variable temporarily stores the j th element so that its value is not lost when its location is overwritten by the k th element. The need for this variable is a subtlety that beginning programmers frequently overlook. But consider what would happen if we used the following erroneous algorithm:

arr[j] = arr[k];

// Erroneous swap code

arr[k] = arr[j];

Swapping blunder

If arr[j] refers to 4 and arr[k] refers to 2 in the array 1 4 2 8 , then the erroneous algorithm would produce 1 2 2 8 , the wrong result.

Java Programming Tip: Swapping Variables

When swapping two memory elements, a temporary variable must be used to store one of the elements while its memory location is being overwritten.

The following method implements the swap algorithm for two elements, el1 and el2 of an int array:

void

swap(

int

arr[],

int

el1,

int

el2) {

int

temp = arr[el1];

// Assign first element to temp

arr[el1] = arr[el2];

// Overwrite first with second

arr[el2] = temp;

// Overwrite second with first

}

// swap()

Self-Study Exercises

9.5.4. Passing a Value and Passing a Reference

Recall from Chapter 3 that when an Object is passed to a method, a copy of the reference to the Object is passed. Because an array is an object, a reference to the array is passed to insertionSort() rather than the whole array itself. This is in contrast to how a value of a primitive type is passed. In that case, a copy of the actual value is passed.

Java Language Rule: Primitive vs. Object Parameters

When a value of a primitive data type int , double , char , boolean is passed as an argument to a method, a copy of the value is passed; when a reference to an Object is passed, a copy of the reference is passed.

One implication of this distinction is that for arguments of primitive type, the original argument cannot be changed from within the method because the method has only a copy of its value.

For example, the following method takes an int parameter n , which is incremented within the method:

public void

add1(

int

n) {
  System.out.print("n = " + n);
  n = n + 1;
  System.out.println(",   n = " + n);
}

But because n is a parameter of primitive type, incrementing it within the method has no effect on its associated argument. Thus, in the following segment, the value of Num n 's associated argumentwill not be affected by what goes on inside the add() method. The output produced by the code segment is shown in the comments:

int

Num = 5;
System.out.println("Num = " + Num);

// Prints Num = 5

add1(Num);

// Prints n = 5,  n = 6

System.out.println("Num = " + Num);

// Prints Num = 5

Passing a primitive value

Note that while n 's value has changed inside the method, Num 's value remains unaffected.

The case is much different when we pass a reference to an object. In that case, the object itself can be manipulated from within the method. The insertionSort() method is a good illustration. In the following code segment, the array anArr is printed, then sorted, and then printed again:

Sort sorter =

new

Sorter();

int

anArr[] = { 5, 10, 16, -2, 4, 6, 1 };
sorter.print(anArr);

// Prints 5 10 16 - 2 4 6 1

sorter.insertionSort(anArr);

// Sorts anArr

sorter.print(anArr);

// Prints - 2 1 4 5 6 10 16

Passing an object

As you can see, the object itself (the array) has been changed from within the method. This shows that changes within insertionSort to the array referenced by arr are actually being made to anArr itself. If fact, because insertionSort() is passed a copy of the reference variable anArr , both arr and anArr are references to the very same objectthat is, to the same array (Fig. 9.14).

The justification for passing a reference to an object rather than the entire object itself is a matter of efficiency. A reference uses just 4 bytes of data, whereas an object may use thousands of bytes. It would just be too inefficient to copy hundreds of bytes each time an object is passed to a method. Instead, the method is passed a reference to the object, thereby giving it access to the object without incurring the expense of copying large amounts of data. Indeed, Java provides no way to pass a copy of an object to a method.

Method call overhead

int

myArr[] = {1,2,3,4,5};

int

k = 3;

void

mystery(

int

a[],

int

m) {
    ++a[m];
    --m;
}