Giải thuật sắp xếp trộn (Merge Sort)

Giải thuật sắp xếp trộn (Merge Sort) là gì?

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Cách giải thuật sắp xếp trộn (Merge Sort) làm việc

Dưới đây là các hình minh họa cách giải thuật sắp xếp trộn làm việc. Giả sử chúng ta có mảng sau:

Giải thuật sắp xếp trộn 1

Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa. Tiến trình chia này tiếp tục diễn ra cho đến khi không còn chia được nữa và chúng ta thu được các giá trị tương ứng biểu diễn các phần tử trong mảng. Trong hình dưới, đầu tiên chúng ta chia mảng kích cỡ 8 thành hai mảng kích cỡ 4.

Giải thuật sắp xếp trộn 2

Tiến trình chia này không làm thay đổi thứ tự các phần tử trong mảng ban đầu. Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa.

Giải thuật sắp xếp trộn 3

Tiến hành chia tiếp cho tới khi không còn chia được nữa.

Giải thuật sắp xếp trộn 4

Bây giờ chúng ta tổ hợp chúng theo như đúng cách thức mà chúng được chia ra.

Đầu tiên chúng ta so sánh hai phần tử trong mỗi list và sau đó tổ hợp chúng vào trong một list khác theo cách thức đã được sắp xếp. Ví dụ, 14 và 33 là trong các vị trí đã được sắp xếp. Chúng ta so sánh 27 và 10 và trong list khác chúng ta đặt 10 ở đầu và sau đó là 27. Tương tự, chúng ta thay đổi vị trí của 19 và 35. 42 và 44 được đặt tương ứng.

Giải thuật sắp xếp trộn 5

Vòng lặp tiếp theo là để kết hợp từng cặp list một ở trên. Chúng ta so sánh các giá trị và sau đó hợp nhất chúng lại vào trong một list chứa 4 giá trị, và 4 giá trị này đều đã được sắp thứ tự.

Giải thuật sắp xếp trộn 6

Sau bước kết hợp cuối cùng, danh sách sẽ trông giống như sau:

Giải thuật sắp xếp trộn 7

Phần tiếp theo chúng ta tìm hiểu một số khía cạnh khác của giải thuật sắp xếp trộn.

Giải thuật cho Sắp xếp trộn (Merge Sort)

Giải thuật sắp xếp trộn tiếp tục tiến trình chia danh sách thành hai nửa cho tới khi không thể chia được nữa. Theo định nghĩa, một list mà chỉ có một phần tử thì list này coi như là đã được sắp xếp. Sau đó, giải thuật sắp xếp trộn kết hợp các sorted list lại với nhau để tạo thành một list mới mà cũng đã được sắp xếp.

Bước 1: Nếu chỉ có một phần tử trong list thì list này được xem như là đã được sắp xếp. Trả về list hay giá trị nào đó. Bước 2: Chia list một cách đệ qui thành hai nửa cho tới khi không thể chia được nữa. Bước 3: Kết hợp các list nhỏ hơn (đã qua sắp xếp) thành list mới (cũng đã được sắp xếp).

Giải thuật mẫu cho Sắp xếp trộn (Merge Sort)

Có thể nói rằng với giải thuật sắp xếp trộn, bạn cần chú ý hai điểm chính: chia và hợp.

Bởi vì giải thuật sắp xếp trộn làm việc theo phương thức đệ qui nên phần triển khai giải thuật chúng ta cũng nên sử dụng đệ qui để biểu diễn.

Bt đầu gii thut sp xếp trn mergesort( biến a là mt mng ) if ( n == 1 ) return a khai báo biến l1 là mt mng = a[0] ... a[n/2] khai báo biến l2 là mt mng = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) // gọi hàm merge() Kết thúc gii thut Bt đầu hàm merge( Mng a, mng b ) khai báo biến c là mt mng while ( a và b có phn t ) if ( a[0] > b[0] ) Thêm b[0] vào cui mng c Xóa b[0] t b else Thêm a[0] vào cui mng c Xóa a[0] t a kết thúc if kết thúc while while ( a có phn t ) Thêm a[0] vào cui mng c Xóa a[0] t a kết thúc while while ( b có phn t ) Thêm b[0] vào cui mng c Xóa b[0] t b kết thúc while return c Kết thúc hàm

Theo Tutorialspoint

Bài trước: Giải thuật sắp xếp chọn (Selection Sort)

Bài tiếp: Shell Sort trong cấu trúc dữ liệu và giải thuật

Thứ Tư, 15/08/2018 15:20
52 👨 373