Insertion Sort (Sắp xếp chèn)

Posted on by mtoplistChuyên mục:Top List

Insertion Sort (Sắp xếp chèn) là một thuật toán sắp xếp đơn giản. Nếu tôi đưa cho bạn một cỗ bài và yêu cầu sắp xếp theo thứ tự tăng dần, có thể bạn sẽ sử dụng thuật toán này mà không hề biết mình đang dùng, vì Insertion Sort là một trong những cách sắp xếp tự nhiên nhất.

Giả sử bây giờ bạn có 1 cỗ bài với 10 thẻ bài trong tay, chúng đã được sắp xếp theo thứ tự tăng dần. Nếu tôi đưa cho bạn thêm 1 thẻ bài khác, vào yêu cầu chèn (insert) thẻ bài này vào đúng vị trí trong cỗ bài sao cho các thẻ bài vẫn được sắp xếp theo thứ tự tăng dần. Bạn sẽ làm gì?

Theo cách nghĩ tự nhiên nhất, bạn sẽ duyệt lần lượt các thẻ bài trong cỗ bài, bắt đầu duyệt từ vị trí đầu tiên hoặc duyệt từ cuối lên, so sánh giá trị của thẻ bài mới với giá trị của các thẻ bài trong cỗ bài. Khi bạn tìm đúng vị trí, bạn sẽ chèn (insert) thẻ bài mới vào đó. Tương tự, nếu tiếp tục đưa cho bạn thêm các lá bài mới, bạn sẽ lặp lại quy trình đó, chèn thẻ mới, đồng thời vẫn đảm bảo thứ tự của các thẻ bài.

Đây chính là cơ chế hoạt động của Insertion Sort. Nó bắt đầu từ phần tử thứ 2 (tức index = 1). Coi phần tử đầu tiên (tức index = 0) là một cỗ bài đã được sắp xếp. Mỗi phần tử bắt đầu từ vị trí index = 1 sẽ giống như 1 thẻ bài mới.

1. Cơ chế hoạt động của Insertion Sort

Lấy ví dụ một mảng với các giá trị {5, 1, 6, 2, 4, 3}. Hình ảnh dưới đây mô tả cách sắp xếp chèn mảng đã cho:

Image source: Studytonight

2. Cài đặt Insertion Sort

Mã code dưới đây sẽ mô tả cách cài đặt giải thuật Insertion Sort trong Java:

InsertionSort

package com.icancodeit.algorithm.sorting;

import java.util.Arrays;

public class InsertionSort {

  // Sort the original data
  private static final int[] NUMBERS = {5, 1, 6, 2, 4, 3};

  public static void insertionSort(int[] arr) {
    int temp, length = arr.length;
    for (int i = 1; i < length; i++) {
      for (int j = i; j > 0; j--) {
        if (arr[j] < arr[j - 1]) {
          temp = arr[j];
          arr[j] = arr[j - 1];
          arr[j - 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    insertionSort(NUMBERS);
    System.out.println(Arrays.toString(NUMBERS) + " insertionSort");
  }

}

Kết quả

[1, 2, 3, 4, 5, 6] insertionSort

3. Phân tích độ phức tạp của Insertion Sort

  • Time Complexity: O(n2)
  • Space Complexity: O(1)

Đọc thêm:

https://www.studytonight.com/data-structures/insertion-sorting

https://github.com/amejiarosario/

Advertisement

mtoplist