Data Structure & Algorithm - Sort Algorithms - Merge sort
Merge Sort là gì?
Merge Sort là một thuật toán sắp xếp dựa trên phương pháp "chia để trị". Nó hoạt động bằng cách chia một mảng thành các phần con nhỏ hơn, sắp xếp từng phần con, sau đó ghép chúng lại với nhau để tạo ra mảng đã được sắp xếp cuối cùng.
Đây là một thuật toán đệ quy, chia mảng thành hai nửa cho đến khi chỉ còn một phần tử (một mảng với một phần tử luôn được coi là đã được sắp xếp). Sau đó, các phần con đã được sắp xếp sẽ được ghép lại thành một mảng đã được sắp xếp.
Merge Sort hoạt động như thế nào?
Giả sử chúng ta có một mảng sau: 5, 3, 1, 4, 2
Bước 1: Chia mảng thành hai nửa nhỏ hơn.
- Mảng 1:
5, 3, 1 - Mảng 2:
4, 2
Bước 2: Tiếp tục chia các mảng này thành hai nửa nhỏ hơn.
- Mảng 1.1:
5, 3 - Mảng 1.2:
1 - Mảng 2.1:
4 - Mảng 2.2:
2
Bước 3: Tiếp tục chia các mảng này thành hai nửa nhỏ hơn cho đến khi chúng chỉ chứa một phần tử.
- Mảng 1.1.1:
5 - Mảng 1.1.2:
3 - Mảng 1.2:
1 - Mảng 2.1.1:
4 - Mảng 2.2:
2
Bước 4: Khởi tạo quá trình ghép lại.
- Ghép mảng 1.1.1 và 1.1.2:
3, 5 - Ghép mảng 1.2:
1 - Ghép mảng 2.1.1 và 2.2:
2, 4
Bước 5: Ghép các mảng đã được sắp xếp lại với nhau.
- Ghép mảng 1.1 (3, 5) và 1.2 (1):
1, 3, 5 - Ghép mảng 2.1 (2, 4):
2, 4
Bước 6: Cuối cùng, ghép các mảng đã được sắp xếp lại với nhau: 1, 2, 3, 4, 5
Vậy, mảng ban đầu 5, 3, 1, 4, 2 đã được sắp xếp thành 1, 2, 3, 4, 5
Cách cài đặt Merge Sort
Đầu tiên, hãy tạo hàm merge() để ghép hai mảng đã được sắp xếp thành một mảng đã được sắp xếp:
function merge(arr1, arr2) {
let i = 0;
let j = 0;
let results = [];
while(i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j])
j++
}
}
while(i < arr1.length){
results.push(arr1[i]);
i++;
}
while(j < arr2.length){
results.push(arr2[j]);
j++;
}
return results;
}
Tiếp theo, tạo hàm mergeSort() để chia mảng thành hai nửa và gọi hàm merge() để ghép chúng lại:
function mergeSort(arr){
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
Ứng dụng của Merge Sort
Thuật toán Merge Sort có nhiều ứng dụng trong các lĩnh vực khác nhau. Dưới đây là một số ví dụ:
- Sắp xếp dữ liệu: Merge Sort là một thuật toán sắp xếp hiệu quả, có thể được sử dụng để sắp xếp các mảng, danh sách hoặc bất kỳ tập hợp dữ liệu nào khác có thể được biểu diễn dưới dạng một chuỗi.
- Xử lý dữ liệu: Merge Sort thường được sử dụng trong các hệ thống xử lý dữ liệu, nơi mà dữ liệu cần được sắp xếp trước khi được xử lý. Ví dụ, nó có thể được sử dụng để sắp xếp các bản ghi trong một cơ sở dữ liệu.
- Phân tích dữ liệu: Trong phân tích dữ liệu, Merge Sort có thể được sử dụng để sắp xếp các dữ liệu để tìm kiếm các mẫu hoặc xác định các quan hệ giữa các dữ liệu.
- Đồ thị và mạng máy tính: Trong các lĩnh vực như đồ thị và mạng máy tính, Merge Sort có thể được sử dụng để sắp xếp các nút hoặc các đỉnh trong một đồ thị hoặc mạng máy tính.
- Trong lập trình: Merge Sort cũng được sử dụng rộng rãi trong lập trình để sắp xếp mảng của các đối tượng hoặc các phần tử dữ liệu.
Nguồn tham khảo:
All rights reserved
