Thuật toán sắp xếp chèn – Insertion Sort

Giới thiệu

Thuật toán sắp xếp chè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 xếp các quân bài trên tay trong một trò chơi bài.

Để sắp xếp theo đúng trật tự, người chơi sẽ rút lần lượt từ quân bài thứ 2, sau đó so với các quân bài đứng trước nó để chèn vào vị trí thích hợp.

Tóm lại, sắp xếp chèn là thuật toán sắp xếp đặt một phần tử chưa được sắp xếp vào vị trí thích hợp của nó trong mỗi lần lặp.

Ý tưởng thuật toán sắp xếp chèn

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

Bước 1

Phần tử đầu tiên trong mảng được giả định là đã được sắp xếp. Lấy từ phần tử thứ hai và lưu chúng trong 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.

Bước 2

Bây giờ, hai phần tử đầu tiên đã được sắp xếp.

Lấy phần tử thứ ba và so sánh nó với các phần tử bên trái của nó. Đặt nó ngay sau phần tử nhỏ hơn nó. Nếu không có phần tử nào nhỏ hơn nó, thì hãy đặt nó ở đầu mảng.

Bước 3

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

Thuật toán sắp xếp chèn

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSortCode language: PHP (php)

Cài đặt thuật toán sắp xếp chèn

function insertionSort(array) {
    var size = array.length;

    for (var step = 1; step < size; step++) {
      var key = array[step];
      var 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;
    }
  }

var arr = [3, 5, -2, 14, -9, 30];
insertionSort(arr);
console.log(arr);
Code language: PHP (php)

Kết quả

[-9, -2, 3, 5, 14, 30]Code language: JSON / JSON with Comments (json)

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

Độ phức tạp thời gian:

• Trường hợp xấu nhất: O(n²)
  Giả sử, một mảng có thứ tự tăng dần và bạn muốn sắp xếp nó theo thứ tự giảm dần. Trong trường hợp này, trường hợp xấu nhất sẽ xảy ra.
  Mỗi phần tử phải được so sánh với mỗi phần tử khác, do đó, đối với mỗi phần tử thứ n sẽ có (n-1) số phép so sánh được thực hiện. Do đó, tổng số phép so sánh = n*(n-1) ~ n²
• 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 lần trong khi vòng lặp bên trong hoàn toàn không chạy. Vì vậy, chỉ có n số phép so sánh. Do đó, độ phức tạp là tuyến tính.
• Trường hợp trung bình: O(n²)
  Nó xảy ra khi các phần tử của mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).

Độ phức tạp không gian:

Độ phức tạp không gian là O(1) vì một biến key được sử dụng.

Ứng dụng của thuật toán sắp xếp chèn

Thuật toán sắp xếp chèn được sử dụng trong các trường hợp:

• Mảng có ít phần tử
• Mảng gần như đã được sắp xếp, chỉ một vài phần tử bị đặt sai chỗ

Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.

---

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.