[Thuật toán sắp xếp CHÈN (Insertion Sort)]

Nội Dung:
   1. Thuật toán hoạt động như thế nào.
   2. Cài đặt thuật toán.
   3. Bình luận.

#1. Thuật toán hoạt động như thế nào?

     Sắp xếp chèn (insertion sort) cũng giống như sắp xếp chọn là một trong số những thuật toán sắp xếp kinh điển. Chúng ta lại để ý cái tên "sắp xếp CHÈN". Vậy chèn cái gì? chèn vào đâu? Đến đây chắc hẳn nhiều bạn đã có sự liên tưởng riêng cho mình 😁. Ok!, để dễ hình dung chúng ta lại coi một animation cho dễ hiểu.

Màu xanh lá: là biến chạy để tìm phần tử nhỏ nhất lớn hơn phần tử đang xét.

Màu đỏ: đánh dấu phần tử đang xét.

Màu cam: là các phần tử đã được sắp xếp.

      Khác với sắp xếp chọn thì sắp xếp chèn không chia mảng dữ liệu ra làm đôi mà nó chỉ đơn giản duyệt từ đầu đến cuối mảng. Với mỗi phần tử được lấy ra để xét (màu đỏ) thì thuật toán thực hiện duyệt từ phần tử trước đó (biến chạy màu xanh) đến đầu của mảng.

       Trong quá trình duyệt thì thực hiện so sánh. So sánh cái gì? Thì nó so sánh thằng đang xét (màu đỏ) với những thằng phía trước. Quá trình này dừng lại khi gặp được phần tử NHỎ NHẤT trong số những phần tử LỚN HƠN trước đó.

        Khi đó thuật toán thực hiện chèn phần tử đang xét (màu đỏ) vào vị trí phần tử nhỏ nhất trong số các phần tử lớn hơn trước đó. Và lưu ý rằng trong quá trình để chèn được ta phải thực hiện dịch các phần tử lên một đơn vị.

         Quá trình tiếp diện với các phần tử tiếp theo. Vậy chúng ta trả lời được câu hỏi:"CHÈN cái gì" và "CHÈN vào đâu". Đó là chèn phần tử đang xét vào vị trí của phần tử nhỏ nhất trong số những phần tử lớn hơn trước đó.

#2. Cài đặt thuật toán.

Cài đặt bằng C++  

1. #include<iostream>  
2. using namespace std;  
3.   
4. int main() {  
5.     int data[] = {9, 14, 3, 2, 43, 11, 58, 22};  
6.     int size = sizeof(data) / sizeof(int);  
7.     for(int i = 1; i < size; i++){  
8.         int item = data[i];  
9.         int j = i-1;  
10.         while((j>=0) && (item < data[j])){  
11.             data[j+1] = data[j];  
12.             j--;  
13.         }  
14.         data[j+1] = item;  
15.     }  
16.     for(int k = 0; k < size; k++)  
17.         cout << data[k] << " ";  
18.     return 0;  
19. }  

Cài đặt bằng Java

1. public class InsertionSort {  
2.     public static void main(String[] args) {  
3.         int[] data = {9, 14, 3, 2, 43, 11, 58, 22};  
4.         for (int i = 1; i < data.length; i++) {  
5.             int item = data[i];  
6.             int j = i - 1;  
7.             while ((j >= 0) && (item < data[j])) {  
8.                 data[j+1] = data[j];  
9.                 j--;  
10.             }  
11.             data[j+1] = item;  
12.         }  
13.         for (int i = 0; i < data.length; i++){  
14.             System.out.println(data[i]);  
15.         }  
16.     }  
17. }  

Cài đặt bằng Python

1. def insertion_sort():  
2.     data = [9, 14, 3, 2, 43, 11, 58, 22]  
3.     for i in range(1, len(data)):  
4.         item = data[i]  
5.         j = i - 1  
6.         while (j >= 0) and (item < data[j]):  
7.             data[j + 1] = data[j]  
8.             j -= 1  
9.         data[j+1] = item  
10.     for x in range(0, len(data)):  
11.         print(data[x])  
12. insertion_sort()  

     OK! Code xong rồi, ngồi đọc lại cái nhỉ. Như thường lệ mình đã triển khai code trên Cpp, Java, Python để bạn nào quen với ngôn ngữ nào có thể dễ dàng hiểu được (cơ mà toàn cú pháp cơ bản đúng hem).

     Chúng ta có gì và phải làm gì?

      - Input: là một mảng các phần tử chưa được sắp xếp (ở đây mình đặt tên là data). Các bạn có thể                       viết một hàm sinh ra một mảng random với size nào đó để test cũng ok đấy.

      - Output: đưa ra một mảng các phần tử sau khi sắp xếp (có thể tăng dần hoặc giảm dần)

[2, 3, 9, 11, 14, 22, 43, 58]

     Ở đây chúng ta vẫn sẽ có hai vòng lặp. Vậy vòng for bên ngoài làm cái gì? Đơn giản nó dùng để lặp qua tất cả các phần tử của mảng (nhìn là biết rồi 😆) . Khoan, nhưng sao nó không chạy từ phần tử đầu tiên mà chạy từ phần tử thứ 2? Ơ hay, chạy từ phần tử đầu tiên thì lấy đâu ra thằng nào để xét ở phía trước nó có nhỏ hơn nó không?

     OK, bên trong vòng for ta làm cái gì? Đầu tiên lấy ra phần tử ở vị trí tương ứng để xét (ở đây mình gọi là item). Sau đó duyệt từ phần tử trước nó đến đầu mảng. Ở đây các bạn lưu ý tại sao mình lại phải sử dụng vòng lặp while. Thực ra nó theo tư duy của thuật toán và hai nữa chúng ta đang làm việc với array (các bạn biết rồi, array có size cố định nên chúng ta phải kiểm tra ở chỗ j>=0 nếu không là gặp ArrayIndexOutOfBoundsException ngay.

     Còn về chức năng thì vòng lặp while sẽ chạy y như màu xanh trong đoạn animation mô phỏng bên trên. Cứ gặp bất cứ phần tử nào lớn hơn phần tử đang xét thì dịch phần tử đó lên một đơn vị cho đến cuối cùng (kết thúc while) gặp được phần tử nhỏ nhất trong số những phần tử lớn hơn item thì thực hiện chèn item vào vị trí đó.

#3. Bình luận.

     Sắp xếp chèn cũng như sắp xếp chọn là một trong số những thuật toán sắp xếp kinh điển (biết rồi khổ quá nói mãi 😁). Về cách cài đặt và triển khi thì cũng không quá là khó khăn.

      Về độ phức tạp không gian và thời gian thì như sau. Ở đây mình cũng sẽ chưa đi vào giải thích cụ thể về khía cạnh này. Ta sẽ giành một bài riêng khi mà đã hiểu được một số thuật toán cơ bản khác nữa.

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

          - Trường hợp tốt:  O(n)

          - Trường hợp xấu: O(n^2)

     + Độ phức tạp không gian: O(1)