Insertion Sort - Deft Blog

Mục lục

1 Minh hoạ
2 Implementation
3 Độ phức tạp của thuật toán

Insertion Sort là thuật toán sắp xếp hoạt động tương tự cách chúng ta sắp các lá bài. Với mỗi phần tử trong danh sách, sẽ được di chuyển đến vị trí tương ứng:

Cho mảng arr có số lượng phần tử là size

B1: Khởi tạo i = 1
B2: Loop i từ 1 đến SIZE – 1 + Khởi tạo key = arr[i]
(a) Khởi tạo j = i – 1
– Trong khi j >= 0 và arr[j] < key * swap arr[j] với arr[j + 1] * j = j – 1 + arr[j + 1] = key

Minh hoạ

Implementation

/*
 * Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
 * O(n^2)
 */

public class InsertionSort {

    public static <T extends Comparable<T>> void sort(T[] arr, int n) {
        for (int i = 1; i < n; ++i) {
            T key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1],
            // that are greater than key,
            // to one position ahead of
            // their current position
            /*
             * Use codition arr[j] with pivot
             * Sort by ASC => Compare ">"
             * Sort by DESC => Compare "<"
             */
            while (j >= 0 && arr[j].compareTo(key) < 0) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

Độ phức tạp của thuật toán

Trường hợp xấu nhất là dãy được sắp xếp theo tự ngược: θ(n²).
Trường hợp tốt nhất: Dãy sắp xếp theo đúng thứ tự: θ(n).

Link source code: insertion sort