Sắp xếp chèn (Insertion Sort) phỏng theo cách làm của người chơi bài khi cần "chèn" thêm một con bài vào bộ bài đã được sắp xếp.
Để chèn 7, ta cần tạo chỗ trống cho nó bằng việc dịch chuyển đầu tiên là 5 và sau đó là 9.
Sắp xếp chèn là một thuật toán sắp xếp đơn giản hoạt động tương tự như cách bạn sắp xếp các thẻ chơi trong tay của mình. Mảng hầu như được chia thành một phần được sắp xếp và một phần chưa được sắp xếp. Các giá trị từ phần chưa được sắp xếp sẽ được chọn và đặt ở vị trí chính xác trong phần được sắp xếp.
Thuật toán tổng quát:
Giả sử chúng ta cần sắp xếp mảng có n phần tử, thì ta sẽ cần làm các bước cơ bản sau:
Bước 1: Thực hiện vòng lặp để duyệt qua mảng, k chạy từ 1 tới nLưu ý:
k=2 là phần tử thứ 2 trong mảng - tương đương với index = 1 trong array khi code ,
k=n là phần tử thứ n trong mảng - tương đương với index = n-1 trong array khi code.
Bước 2: Tại bước k = 1, 3, 4,..., n, ta đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần tử đầu tiên
- Để tìm được vị trí đúng cho phần tử đó, ta cần so sánh nó với các phần tử tiền nhiệm của nó.
- Nếu phần tử chính nhỏ hơn (xét nhỏ hơn nếu sắp xếp tăng dần - nếu giảm dần thì xét lớn hơn) phần tử trước đó, thì ta tiến hành di chuyển phần tử lớn hơn lên một vị trí để tạo khoảng trống cho phần tử được hoán đổi.
Ví dụ: Ta cần sắp mảng sau gồm các phần tử 4 3 2 10 12 1 5 6
Một ví dụ khác: Ta cần sắp xếp mảng gồm các phần tử 12 11 13 5 6
12 , 11, 13, 5, 6
Chúng ta hãy lặp cho i = 1 (phần tử thứ hai của mảng) đến 4 (phần tử cuối cùng của mảng)
i = 1. Vì 11 nhỏ hơn 12, hãy di chuyển 12 và chèn 11 trước 12
11, 12 , 13, 5, 6
i = 2. 13 sẽ vẫn ở vị trí của nó vì tất cả các phần tử trong A [0..I-1] đều nhỏ hơn 13
11, 12, 13 , 5, 6
i = 3. 5 sẽ di chuyển về đầu và tất cả các phần tử khác từ 11 đến 13 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng.
5, 11, 12, 13 , 6
i = 4. 6 sẽ di chuyển đến vị trí sau 5, và các phần tử từ 11 đến 13 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng.
5, 6, 11, 12, 13
Ví dụ sắp xếp chèn trong C++
Hàm sắp xếp chèn
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, j, last;
for (i = 1; i < n; i++)
{
last = arr[i];
j = i;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j > 0 && arr[j-1] > last)
{
arr[j] = arr[j-1];
j = j - 1;
}
arr[j] = last;
}
}
Chứng minh tính đúng đắn của sắp xếp chèn
Bổ đề: Sau lần lặp i (từ 1 đến n), các phần tử từ 0 đến i là được sắp xếp theo thứ tự.
Chứng minh: Quy nạp theo i.
Base case: Khi i =1, dãy gồm một phần tử a[1] là dãy được sắp.
Inductive step: Giả sử sau lần lặp i-1(i>1), dãy a[1], ...,a[i-1] là được sắp theo thứ tự.
Ở lần lặp thứ i ta sẽ xếp phần tử mới a[i] (được gán vào last) vào đúng chỗ của nó trong dãy gồm i phần tử đầu tiên. Để ý rằng ta gán a[j] bằng a[j-1] nếu a[j-1] lớn hơn phần tử mới (last). Sau đó ta tiếp tục di chuyển sang trái, cho đến khi gặp phần tử đầu tiên nhỏ hơn last (a[j-1] <= last).
Theo giả thiết quy nạp, đoạn gồm i-1 phần tử đầu được sắp theo thứ tự, còn theo lập luận vừa nêu thì phần tử mới thêm vào được xếp đúng chỗ, vì thế dãy thu được là được sắp theo thứ t.
Bổ đề được chứng minh.
Các đặc tính của Insertion Sort
- Sắp xếp chèn là tại chỗ và ổn định (In Place and Stable)
- Phân tích thời gian của thuật toán:
+ Best Case: 0 hoán đổi, n-1 so sánh (khi dãy đầu vào có thứ tự ngược lại với thứ tự cần sắp xếp).
+ Worst Case: 
/2 hoán đổi và so sánh
+ Average Case: 
/4 hoán đổi và so sánh.
- Thuật toán này có thời gian tính trong thì huống tốt nhất là tốt nhất
- Là thuật toán sắp xếp tốt đối với dãy đã gần được sắp xếp, nghĩa là mỗi phần tử đã đứng ở vị trí rất gần vị trí trong thứ tự cần sắp xếp.
إرسال تعليق