 |
| Sắp xếp chèn (insertion sort) |
Để hình dung rõ hơn, ta xét với vị dụ sau đây, cho danh sách a và thực hiện thuật toán sắp xếp chèn trên nó:
a=[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]
Ý tưởng của thuật toán thực sự rất đơn giản. Giả sử các phần tử từ 1 đến i-1 đã được sắp xếp. Bây giờ, ta xét đến phần tử thứ i để cho các phần tử từ 1 đến i được sắp xếp thì ta phải tìm một vị trí phù hợp để đặt i vào đó. Để tìm được vị trí đó ta làm như sau:
- Đặt t = a[i], việc này chỉ là lưu trữ tạm thời
- Nếu a[i-1] > t thì đăt a[i] = a[i-1] và chuyển sang bước 3,ngược lại thì kết thúc thuật toán vì đã đúng thứ tự sẵn rồi.
- Lại kiểm tra nếu a[i-2] > t thì đặt a[i-1] = a[i-2] và chuyển sang bước tiếp, ngược lại thì đặt a[i-1]=t và kết thúc thuật toán .
- Bước 3 được lặp lại cho đến khi tìm được vị trí thích hợp và kết thuc thuật toán hoặc chuyển đến đầu danh sách.
Nói một cách đơn giản, nếu muốn sắp phần tử i vào đúng vị trí, ta nhấc nó lên (tức là đặt t = a[i]) và dịch chuyển các phần tử từ trái sang phải 1 vị trí bắt đầu từ vị trí i-1 cho đến khi tìm được vị trí thích hợp hoặc cho đến đầu dãy (vị trí 1).
Vậy, với danh sách a như trên, các bước cần làm là:
a=[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]
- Ta thấy, xét phần tử đầu tiên, nếu danh sách chỉ có 1 phần tử thì hiển nhiên là nó được xắp xếp rồi. Chính vì thế ta quan tâm phần tử thứ 2 (6) trở đi.
- Xét phần tử thứ hai (6) lớn hơn phần tử thứ nhất (3) nên ta không làm gì cả và chuyển sang phần tử tiếp theo.
- Xét phần tử thứ ba (9) lớn hơn phần tử thứ hai (6) nên không làm gì, chuyển sang phần tử tiếp theo.
- Phần tử thứ tư (2) nhỏ hơn phần tử thứ ba (9) nên ta cần phải đổi chỗ. Đặt t = a[4] = 2, lúc này ta sẽ dịch các phần tử thứ ba, thứ hai và thứ nhất sang phải một đơn vị và đặt a[1] = t. Danh sách lúc này sẽ là:
a=[2, 3, 6, 9, 6, 8, 9, 1, 7, 21, 7, 12] - Xét tiếp phần tử thứ năm (6) nhỏ hơn phần tử thứ tư (9) nhưng bằng phần tử thứ ba (6) nên ta chỉ cần dịch chuyển phần tử thứ tư (9) mà thôi. Lúc này danh sách a sẽ như sau:
a=[2, 3, 6, 6, 9, 8, 9, 1, 7, 21, 7, 12] - Bây giờ ta xét phần tử thứ sáu (8) nhỏ hơn phần tử thứ năm và lớn hơn phần tử thứ từ nên chỉ có một phần tử cần dịch chuyển và danh sách lúc này sẽ là:
a=[2, 3, 6, 6, 8, 9, 9, 1, 7, 21, 7, 12] - Xét tiếp phần tử thứ bảy (9) bằng phần tử thứ sau (9) nên không cần làm gì và chuyển bước tiếp.
- Lúc này phần tử thứ tám (1) nhỏ hơn các phần tử thứ bảy, sáu,... nhất lên ta sẽ dịch chuyển tất cả các phần tử thứ thứ bảy đến thứ nhất sang phải một vị trí và danh sách lúc này sẽ như sau:
a=[1, 2, 3, 6, 6, 8, 9, 9, 7, 21, 7, 12] - Ta xét tiếp phần tử thứ chín (7) nhỏ hơn các phần tử thứ tám (9), thứ bảy(9) và thứ sáu(8) nhưng lớn hơn phần tử thứ năm (6), vì vậy ta dịch chuyển ba phần tử thứ tám, bảy và sáu. Trạng thái lúc này của danh sách là:
a=[1, 2, 3, 6, 6, 7, 8, 9, 9, 21, 7, 12] - Phần tử thứ mười (21) lớn hơn phần tử thứ chính (9) nên không có thay đổi gì cả, ta xem xét bước tiếp theo.
- Phần tử thứ mười một (7) nhỏ hơn phần tử thứ mười, chín, tám và bảy nhưng bằng phần tử thứ sáu. Vì vậy ta di chuyển bốn phần tử đứng trước phần tử thứ mười một và danh sách như sau:
a=[1, 2, 3, 6, 6, 7, 7, 8, 9, 9, 21, 12] - Ta xét phần tử cuối cùng là phần tử thứ mười hai (12) nhỏ hơn phần tử thứ mười một (21) nhưng lớn nhơn phần tử thứ mười (9). Vì vậy, chỉ cần dịch chuyển phần tử thứ mười một mà thôi. Danh sách lúc này là:
a=[1, 2, 3, 6, 6, 7, 7, 8, 9, 9, 12, 21]
Vậy là a đã được sắp xếp. Thuật toán kết thúc.
Ta thấy cần có hai vòng lặp cho thuật toán này, vòng lặp thứ nhất xét từng thuật toán và vòng lặp thứ hai dịch chuyển các phần tử để chọn vị trí phù hợp. Sau đây là code ví dụ của thuật toán:
Python code:
C code (phiên bản con trỏ):
Cải tiến, ta thấy rằng để chọn vị trí thích hợp thì ở vòng lặp bên trong ta sẽ dịch chuyển các phần tử lớn hơn sang phải một vị trí để tìm vị trí thích hợp. Trong các cấu trúc mà không cần phải dịch chuyển các phần tử (như mảng trong c hay danh sách trong python) mà chỉ cần tìm vị trí phù hợp và chèn phần tử đang xem xét vào thì chúng ta có thể áp dụng kỹ thuật tìm kiếm nhị phần (vị đoạn từ 1 đến i-1 đã được sắp xếp rồi). Kỹ thuật tìm kiếm nhị phân sẽ giảm thời gian tìm kiếm đi rất nhiều nên sẽ thuật toán sẽ được tăng tốc đãng kể. Phần này sẽ dành cho bạn tự thực hành nhé.
Không có nhận xét nào:
Đăng nhận xét