Selection sort, insertion sort, bubble sort, almost every book on algorithms for getting started, seems to be there for a reason these days: what would you do if an interviewer asked you to sort numbers in actual development? If you say bubble sort, well, that’s basically saying: I don’t have any real development experience, I’ve only heard of some terms, and I remember bubble sort in my head…

Selection sort

Wikipedia definition:

Selection sort is a simple and intuitive sorting algorithm. Here’s how it works. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements and place it at the end of the sorted sequence. And so on until all the elements are sorted.

It’s an in-place sort algorithm, meaning no additional arrays need to be defined. It’s intuitive: suppose you’ve got 10 cards in your hand and you want to order them from smallest to largest, what should we do? First of all, we sweep unsorted with the naked eye to 10 CARDS, 1 to 9 the smallest of the 9 CARDS out compared to 0, if it is less than 0 exchange (namely the left, if we put the most on the left side of the position number is 0, time on the left side of the position number is 1, so on), and then with the naked eye to sweep unsorted eight CARDS, Take the smallest of the eight cards from number 2 to 9 and swap them with the card in position 1… This process is repeated until the sort is complete, as expressed in Java code:

public class TestSelectSort {
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            for (var j = i + 1; j < a.length; ++j) {
                if(a[j] < a[i]) { var temp = a[i]; a[i] = a[j]; a[j] = temp; } } } System.out.println(Arrays.toString(a)); }}Copy the code

There is room for optimization: the inner for loop swaps elements every time it compares, and can wait until the smallest element is found. To improve:

public class TestSelectSort {
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            var min = i;
            for (var j = i + 1; j < a.length; ++j) {
                if(a[j] < a[i]) { min = j; }}if (min != i) {
                var temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}
Copy the code

Insertion sort

Instead of the sorting scenario, imagine picking up the cards from the table: Suppose we hold the cards in our left hand, pick up the cards in our right hand, start with our left hand empty, then take the cards from the table one by one, and arrange them from left to right from small to large:

On the first card, it is naturally the smallest so far, on the far left;

From the second card, it and the hand of the first card, if it is smaller than the first card, insert in front of the first card, the first card naturally to move back (right) one position;

Up 3 CARDS, it compared and have 2 CARDS in hand, right hand of the new brand and in the left hand for 2 CARDS from right to left one by one contrast, assuming that it is smaller than 2 CARDS, then continue and 1 card contrast, assuming that it is smaller than 1 card, insert it in the first card in front, behind the 2 CARDS to ward (right) a position;

From the NTH card, and so on…

Java code:

public class TestInsertSort{
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            var pos = -1;
            for (var j = i - 1; j >= 0; --j) {
                if (a[i] < a[j]) {
                    pos = j;
                } else {
                    break; }}if (pos >= 0) {
                var v = a[i];
                for (var k = i - 1; k >= pos; --k) {
                    a[k + 1] = a[k]; } a[pos] = v; } } System.out.println(Arrays.toString(a)); }}Copy the code

The code is written according to the insertion sort scenario, the outer for loop represents the starting card, a[I] represents the current playing card, and the first for loop in the inner layer is to find the appropriate position in the left hand of the sorted cards, so that the card A [I] can be inserted, and this position is recorded with pos. The second inner for loop moves the cards pos to i-1 in the left hand one position to the right and inserts the A [I]. Admittedly, the code above is a bit long and there is room for optimization, since the first inner for loop can be moved when the comparison is made:

public class TestInsertSort{
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            for (var j = i - 1; j >= 0; --j) {
                if (a[j + 1] < a[j]) {
                    var tmp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = tmp;
                } else {
                    break; } } } System.out.println(Arrays.toString(a)); }}Copy the code

The inner for loop executes three assignments for each exchange. We could simply store the target element a[I] and insert it into the appropriate position after the inner for loop completes:

public class TestInsertSort {
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            var tmp = a[i];
            var j = i - 1;
            for (; j >= 0 && a[j] > tmp; --j) {
                a[j + 1] = a[j];
            }
            a[j + 1] = tmp; } System.out.println(Arrays.toString(a)); }}Copy the code

Bubble sort

Undergraduate computer science majors are expected to be taught about this algorithm in data structures or algorithms. Here’s the basic idea:

Round 1: starting from the first element, the adjacent elements, if the front element is larger than the back element, the exchange between them, than the last set of elements that end is good, the biggest elements must be in the position of the last, it seems, bubble sort is sink sorting: big element in slowly sink.

Round 2: Start with element 1 again, but compare to element 2 from the bottom, after all, the last round has sunk the largest element.

Round 3: And so on…

Java code:

public class TestBubbleSort{
    public static void main(String[] args) {
        var a = new int[] {2.1.23.11.9.5.7};
        for (var i = 0; i < a.length; ++i) {
            for (var j = 0; j < a.length - i - 1; ++j) {
                if (a[j] > a[j + 1]) {
                    var tmp = a[j + 1];
                    a[j + 1] = a[j]; a[j] = tmp; } } } System.out.println(Arrays.toString(a)); }}Copy the code

In the next article we will introduce Hill sorting.