Thuật toán Bubble Sort

Bubble Sort là thuật toán sắp xếp đơn giản nhất hoạt động bằng cách liên tục hoán đổi các phần tử liền kề nếu chúng sai thứ tự. Chúng ta cùng xem tập tin GIF bên dưới để hiểu rõ hơn các hoạt động của thuật toán Bubble Sort.


package vn.fstack.algorithm;

public class BubbleSort {

    private static void sort(int a[], int n) {
        int step = 1;
        int i, j, temp;
        boolean swapped;
        for (i = 0; i < n - 1; i++) {
            swapped = false;
            for (j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swapped = true;
                }
                show(a, n, step++);
            }
            
            if (swapped == false) {
                break;
            }
        }
    }

    private static void show(int a[], int size, int step) {
        int i;
        System.out.print("Step " + (step < 10 ? "0" + step : step) + ": ");
        for (i = 0; i < size; 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 };
        int n = a.length;
        sort(a, n);
    }

}

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: 5 3 6 1 8 7 2 4 
 Step 03: 5 3 1 6 8 7 2 4 
 Step 04: 5 3 1 6 8 7 2 4 
 Step 05: 5 3 1 6 7 8 2 4 
 Step 06: 5 3 1 6 7 2 8 4 
 Step 07: 5 3 1 6 7 2 4 8 
 Step 08: 3 5 1 6 7 2 4 8 
 Step 09: 3 1 5 6 7 2 4 8 
 Step 10: 3 1 5 6 7 2 4 8 
 Step 11: 3 1 5 6 7 2 4 8 
 Step 12: 3 1 5 6 2 7 4 8 
 Step 13: 3 1 5 6 2 4 7 8 
 Step 14: 1 3 5 6 2 4 7 8 
 Step 15: 1 3 5 6 2 4 7 8 
 Step 16: 1 3 5 6 2 4 7 8 
 Step 17: 1 3 5 2 6 4 7 8 
 Step 18: 1 3 5 2 4 6 7 8 
 Step 19: 1 3 5 2 4 6 7 8 
 Step 20: 1 3 5 2 4 6 7 8 
 Step 21: 1 3 2 5 4 6 7 8 
 Step 22: 1 3 2 4 5 6 7 8 
 Step 23: 1 3 2 4 5 6 7 8 
 Step 24: 1 2 3 4 5 6 7 8 
 Step 25: 1 2 3 4 5 6 7 8 
 Step 26: 1 2 3 4 5 6 7 8 
 Step 27: 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