Thuật toán Insertion Sort

Thuật toán này dựa trên cách sắp xếp các lá bài khi chúng ta chơi bài Tú lơ khơ hay Tiến lên miền nam.

Chúng ta bắt đầu với bàn tay trái trống rỗng và 13 lá bài trên bàn. Chúng ta lấy 1 lá bài trên bàn và đặt nó vào vị trí sao cho các lá bài được sắp xếp tăng dần từ lá 3 bích cho đến lá 2 cơ. Cứ lặp lại cho đến khi nào hết bài trên bàn thì chúng ta có 13 lá bài đã được sắp xếp.


package vn.fstack.algorithm;

public class InsertionSort {

    void sort(int a[]) {
        int n = a.length;
        int step = 1;
        for (int i = 1; i < n; ++i) {
            int key = a[i];
            int j = i - 1;

            while (j >= 0 &amp;&amp; a[j] > key) {
                a[j + 1] = a[j];
                j = j - 1;
            }
            a[j + 1] = key;
            show(a, step++);
        }
    }

    static void show(int a[], int step) {
        int n = a.length;
        System.out.print("Step " + (step < 10 ? "0" + step : step) + ": ");
        for (int i = 0; i < n; ++i)
            System.out.print(a[i] + " ");

        System.out.println();
    }

    public static void main(String args[]) {
        int a[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
        InsertionSort is = new InsertionSort();
        is.sort(a);
    }

}

Sau khi thực hiện chúng ta có kết quả như bên dưới:

Step 01: 5 6 3 1 8 7 2 4 
Step 02: 3 5 6 1 8 7 2 4 
Step 03: 1 3 5 6 8 7 2 4 
Step 04: 1 3 5 6 8 7 2 4 
Step 05: 1 3 5 6 7 8 2 4 
Step 06: 1 2 3 5 6 7 8 4 
Step 07: 1 2 3 4 5 6 7 8 

Source đầy đủ của ví dụ trong bài này có thể download trên Github qua link bên dưới:

https://github.com/thitranthanh/fstack-blog/tree/master/fstack/fstack-algorithm