Thuật Toán Sắp Xếp Chèn - Insertion Sort Algorithm C/C++

Tìm hiểu toàn bộ về thuật toán sắp xếp chèn, insertion sort algorithm code C/C++ minh họa. Sắp xếp chèn trực tiếp, là một thuật toán cực kì hay và hữu ích đối với người học lập trình.

Mục lục bài viết

• 1. Ý tưởng thuật toán sắp xếp chèn
• 2. Giải thuật Insertion sort
• 3. Cài đặt thuật toán Insertion sort
• 4. Đánh giá thuật toán Insertion sort

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

Thuật toán sắp xếp chèn (Insertion sort) được John Mauchly đưa ra rất sớm vào năm 1946 trong cuộc hội thảo đầu tiên về thuật toán sắp xếp trên máy tính. Đây là một thuật toán sắp xếp 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.

Thuật toán sử dụng vòng lặp để duyệt từ đầu danh sách tới cuối danh sách và chèn phần tử vào đúng vị trí để phát triền thành danh sách có thứ tự đúng.

• Tại mỗi vị trí i của phần tử đang duyệt, lấy ra phần tử a[i] đó, tìm vị thích hợp trong đoạn đã xét a[0] đến a[i-1] sau đó chèn để đoạn danh sách a[0] đến a[i] trở thành danh sách có thứ tự đúng.
• Ở lần duyệt thứ i (i bắt đầu từ i, bỏ qua phần tử đầu tiên), ta có i+1 phần tử ở đầu danh sách là một danh sách có thứ tự.

Việc sắp xếp thường được thực hiện tại chỗ, bằng cách lặp lại mảng, tăng danh sách được sắp xếp đằng sau nó. Tại mỗi vị trí mảng, nó kiểm tra giá trị ở đó so với giá trị lớn nhất trong danh sách đã sắp xếp (tức là phần tử ở bên trái nó, danh sách trước nó đã được kiểm tra). Nếu lớn hơn, nó đứng tại chỗ và chuyển sang kiểm tra phần tử tiếp theo. Nếu nhỏ hơn, nó sẽ tìm vị trí chính xác trong danh sách đã sắp xếp, dịch chuyển tất cả các giá trị lớn hơn để tạo khoảng trắng và chèn vào vị trí chính xác đó.

Thuật toán sắp xếp chèn còn có một biến thể đó là chèn nhị phân ( Binary Insertion sort). Ở biến thể này, thuật toán sẽ sử dụng phương pháp tìm kiếm nhị phân để tìm vị trí chèn phù hợp cho phần tử đang duyệt. Sau đó mới tiến hành chèn.

2. Giải thuật Insertion sort

Thuật toán Insertion Sort:

Input: Mảng số nguyên a có n phần tử

Output: Mảng a sắp xếp có thứ tự

Bước 1: i = 1; // Bỏ qua phần tử đầu tiên

Bước 2: j = i;

Bước 3: a[j] = x;

• Trong khi ( j> 0 và x < a[j-1] // Tìm vị trí thích hợp cho x
• a[j]=a[j-1];
• j = j-1;
• a[j] = x;

Bước 4: i = i +1 // Lần duyệt tiếp

• Nếu i > n-1 Dừng vòng lặp, kết thúc thuật toán
• Ngược lại, quay trở về bước 2

Lưu đổ thuật toán:

Sắp xếp chèn còn có các biến thế là:

• Chèn nhị phân (Binary Insertion Sort): Sử dụng tìm kiếm nhị phân để tìm ra vị trí chèn phù hợp sau đó chènShell sort: Thuật toán sắp xếp tư tưởng giống sắp

3. Cài đặt thuật toán Insertion sort

Thuật toán sắp xếp chèn – Insertion sort cài đặt bằng C/C++

// Thuật toán sắp xếp chèn void insertionSort(int a[], int n){ int j, x; for(int i=1;i<n;i++){ x=a[i]; j=i; while(j>0 && x<a[j-1]){ a[j]=a[j-1]; j--; } a[j]=x; } }

4. Đánh giá thuật toán Insertion sort

Bảng đánh giá thuật toán:

Trường hợp	Số lần so sánh	Số lần gán	Độ phức tạp
Tốt nhất	n-1	2(n-1)	O(n)
Xấu nhất	O(n^2 )

Trung bình, thuật toán sắp xếp chèn – Insertion sort có độ  phức tạp là O(n^2 ). Trường hợp tốt nhất là với đầu vào đã được sắp xếp đúng thứ tự. Trường hợp xấu là dãy bị đảo ngược thứ tự hoàn toàn.

Ưu điểm:

• Dễ dàng cài đặt, giải thuật đơn giản dễ hiểu, phù hợp cho việc học tập và nghiên cứu
• Thuật toán có tính ổn định
• Hoạt động tốt nếu mảng cần sắp xếp nhỏ và đã được sắp xếp một phần
• Tốn ít bộ nhớ

Nhược điểm:

• Là thuật toán có độ phức tạp lớn O( ) chính vì thế không thể áp dụng với dữ liệu lớn
• Hiệu suất của thuật toán thấp, không thực sự tối ưu.

Với một số nhược điểm kể trên, thuật toán này ít được áp dụng trong thực tế, tuy nhiên nó lại cực kì hữu ích trong việc học tập và tìm hiểu các nguyên lý, thuật toán trong lập trình. Chính vì vậy bạn hãy cố gắng master nó nhé!