NỘI DUNG BÀI VIẾT
Giới thiệu
Thuật toán sắp xếp trộn (Merge Sort) là thuật toán sắp xếp phổ biến nhất dựa trên nguyên tắc của Thuật toán chia để trị.
Ở đây, một bài toán được chia thành nhiều bài toán con. Mỗi bài toán con được giải quyết riêng lẻ. Cuối cùng, các đáp án của bài toán con được kết hợp để tạo thành đáp án cuối cùng.
Thuật toán chia để trị
Sử dụng thuật toán chia để trị, chúng ta chia một bài toán thành các bài toán con. Khi lời giải cho mỗi bài toán con đã sẵn sàng, chúng ta ‘kết hợp’ kết quả từ các bài toán con để giải bài toán chính.
Giả sử chúng ta phải sắp xếp một mảng A. Một bài toán con sẽ là sắp xếp một phần con của mảng này bắt đầu từ chỉ mục p và kết thúc ở chỉ mục r, được ký hiệu là A[p..r].
Chia
Nếu q nằm giữa p và r thì chúng ta có thể tách mảng con A[p..r] thành hai mảng A [p..q] và A[q + 1, r].
Trị
Trong bước trị, chúng ta cố gắng sắp xếp cả hai mảng con A [p..q] và A[q + 1, r]. Chúng ta chia cả hai mảng con này cho đến khi không thể chia được nữa thì dừng và tiến hành sắp xếp các phần tử.
Kết hợp
Khi bước trị đạt đến trường hợp tổng quát, chúng ta nhận được hai mảng con được sắp xếp A[p..q] và A[q + 1, r] của mảng A[p..r], chúng ta kết hợp các kết quả bằng cách tạo một mảng được sắp xếp A[p..r] từ hai mảng con được sắp xếp A[p..q] và A[q + 1, r].
Thuật toán sắp xếp trộn
Hàm MergeSort chia mảng thành hai nửa cho đến khi chúng không thể chia nhỏ được nữa.
Sau đó, hàm sẽ kết hợp các mảng con đã được sắp xếp vào thành 1 mảng cho đến khi tất cả các mảng đã được kết hợp.
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)Code language: JavaScript (javascript)Để sắp xếp toàn bộ một mảng, chúng ta cần gọi MergeSort (A, 0, length(A) -1).
Như trong hình bên dưới, thuật toán sắp xếp trộn sử dụng đệ quy để chia mảng thành các nửa cho đến khi không thể chia được nữa. Sau đó, hàm hợp nhất các mảng con đã được sắp xếp và tạo thành 1 mảng hoàn chỉnh.
Các bước của thuật toán sắp xếp trộn
Mọi thuật toán đệ quy đều phụ thuộc vào trường hợp cơ sở và khả năng kết hợp các kết quả từ các trường hợp cơ sở. Sắp xếp trộn không có gì khác biệt. Phần quan trọng nhất của thuật toán chính là bước hợp nhất,
Bước hợp nhất là giải pháp cho vấn đề đơn giản là hợp nhất hai mảng đã sắp xếp để tạo thành một mảng đã được sắp xếp lớn hơn.
Thuật toán duy trì ba con trỏ, một con trỏ cho mỗi mảng trong số hai mảng và một con trỏ để duy trì chỉ mục hiện tại của mảng được sắp xếp cuối cùng.
Cài đặt thuật toán sắp xếp trộn
Nhiệm vụ của chúng ta là hợp nhất hai mảng con A[p..q] và A[q + 1..r] để tạo ra một mảng đã sắp xếp A[p..r]. Vì vậy, các đầu vào cho hàm là A, p, q và r
Hàm hợp nhất hoạt động như sau:
- Tạo bản sao của các mảng con L ← A[p..q] và M ← A[q + 1..r]
- Tạo ba con trỏ i, j và k. Trong đó:
i duy trì chỉ số hiện tại của L, bắt đầu từ 1
j duy trì chỉ số hiện tại của M, bắt đầu từ 1
k duy trì chỉ số hiện tại của A[p..q], bắt đầu từ p. - Duyệt cho đến cuối L hoặc M, chọn phần tử lớn hơn trong số các phần tử từ L và M và đặt chúng vào đúng vị trí tại A[p..q]
- Khi chúng tôi sử dụng hết các phần tử trong L hoặc M, chọn các phần tử còn lại và đưa vào A[p..q]
function merge(left, right) {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
// Pick the smaller among the smallest element of left and right sub arrays
if (left[0] < right[0]) {
function merge(left, right) {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
// Pick the smaller among the smallest element of left and right sub arrays
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
// Concatenating the leftover elements
// (in case we didn't go through the entire left or right array)
return [ ...arr, ...left, ...right ]
}
function mergeSort(array) {
const half = array.length / 2
// Base case or terminating case
if(array.length < 2){
return array
}
const left = array.splice(0, half)
return merge(mergeSort(left),mergeSort(array))
}
var arr = [3, 5, -2, 14, -9, 30];
console.log(mergeSort(arr));Code language: PHP (php)Đánh giá thuật toán sắp xếp trộn
Độ phức tạp thời gian:
- Trường hợp xấu nhất: O(n*log n)
- Trường hợp tốt nhất: O(n*log n)
- Trường hợp trung bình: O(n*log n)
Độ phức tạp không gian:
Độ phức tạp không gian của thuật toán sắp xếp trộn là O(n).
Ứng dụng của thuật toán sắp xếp trộn
Thuật toán sắp xếp trộn được sử dụng trong các trường hợp:
- Đếm nghịch đảo
- Sắp xếp ngoài mảng
- Ứng dụng thương mại điện tử
Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
