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

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

Sắp xếp chèn là một thuật toán tương tự cách sắp xếp quân bài của những người chơi bài.

1. Giải thuật :

Trước hết ta xem phần tử a[1] là một dãy đã có thứ tự.

  • Bước 1 : Chèn phần tử a[2] vào danh sách đã có thứ tự a[1] sao cho a[1],a[2] là một danh sách có thứ tự.
  • Bước 2: Chèn phần tử a[3] vào danh sách đã có thứ tự a[1],a[2] sao cho a[1],a[2],a[3] là một danh sách có thứ tự.
  • Tổng quát, bước i, chèn phần tử a[i+1] vào danh sách đã có thứ tự a[1],a[2],…,a[i] sao cho a[1],a[2],…,a[i+1] là một danh sách có thứ tự
  • Phần tử đang xét a[j] sẽ được chèn vào vị trí thích hợp trong danh sách các phần tử đã được sắp trước đó a[1],a[2],…,a[j-1] bằng cách so sánh khóa của a[j] với khóa của a[j-1] đứng ngay trước nó. Nếu khóa của a[j] nhỏ hơn khóa của a[j-1] thì hoán đổi a[j-1] và a[j] cho nhau và tiếp tục so sánh với khóa của a[j-1] (lúc này a[j-1] chứa nội dung của a[j]) với khóa của a[j-2] đứng nga y trước nó…

2. Cài đặt

2.1 Sắp xếp chèn trực tiếp

Trường hợp viết gộp trong 1 hàm : 

public static int[] InsertionSort(int[] array)
 {
     int pos, x;
     for (int i = 1; i < array.Length; i++)
     {
         x = array[i];
         pos = i-1;
         while ((pos>=0)&&(array[pos]>x))
         {
             array[pos + 1] = array[pos];
             pos--;
         }
         array[pos + 1] = x;
     }
     return array;
 }

Trường hợp viết tách riêng hàm insert : 

/**
 * Chèn phần tử vào vị trí thích hợp
 * @param a
 * @param k
 * @param value
 */
 private static void insert(int[] a, int k, int value) {
     int i = k - 1;
     while (i >= 0 && a[i] > value) {
         a[i + 1] = a[i];
         i = i - 1;
     }
     a[i + 1] = value;
 }
/**
 * Sắp xếp chèn 1 mảng nguyên n phần tử
 * @param a Mảng cần sắp xếp 
 * @param n Số phần tử của mảng
 */
 public static void insertSort(int[] a, int n) {
     int k = 1; // Bắt đầu từ phần tử thứ 2 đến cuối dãy
     while (k < n) {
         insert(a, k, a[k]);
         k = k + 1;
     }
 }

Trường hợp viết tách riêng hàm hoán vị: 

/**
 * Hàm hoán vị 2 phần tử của mảng a
 * @param a
 * @param i
 * @param j
 */
 public static void swap(int a[], int i, int j) {
     int k = a[i];
     a[i] = a[j];
     a[j] = k;
 }
 
 /**
 * Hàm sắp xếp chèn trực tiếp
 * 
 * @param a
 * @param n
 */
 public static void straightInsertionSort(int a[], int n) {
     for (int i = 0; i < n; i++) {
         for (int j = i; j > 0 && a[j - 1] > a[j]; --j) {
             swap(a, j - 1, j);
         }
     }
 }

2.2 Sắp xếp chèn nhị phân

Trường hợp viết gộp trong 1 hàm : 

/**
 * Hàm sắp xếp chèn nhị phân
 * 
 * @param a
 * @param n
 */
 public static void binaryInsertionSort(int a[], int n) {
     int left,right,middle;
     int temp;
     for (int i = 0; i < n; i++) {
         temp = a[i];
         left = 0;
         right = i;
         while (left < right) {
             middle = (left + right) / 2;
             if (temp >= a[middle]) {
                 left = middle + 1;
             } else {
                 right = middle;
             }
         }
         for (int j = i; j > left; --j) {
             a[j]=a[j-1];
         }
         a[left]=temp;
     }
 }

Trường hợp viết tách riêng hàm hoán vị: 

/**
 * Hàm hoán vị 2 phần tử của mảng a
 * @param a
 * @param i
 * @param j
 */
 public static void swap(int a[], int i, int j) {
     int k = a[i];
     a[i] = a[j];
     a[j] = k;
 }
 
 /**
 * Hàm sắp xếp chèn nhị phân
 * 
 * @param a
 * @param n
 */
 public static void binaryInsertionSort(int a[], int n) {
     for (int i = 0; i < n; i++) {
         int temp = a[i];
         int left = 0;
         int right = i;
         while (left < right) {
             int middle = (left + right) / 2;
             if (temp >= a[middle]) {
                 left = middle + 1;
             } else {
                 right = middle;
             }
         }
         for (int j = i; j > left; --j) {
             swap(a, j - 1, j);
         }
     }
 }

3. Đánh giá độ phức tạp thuật toán:

  • Tốt nhất – O(n^2)
  • Trung bình – O(n^2)
  • Xấu nhất – O(n^2)
  • Tính ổn định – phụ thuộc vào việc thực hiện
Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: