1. Insertion Sort

Insertion Sort là một thuật toán sắp xếp đơn giản hoạt động bằng cách chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Ban đầu, phần đã sắp xếp chỉ chứa một phần tử (phần tử đầu tiên), sau đó các phần tử từ phần chưa sắp xếp được lấy từng cái một và chèn vào vị trí thích hợp trong phần đã sắp xếp.

Thuật toán này tương tự như cách bạn sắp xếp bài trong tay khi chơi bài: bạn lấy từng lá bài và đặt nó vào đúng vị trí trong dãy bài đã sắp xếp.

2. Cách hoạt động của Insertion Sort

Giả sử chúng ta cần sắp xếp mảng sau.

1. Chúng ta sẽ gán phần tử đầu tiên của mảng coi như là đã được sắp xếp. Lấy phần tử thứ 2 là lưu vào biến key.
   So sánh key với phần tử đầu tiên. Nếu phần tử đầu tiên lớn hơn key, thì key sẽ được đặt trước phần tử đầu tiên.

2. Bây giờ ta có 2 phần tử đầu tiên đã được sắp xếp.
   Lấy phần tử thứ 3 và so sánh nó với các phần tử bên trái của nó. Và đặt nó vào ngay sau phần tử nhỏ hơn nó. Nếu không có phần tử nào nhỏ hơn, hãy đặt ở đầu mảng.

3. Tương tự như vậy, đặt mọi phần tử chưa được sắp xếp vào đúng vị trí của nó.

3. Triển khai thuật toán

// Insertion sort in Java
 
import java.util.Arrays;
 
class InsertionSort {
 
  void insertionSort(int array[]) {
    int size = array.length;
 
    for (int step = 1; step < size; step++) {
      int key = array[step];
      int j = step - 1;
 
      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }
 
      // Place key at after the element just smaller than it.
      array[j + 1] = key;
    }
  }
 
  // Driver code
  public static void main(String args[]) {
    int[] data = { 9, 5, 1, 4, 3 };
    InsertionSort is = new InsertionSort();
    is.insertionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

4. Độ phức tạp thuật toán

4.1 Độ phức tạp về thời gian

• Trường hợp xấu nhất: O(n2)
  Giả sử một mảng được sắp xếp theo thứ tự tăng dần, và bạn muốn sắp xếp theo thứ tự giảm dần. Trong trường hợp này, độ phức tạo trường hợp xấu nhất xảy ra.
  Mỗi phần tử phải được so sánh với từng phần tử khác, do đó, với mỗi phần tử thứ n, ta có (n-1) số lần cần phải so sánh.
  Do đó, tổng số lần cần so sánh là = n*(n-1) ~ n2
• Trường hợp tốt nhất: O(n)
  Khi mảng được sắp xếp, vòng lặp bên ngoài chạy n số lần trong khi bên trong không chạy lần nào. Vì vậy, chỉ có n số phép so sánh. Do đó, độ phức tạp là O(n)
• Trường hợp thường xảy ra: Khi các phần tử của mảng không theo thứ tự nhất định(không tăng dần hoặc giảm dần) O(n2)

4.2 Độ phức tạp của không gian

Độ phức tạp của không gian là O(1) do key sử dụng thêm một biến.

5. Ứng dụng Insertion Sort

Phương phát Insertion Sort được sử dụng khi:

• Mảng có một số lượng nhỏ các phần tử.
• Chỉ còn lại một vài phần tử cần sắp xếp.