Thuật toán sắp xếp : INSERTION SORT và BINSERTION SORT

Ý tưởng

Xét dãy a1, a2…., an, trong đó i-1 phần tử đầu tiên a1, a2,…,an đã có thứ tự. Tìm vị trí thích hợp để chèn phần tử ai vào vị trí thích hợp trong i-1 phần tử đã sắp để có dãy mới a1, a2,…,ai trở nên có thứ tự. Vị trí này nằm giữa ak-1ak thỏa      ak-1 ai < ak (1 k < i).

 

Giải thuật

            Bước 1i = 2            // Giả sử có đoạn a[1] đã được sắp

            Bước 2x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào.

            Bước 3:  Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i].

            Bước 4a[pos] = x; // có đoạn a[1]..a[i] đã được sắp

Bước 5i = i +1;

                Nếu in : lặp lại bước 2.

                Ngược lại: Dừng

 

BINSERTION SORT

Ý tưởng

BInsertion Sort cũng tương tự như Insertion Sort, chỉ khác ở cách tìm vị trí thích hợp pos trong đoạn a[0] đến a[i-1]. Do đoạn a[0] đến a[i-1] đã có thứ tự nên ta có thể sử dụng giải thuật tìm nhị phân (Binary Search) để thực hiện việc tìm vị trí pos.

Đó là ý tưởng của BInsertion Sort – giải thuật sắp xếp chèn nhị phân.

Chủ đề liên quan
Thuật toán sắp xếp : INSERTION SORT và BINSERTION SORT

Cùng chuyên mục

Xem nhiều hôm nay