Sắp xếp chèn – Insertion Sort

Giới thiệu

Sắp xếp chèn (Insertion sort) là một thuật toán sắp xếp in-place, bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Với cấu trúc dữ liệu mảng, hãy tưởng tượng nó gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự chưa được sắp xếp. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).

Cài đặt

public static void  insertSort (int [] array) {
     for (int  i =  1 ; i < array.length; i++) {
          int  temp = array[i];
          int  j = i - 1 ;
          for  (; j > = 0 && array[j] > temp; j--) {
          // Moves the value greater than temp back by one unit
               array [j + 1] = array [j];
          }
          array [j + 1] = temp;
     }
     System.out.println(Arrays.toString(array) + "insertSort");
}

Đánh giá thuật toán sắp xếp chèn

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

• Trường hợp tốt: O(n)
• Trung bình: O(n²)
• Trường hợp xấu: O(n²) (Khi mảng đầu vào sắp xếp ngược)

Không gian bộ nhớ sử dụng: O(1)

Ổn định (Stable): Có

Tại chỗ (In-place): Có

Cách sử dụng: Sắp xếp chèn được sử dụng khi số lượng phần tử nhỏ, nó có thể hữu ích khi mảng đầu vào gần như đã được sắp xếp, chỉ một vài phần tử bị đặt sai trong mảng lớn hoàn chỉnh.