Array Sorting ​

Sorting an array is a very basic need in a program. Commonly used sorting algorithms include bubble sort, insertion sort, and quick sort.

Let's take a look at how to use the bubble sort algorithm to sort an integer array from small to large:

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
    // before sorting:
    System.out.println(Arrays.toString(ns));
    for (int i = 0; i < ns.length - 1; i++) {
      for (int j = 0; j < ns.length - i - 1; j++) {
        if (ns[j] > ns[j+1]) {
          // Swap ns[j] and ns[j+1]:
          int tmp = ns[j];
          ns[j] = ns[j+1];
          ns[j+1] = tmp;
        }
      }
    }
    // after sorting:
    System.out.println(Arrays.toString(ns));
  }
}

The characteristic of bubble sorting is that after each cycle, the largest number is swapped to the end. Therefore, the next cycle can "eliminate" the last number. Each cycle is higher than the end position of the previous cycle. The first one.

In addition, note that exchanging the values of two variables requires the use of a temporary variable. It is wrong to write something like this:

int x = 1;
int y = 2;

x = y; // x is now 2
y = x; // y is still 2 now

The correct way to write it is:

int x = 1;
int y = 2;

int t = x; // Save the value of x in the temporary variable t, which is now 1
x = y; // x is now 2
y = t; // y is now the value of t 1

In fact, Java's standard library already has a built-in sorting function. We only need to call Arrays.sort() provided by the JDK to sort:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        Arrays.sort(ns);
        System.out.println(Arrays.toString(ns));
    }
}

It's important to note that sorting an array actually modifies the array itself. For example, the array before sorting is:

int[] ns = { 9, 3, 6, 5 };

In memory, this integer array is represented as follows:

      ┌───┬───┬───┬───┐
ns───▶│ 9 │ 3 │ 6 │ 5 │
      └───┴───┴───┴───┘

When we call Arrays.sort(ns); this integer array becomes:

      ┌───┬───┬───┬───┐
ns───▶│ 3 │ 5 │ 6 │ 9 │
      └───┴───┴───┴───┘

That is, the contents of the array pointed to by the variable ns have been changed.

If you are sorting an array of strings, for example:

String[] ns = { "banana", "apple", "pear" };

Before sorting, this array is represented in memory as follows:

                  ┌──────────────────────────────────┐
               ┌───┼──────────────────────┐           │
               │   │                      ▼           ▼
         ┌───┬─┴─┬─┴─┬───┬────────┬───┬───────┬───┬──────┬───┐
ns ─────▶│░░░│░░░│░░░│   │"banana"│   │"apple"│   │"pear"│   │
         └─┬─┴───┴───┴───┴────────┴───┴───────┴───┴──────┴───┘
           │                 ▲
           └─────────────────┘

After calling Arrays.sort(ns); after sorting, the array is represented in memory as follows:

                   ┌──────────────────────────────────┐
               ┌───┼──────────┐                       │
               │   │          ▼                       ▼
         ┌───┬─┴─┬─┴─┬───┬────────┬───┬───────┬───┬──────┬───┐
ns ─────▶│░░░│░░░│░░░│   │"banana"│   │"apple"│   │"pear"│   │
         └─┬─┴───┴───┴───┴────────┴───┴───────┴───┴──────┴───┘
           │                              ▲
           └──────────────────────────────┘

The original three strings have not changed in memory, but the pointer of each element of the ns array has changed.

Practise ​

Please think about how to sort an array in descending order:

// Sort descending
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        // Before sorting:
        System.out.println(Arrays.toString(ns));
        // TODO:
        // After sorting:
        System.out.println(Arrays.toString(ns));
        if (Arrays.toString(ns).equals("[96, 89, 73, 65, 50, 36, 28, 18, 12, 8]")) {
            System.out.println("Test successful");
        } else {
            System.out.println("test failed");
        }
    }
}

Summary ​

Commonly used sorting algorithms include bubble sort, insertion sort, quick sort, etc.;

Bubble sort uses two levels for loops to implement sorting;

Swapping the values of two variables requires the use of a temporary variable;

You can directly use Arrays.sort() provided by the Java standard library for sorting;

Sorting an array directly modifies the array itself.