Java Arena
Start learning
Step 2 of 6

Swapping, and sorting by hand

Sorting moves values around in an array, and its basic move is the swap: two elements trade places. It takes a little care. This tries to swap the first two heights the obvious way:

int[] heights = {152, 140, 171};
heights[0] = heights[1];
heights[1] = heights[0];
System.out.println(Arrays.toString(heights));
Output
[140, 140, 171]

The first line copies 140 over 152, so 152 is gone before the second line can use it. heights[1] = heights[0] then copies 140 back to where it already was. It's like swapping the drinks in two full glasses: you need a third, empty glass to hold one drink while you pour the other.

In code, the third glass is a variable:

int[] heights = {152, 140, 171};
int temp = heights[0];
heights[0] = heights[1];
heights[1] = temp;
System.out.println(Arrays.toString(heights));
Output
[140, 152, 171]

temp keeps a copy of 152 while 140 moves to index 0, and then 152 goes to index 1. (Arrays.toString gives an array's values in square brackets, as in module 15.)

As a method, a swap takes the array and the two indexes. A method that gets an array can change the caller's array (module 15), so the swap shows in main:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] heights = {152, 140, 171, 131};
        switchPlaces(heights, 0, 3);
        System.out.println(Arrays.toString(heights));
    }

    public static void switchPlaces(int[] values, int a, int b) {
        int temp = values[a];
        values[a] = values[b];
        values[b] = temp;
    }
}
Output
[131, 140, 171, 152]

Sorting a line of people by hand

Picture a class lining up for a photo, shortest first. One simple way to do it: find the shortest person, and have them swap places with whoever stands first. Then find the shortest of the rest, and swap them with whoever stands second. Keep going until you reach the end of the line. This is selection sort: each round selects the smallest of the values that aren't in place yet.

Here it is on five heights, in centimeters. Each round finds the smallest value from the round's index on, and swaps it to that index:

Round Smallest from the index on Swap The array after the round
start [152, 140, 171, 131, 160]
index 0 131, at index 3 0 and 3 [131, 140, 171, 152, 160]
index 1 140, at index 1 1 and 1 [131, 140, 171, 152, 160]
index 2 152, at index 3 2 and 3 [131, 140, 152, 171, 160]
index 3 160, at index 4 3 and 4 [131, 140, 152, 160, 171]
  • After each round, one more value is in its final place, and the front part of the array is sorted.
  • In the round of index 1, 140 is already where it belongs. Swapping an element with itself changes nothing, so this round needs no special case.
  • Five values take four rounds. Once all the others are in place, the last one, 171, has nowhere else to go.

Each round is two things you've already seen: step 1's search for the smallest value from an index on, and a swap. The program of this task writes the rounds out by hand. Its positionOfLowest(values, start) is step 1's fastestFrom with names that fit any numbers: it returns the index of the smallest value from start on.

Your task

Challenge 1 of 3

What does this program print? Do the rounds on paper, the way the table does.

Challenge 2

A relay team's running order is a list of names. Write the method tradePlaces(ArrayList<String> order, int a, int b), which swaps the runners at indexes a and b. A list has no [ ]: read an element with get, and put a new one in its place with set(index, value) (module 14). The check runs:

ArrayList<String> order = new ArrayList<>();
order.add("Ada");
order.add("Bo");
order.add("Cy");
order.add("Dee");
tradePlaces(order, 1, 2);
System.out.println(order);

and expects:

[Ada, Cy, Bo, Dee]

Challenge 3

A hiking trail's checkpoints are in an array, in the order of the walk out. Write the method reverseInPlace(String[] checkpoints), which turns the same array around for the walk back: the last checkpoint becomes the first, and so on. Don't make a new array. Swap elements instead: the first with the last, the second with the second to last, and so on, up to the middle. The check runs:

String[] checkpoints = {"Parking", "Lake", "Bridge", "Summit"};
reverseInPlace(checkpoints);
System.out.println(Arrays.toString(checkpoints));

and expects:

[Summit, Bridge, Lake, Parking]
Previous: Algorithms and the smallest value Next: Selection sort in code