Insertion Sort

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:  θ(n2).
Trường hợp tốt nhất: Dãy sắp xếp theo đúng thứ tự: θ(n).

Link source code: insertion sort

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x