Array Algorithms: Sorting

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

Subsection 9.5.1 Insertion Sort

The first sorting algorithm we’ll 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.

Sorted   |  Unsorted   Before inserting the kth element
5 14 19  |  1 0 67 4
            ^
            k

On each iteration insertion sort will insert the first element in the unsorted part of the array, the kth element, into its correct position in the sorted part of the array.

Sorted    |  Unsorted  After inserting the kth element
1 5 14 19 |  0 67 4
             ^ 
             k

To insert the kth element into the sorted part of the array, it will be necessary to move elements greater than it out of the way.

In pseudocode, insertion sort can be represented as follows:

Algorithm 9.5.1. Insertion sort.

Insertion Sort of an array, arr, of N elements into ascending order
1. For k assigned 1 through N-1
2.   Save the kth element, arr[k], in temp.
3.   Set i to point to the largest element in the sorted part
4.   While i >= 0 AND the ith element is greater than temp  
5.     Shift the ith element to the right
6.     Set i to point to the next element in the sorted part
7.   Insert temp, the kth element, at its correct location.

As you see, the algorithm has nested loops, an outer for-loop and an inner while-loop. Each iteration of the outer loop will insert one element, the kth element, into its proper place in the sorted part of the array. The role of the inner while-loop is to move the already sorted elements out of the way.

The outer (k) loop, iterates from 1 to N-1. On each iteration, it saves the kth element in temp. It then sets the while-loop variable, i, to point to the largest element in the sorted part of the array, the element just to the left of the kth element.

The inner loop proceeds from right to left — that is, from k-1 towards 0. It shifts all numbers greater than temp to the right. It terminates when it finds a number smaller or equal to temp.

After the while-loop terminates, temp (the kth element) is inserted into its proprer place in the sorted part of the array.

To see how this works, consider an integer array containing five numbers:

21 |  20  27  24  19      temp = 20
      k

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, starting at arr[1], one at a time, inserting them into their proper positions in the sorted portion of the array. The outer loop saves the kth element (20) in temp.

Because 21 is greater than 20, the inner loop will move 21 to the right by one position. And will then terminate.

The outer loop will complete its work by inserting 20 in the location previously occupied by 21, in effect swapping 20 and 21. At this point, after one complete iteration of the outer loop, the first two numbers are in the correct order relative to each other:

20  21 |  27  24  19     temp = 27
          k

For the next element, 27, none of elements in the sorted portion need to be moved because they are all less than 27. The inner loop will not iterate at all in this case. So after two complete iterations we have:

20  21  27 |  24  19    temp = 24
              k

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

20  21  24  27 | 19    temp = 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.

However, for the last element, 19, all of the elements in the sorted part of the array need to be shifted one space to the right. Let’s trace each iteration of the inner loop starting from this point, where k = 4 and i = 3:

              k
20 21 24 27 | 19   Save 19 in temp:              temp=19, i=3
20 21 24 27 | 27   Move 27 to the right:         temp=19, i=2
20 21 24 24 | 27   Move 24 to the right:         temp=19, i=1
20 21 21 24 | 27   Move 21 to the right:         temp=19, i=0
20 20 21 24 | 27   Move 20 to the right:         temp=19, i=-1 inner loop terminates
19 20 21 24 27 |   Insert temp=19 at index i+1

It’s important to see that when the inner loop terminates i will always be one space to the left of where we make the insertion. That’s why the insertion is made at arr[i+1].

The Sort class (Listing 9.5.2) provides an implementation of the insertionSort() method.

public class Sort {

public void insertionSort(int arr[]) {
    int temp;                         // Temporary variable 
    for (int k = 1; k < arr.length; k++)  {
        temp = arr[k];                  // Save the kth element in temp
        int i = k-1;                    // Start at high end of sorted 
        while (i >= 0 && arr[i] > temp) { // For each element > temp
          arr[i+1] = arr[i];            // Move it to the right
          i--;                          // Move i to the left
        }
        arr[i + 1] = temp;              // Insert the kth element
    } // outer
  } // 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

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

It’s important to see, again, that after the while-loop terminates the variable i will always point one space to the left of where the kth element should be inserted. Thus, the insertion is made at arr[i+1].

Also, note the complex entry condition we use for the inner while-loop:

i >= 0 && arr[i] > temp;

This is necessary because we want i to iterate from right to left, but not to go past 0. But we also want the loop to stop if arr[i] isn’t greater than temp. We want it to stop as soon as we find a number that’s less than or equal to temp. That’s where temp needs to be inserted.

There are also a couple of syntax points that are important to observe. First, note in the declaration of the insertionSort() method 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.

Principle 9.5.3. 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 non-array parameter.

Second, in the main() method note that brackets are not used when an array of integers is passed to the insertionSort() method:

sorter.insertionSort(intArr); // Pass intArr to the method

Principle 9.5.4. DEBUGGING TIP: Passing an Array Argument.

When passing an array to a method only the array name is used. Brackets are not used.

Exercises Self Study Exercise

1. Run Insertion Sort.

Run the insertion sort program. Click on Show CodeLens to step through the code with the Next button.

public class Sort {

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()

2. Insertion sort trace 1.

Suppose the following array of numbers is sorted from low to high by insertion sort:

24 18 90 1 0 85 34 18

Which of the following shows the order of the numbers after one pass through the array?

24 18 90 1 0 85 34 18
Incorrect
1 24 18 90 0 85 34 18
Incorrect
85 24 90 1 0 18 34 18
Incorrect
18 24 90 1 0 85 34 18
Correct. 18 would be inserted before 24.

Hint.

Trace through one complete iteration of the outer loop.

3. Insertion sort trace 2.

Suppose the following array of numbers is sorted from low to high by insertion sort:

24 18 90 1 0 85 34 18

Which of the following shows the order of the numbers after four passes through the array?

18 24 90 1 0 85 34 18
Incorrect. That’s how it would look after 2 passes.
0 1 18 24 85 90 34 18
Incorrect. That’s how it would look after 5 passes.
0 1 18 24 90 85 34 18
Correct. The left side would be sorted up to the 5th element.
0 1 18 18 24 34 85 90
Incorrect. The array would not be completely sorted after 4 passes.

Hint.

Trace through four complete iterations of the outer loop. After four passes the numbers up to and including location 4 in the original array should be in the correrct order.

Subsection 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, layed out on the table. Starting with the first card, assume it is the smallest card. Compare it with the second, third, fourth and every other card in the deck. Whenever you find a card that is smaller than the first card, swap it with the first card.

In this way we will have selected the smallest card and placed it at the first position in the deck.

Complete the process again starting this time with the second card. Find the smallest card in the remaining deck and swap it with the second card. Repeating this process 24 times a for deck of 25 cards will correctly sort the deck.

Translating this strategy into pseudocode gives the following algorithm:

Algorithm 9.5.5. Selection sort.

Selection sort of an N element array <c>arr</c> from small to large
1. For k assigned 0 to N-2          // Outer loop
2.   smallest = k                   // Assume kth is smallest so far
3.   For j assigned k+1 to N-1       // Inner loop: finds smallest
4.     If arr[j] &lt; arr[smallest]
5.        smallest = j               // Remember which is smallest
6.   Swap arr[k] and arr[smallest]   // Swap kth and smallest

For an array of N elements, you need to repeat the outer loop N-1 times. On each iteration of the outer loop,the inner loop takes care of finding the next smallest element.

In the outer loop, the algorithm assumes that the kth element is the smallest so far (line 2). It usually won’t be, of course. But it will be after the inner loop terminates and kth element is swapped with the smallest.

The inner loop finds smallest by iterating through the rest of the array (from k+1 to N-1) comparing each element with the smallest so far (lines 4) and remembering the location of the element that is currently the smallest (lines 5).

Finally, when the inner loop terminates, the algorithm swaps the smallest element with kth element.

Exercises Self-Study Exercises

1. Selection sort trace 1.

Suppose the following array of numbers is sorted from low to high by selection sort:

24 18 90 1 0 85 34 18

Which of the following shows the order of the numbers after one pass through the array?

18 24 90 1 0 85 34 18
Incorrect. Are you thinking of insertion sort?
0 1 18 18 24 85 34 90
Incorrect. That’s how it would look after 5 passes.
0 18 90 1 24 85 34 18
Correct. The smallest number would be swapped into the 1st location.
0 1 18 18 24 34 85 90
Incorrect. The array would not be completely sorted after 1 pass.

Hint.

Trace through one complete iteration of the outer loop.

2. Selection sort trace 2.

Suppose the following array of numbers is sorted from low to high by selection sort:

24 18 90 1 0 85 34 18

Which of the following shows the order of the numbers after four passes through the array?

0 1 90 18 24 85 34 18
Incorrect. That’s how it would look after 2 passes.
0 1 18 90 24 85 34 18
Incorrect. That’s how it would look after 3 passes.
0 1 18 18 24 85 34 90
Correct. The four smallest numbers would be swapped into their locations.
0 1 18 18 24 34 85 90
Incorrect. The array would not be completely sorted after 1 pass.

Hint.

Trace through four complete iterations of the outer loop. After each iteration the next smallest number should be swapped into place.

Subsection 9.5.3 Algorithm: Swapping Memory Elements

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

Algorithm 9.5.6. Swap Two Variables.

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

The temp variable temporarily stores the jth element so its value is not lost when its location is overwritten by the kth 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];

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.

Principle 9.5.7. 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()

Exercises Self-Study Exercises

1. Swapping values in variables.

Suppose the double variables var1 and var2 have been properly declared and initialized. Arrange the following blocks to swap their values.

double temp = 0;
---
temp = var1;
---
var1 = var2;
---
var2 = temp;

Hint.

temp

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

Principle 9.5.8. 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 argument — will 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

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

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 object — that is, to the same array (Figure 9.5.9).

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

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.

Exercises Self-Study Exercise

1. Array Parameter.

Consider the fillowing code segment:

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

void mystery(int a[], int m) {
  ++a[m];
  --m;
}

Which of the following gives the correct values stored in myArr after mystery(myArr, k) is called?

1,2,3,4,5
Incorrect. The expression will increment one of array elements.
1,2,4,4,5
Incorrect. Are you forgetting that arrays are zero-indexed?
1,2,3,5,5
Correct. The change in the myArr[3] will persist after the method finishes.
1,2,3,4,6
Incorrect. Try again you’ve incremented the wrong element.

Hint.

This question has to do with how array arguments are passed to a method.

2. What’s the value?

Consider the fillowing code segment:

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

void mystery(int a[], int m) {
  ++a[m];
  --m;
}

After the mystery(myArr, k) method completes the variable k will have the value .

Hint.

Hint: Recall the difference between value and reference parameters.

3. Selection sort.

Arrange the following blocks to complete the implemention of selection sort.

public void selectionSort(int arr[]) {
  int smallest = 0;
  for (int k = 0; k < arr.length -1; k++)  {

    // Implement here

  } // outer
} // selectionSort()

smallest = k; 
---
for (int i k+1; i<arr.length; i++) {
---
  if (arr[i] < arr[smallest]) 
---
    smallest = j; 
---
}
---
swap(arr, k, smallest);

Hint.

You have attempted of activities on this page.

Prev Top Next