# Section 9.5. Array Algorithms: Sorting

[Page 420 ( continued )]

### 9.5. Array Algorithms: Sorting

Sorting an array is the process of arranging its elements in ascending or descending order. Sorting algorithms are among the most widely used algorithms. Any time large amounts of data are maintained , there is some need to arrange them in a particular order. For example, the telephone company needs to arrange its accounts by the last name of the account holder as well as by phone number.

#### 9.5.1. Insertion Sort

The first sorting algorithm we will look at is known as insertion sort , so named because, as it traverses through the array from the first to the last element, it inserts each element into its correct position in the partially sorted array.

For an array of N elements, let's think of the array as divided into two parts . The sorted part will be the left-hand side of the array. And the unsorted part will be the right-hand side of the array. Initially, the sorted part consists of the first element in the arraythe element at index 0.

Insertion sort moves through the unsorted portion of the arraythat is its loop variable, k , ranges from 1 through N - 1. On each iteration it inserts the k th element into its correct position in the sorted part of the array. To insert an element into the sorted part of the array, it may be necessary to move elements greater than the one being inserted out of the way.

In pseudocode, insertion sort can be represented as follows :

```Insertion Sort of an array, arr, of N elements into ascending order
1. For k assigned 1 through N-1
2.   Remove the element arr[k] and store it in x.
3.   For i starting at k-1 and for all preceding elements greater than x
4.     Move arr[i] one position to the right in the array.
5.   Insert x at its correct location.
```

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
```

[Page 421]

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.

##### (This item is displayed on page 422 in the print version)
 ``` 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

[Page 422]

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.

[Page 423]

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

[Page 424]

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
 Exercise 9.8 Sort the array 24 18 90 1 0 85 34 18 using the insertion sort algorithm. Show the order of the elements after each iteration of the outer loop. Exercise 9.9 Sort the array 24 18 90 1 0 85 34 18 using the selection sort algorithm. Show the order of the elements after each iteration of the outer loop. Exercise 9.10 Write a Java code segment to swap two Student objects, student1 and student2 . Exercise 9.11 Write a Java implementation of the selectionSort() method to sort an array of int .

#### 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.

[Page 425]

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

```
public void

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

// 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).

##### Figure 9.14. When an array is passed to a method, both the parameter and the corresponding argument refer to the same object.

[Page 426]

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.

 Exercise 9.12 Give the values that will be stored in myArr and k after you invoke mystery(myArr, k) , where myArr , k and mystery() are declared as follows: ``` int myArr[] = {1,2,3,4,5}; int k = 3; void mystery( int a[], int m) { ++a[m]; --m; } ```