Merge sort là một kỹ thuật sắp xếp dựa trên kỹ thuật chia và chinh phục. Nó có độ phức tạp thời gian trong trường hợp xấu nhất là Ο (n log n). Nhưng điều này đi kèm với một chi phí tăng thêm về không gian vì thuật toán này chiếm thêm O (n) bộ nhớ.
Bây giờ chúng ta hãy xem cách chúng ta sẽ triển khai thuật toán này. Chúng tôi sẽ tạo 2 chức năng, mergeSort và merge.
hợp nhất - hàm này nhận 2 đối số, đây là 2 mảng từng phần mà sau đó nối thành một mảng bằng cách chèn các phần tử theo đúng thứ tự.
mergeSort - Hàm này gọi đệ quy mergeSort ở nửa bên trái và bên phải của mảng và sau đó sử dụng merge để kết hợp các phần của mảng này lại với nhau. Điều này sẽ rõ ràng hơn nhiều khi chúng ta xem xét việc triển khai.
Hãy bắt đầu với chức năng hợp nhất và đi sâu ngay vào mã -
Ví dụ
Hàmfunction merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
} Hàm này sẽ nhận 2 mảng đã sắp xếp và hợp nhất chúng trong thời gian O (n) sao cho chúng vẫn được sắp xếp như một mảng lớn hơn. Tham khảo các bình luận mã để giải thích sâu hơn về phương pháp. Bạn có thể kiểm tra điều này bằng cách sử dụng -
Ví dụ
let a1 = [1, 2, 3, 5] let a2 = [4, 6, 8, 9] console.log(merge(a1, a2))
Đầu ra
[1, 2, 3, 4, 5, 8, 9]
Bây giờ chúng ta sẽ sử dụng hàm này trong hàm hợp nhất của chúng ta để thực sự sắp xếp toàn bộ mảng.
Chúng ta sẽ tạo một hàm bên trong cho mergeSort mà chúng ta sẽ bọc bằng một hàm bên ngoài để làm cho bộ so sánh của chúng ta khả dụng để hàm của chúng ta có thể mở rộng được. Chúng ta hãy xem xét chức năng bên trong này -
Ví dụ
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
// Create an array from 0 to mid - 1 elements
let left = arr.slice(0, mid);
// Create an array from mid to the last element
let right = arr.slice(mid);
// Sort the left half, sort the right half,
// merge the sorted arrays and return
return merge(mergeSortInner(left), mergeSortInner(right));
} Hàm này chia một mảng thành hai, sắp xếp chúng riêng lẻ và sau đó trả về một mảng đã hợp nhất.
Hãy để chúng tôi xem mã hoàn chỉnh với một bài kiểm tra -
Ví dụ
function mergeSort(arr, compare = (a, b) => a < b) {
function merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSortInner(left), mergeSortInner(right));
}
// Call inner mergesort to sort and return the array for us.
return mergeSortInner(arr);
}
You can test this using:
let arr = [5, 8, 9, 12, -8, 31, 2];
// Sort Array elements in increasing order
arr = mergeSort(arr);
console.log(arr);
// Sort Array elements in decreasing order
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);
arr = [
{
name: "Harry",
age: 20
},
{
name: "Jacob",
age: 25
},
{
name: "Mary",
age: 12
}
];
// Sort Array elements in increasing order alphabetically by names
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// Sort Array elements in decreasing order of ages
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr); Đầu ra
[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 },
{ name: 'Mary', age: 12 }
]
[
{ name: 'Mary', age: 12 },
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 }
] Sắp xếp nhanh
Sắp xếp nhanh là một thuật toán sắp xếp hiệu quả cao và dựa trên việc phân chia mảng dữ liệu thành các mảng nhỏ hơn. Một mảng lớn được phân vùng thành hai mảng, một mảng chứa các giá trị nhỏ hơn giá trị được chỉ định, chẳng hạn như pivot, dựa vào đó phân vùng được tạo ra và một mảng khác chứa các giá trị lớn hơn giá trị pivot.
Sắp xếp nhanh phân vùng một mảng và sau đó gọi chính nó đệ quy hai lần để sắp xếp hai mảng con kết quả. Thuật toán này khá hiệu quả đối với các tập dữ liệu có kích thước lớn vì độ phức tạp trung bình và trường hợp xấu nhất của nó là Ο (n2), trong đó n là số lượng mục.
Quy trình phân vùng
Biểu diễn động sau giải thích cách tìm giá trị tổng hợp trong một mảng. Https://www.tutorialspoint.com/data_structures_algorithm/images/quick_sort_partition_animation.gif
Giá trị pivot chia danh sách thành hai phần. Và một cách đệ quy, chúng tôi tìm tổng hợp cho mỗi danh sách con cho đến khi tất cả các danh sách chỉ chứa một phần tử.
Những gì chúng ta làm trong phân vùng là chúng ta chọn phần tử đầu tiên từ mảng (các phần tử ngẫu nhiên theo kiểu sắp xếp nhanh ngẫu nhiên) và sau đó so sánh phần còn lại của mảng với phần tử này. Sau đó, chúng tôi di chuyển tất cả các phần tử nhỏ hơn phần tử này sang phía bên trái của cái mà chúng tôi gọi là chỉ số tổng hợp và các giá trị lớn hơn phần tử này sang phía bên phải của chỉ số tổng hợp. Vì vậy, khi chúng tôi đến cuối, phần tử pivot (phần tử đầu tiên) được đặt vào đúng vị trí của nó.
Điều này là do tất cả các phần tử lớn hơn nó ở bên phải và nhỏ hơn nó ở bên trái để lại phần tử này ở đúng vị trí. Chúng tôi mở rộng quy trình phân vùng này để giúp chúng tôi sắp xếp bằng cách gọi đệ quy phân vùng trên các mảng con bên trái và bên phải.
Chúng ta có thể triển khai chức năng phân vùng như sau -
Ví dụ
Phân vùng hàmfunction partition(arr, low, high, compare) {
let pivotIndex = low + 1;
for (let i = pivotIndex; i < high; i++) {
if (compare(arr[i], arr[low])) {
// Swap the number less than the pivot
swap(arr, i, pivotIndex);
pivotIndex += 1;
}
}
// Place the pivot to its correct position
swap(arr, pivotIndex - 1, low);
// Return pivot's position
return pivotIndex - 1;
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
You can test the partition function using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr); Đầu ra
4 [ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]
Lưu ý rằng các phần tử ở bên trái của 5 nhỏ hơn 5 và ở bên phải của nó lớn hơn 5. Chúng tôi cũng thấy rằng chỉ số của 5 là 4.
Bây giờ chúng ta hãy xem cách sắp xếp nhanh hoạt động như thế nào -
Nếu chúng ta có một cửa sổ lớn hơn 1 phần tử, chúng ta gọi phân vùng trên mảng từ thấp đến cao, lấy chỉ mục trả về và sử dụng nó để gọi quicksort ở nửa bên trái và bên phải của mảng.
Ví dụ
function QuickSort(arr, low, high, compare = (l, r) => l < r) {
if (high - low > 0) {
// Partition the array
let mid = partition(arr, low, high, compare);
// Recursively sort the left half
QuickSort(arr, low, mid, compare);
// Recursively sort the right half
QuickSort(arr, mid + 1, high, compare);
}
}
You can test this using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr); Đầu ra
[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]