Trong bài viết này, chúng ta nói về thuật toán sắp xếp hợp nhất. Chúng ta sẽ xem một số ví dụ trực quan để giúp hiểu thuật toán và sau đó triển khai nó bằng mã Java và Python.
Thuật toán sắp xếp hợp nhất là gì?
Thuật toán sắp xếp hợp nhất là một thuật toán sắp xếp hiệu quả dựa trên phân chia và chinh phục thuật toán. Nó chia một tập hợp (mảng) các phần tử thành các đơn vị đơn lẻ và sau đó hợp nhất chúng một cách có trật tự.
Hãy xem một ví dụ để hiểu cách sắp xếp hợp nhất hoạt động.
Chúng ta sẽ sử dụng thuật toán sắp xếp hợp nhất để sắp xếp dãy số này: 4, 10, 6, 14, 2, 1, 8, 5
Đây là một hình ảnh để cho bạn thấy quá trình “phân chia”:
Mảng đầu tiên được chia thành hai mảng riêng biệt. Sau đó, những mảng đó cũng được chia. Sự phân chia này tiếp tục cho đến khi tất cả các phần tử trong mảng trở thành một đơn vị.
Sau giai đoạn này, quá trình hợp nhất bắt đầu. Đây là cách điều đó xảy ra:
Các phần tử đang được tập hợp lại thành các mảng nhưng lần này theo thứ tự được sắp xếp. Cũng giống như cách chúng bị tách ra, chúng đang được hợp nhất.
Trước khi chúng tôi triển khai thuật toán này bằng mã, bạn nên hiểu cách chúng tôi có thể thu thập các phần tử này theo thứ tự đã sắp xếp.
Chúng ta sẽ sử dụng phần mà chúng ta đã nhóm lại các phần tử thành hai mảng riêng biệt – 4, 6, 10, 14 và 1, 2, 5, 8. Đây là một minh họa để hiểu cách chúng ta đến mảng cuối cùng:
Như có thể thấy ở trên, chúng ta có hai mũi tên chỉ đến chỉ mục đầu tiên của cả hai mảng. Một so sánh sẽ được thực hiện để tìm ra chỉ số nào nhỏ hơn. Trong trường hợp của chúng tôi, 1 nhỏ hơn 4 nên sẽ được đẩy vào mảng đã hợp nhất. Sau đó, mũi tên màu đỏ sẽ di chuyển đến chỉ mục tiếp theo. Đó là:
Một phép so sánh khác sẽ được thực hiện: có phải 2 < 4 không?
2 nhỏ hơn 4, vì vậy nó sẽ được đẩy vào mảng đã hợp nhất và mũi tên di chuyển đến chỉ mục tiếp theo.
Đối với so sánh tiếp theo:
4 nhỏ hơn 5, vì vậy 4 sẽ được đẩy vào mảng đã hợp nhất và mũi tên màu lục lam sẽ chuyển sang chỉ mục tiếp theo.
Quá trình so sánh này sẽ tiếp tục cho đến khi mảng được hợp nhất được lấp đầy. Nếu đến thời điểm mà một mảng trở nên trống, thì mảng có các phần tử còn lại sẽ được sao chép vào mảng đã hợp nhất theo thứ tự đã sắp xếp.
Hãy xem một số ví dụ mã!
Ví dụ sắp xếp hợp nhất trong Java
Nếu chúng ta muốn triển khai sắp xếp hợp nhất với Java, đây là giao diện:
public class MergeSort {
public static void main(String[] args) {
int[] numbers = {4, 10, 6, 14, 2, 1, 8, 5};
mergeSort(numbers);
System.out.println("Sorted array:");
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
}
private static void mergeSort(int[] inputArray) {
int arrayLength = inputArray.length;
if (arrayLength < 2) {
return;
}
int midPoint = arrayLength / 2;
int[] leftArray = new int[midPoint];
int[] rightArray = new int[arrayLength - midPoint];
for (int i = 0; i < midPoint; i++) {
leftArray[i] = inputArray[i];
}
for (int i = midPoint; i < arrayLength; i++) {
rightArray[i - midPoint] = inputArray[i];
}
mergeSort(leftArray);
mergeSort(rightArray);
merge(inputArray, leftArray, rightArray);
}
private static void merge (int[] inputArray, int[] leftArray, int[] rightArray) {
int leftArrayLength = leftArray.length;
int rightArrayLength = rightArray.length;
int x = 0;
int y = 0;
int z = 0;
while (x < leftArrayLength && y < rightArrayLength) {
if (leftArray[x] <= rightArray[y]) {
inputArray[z] = leftArray[x];
x++;
}
else {
inputArray[z] = rightArray[y];
y++;
}
z++;
}
while (x < leftArrayLength) {
inputArray[z] = leftArray[x];
x++;
z++;
}
while (y < rightArrayLength) {
inputArray[z] = rightArray[y];
y++;
z++;
}
}
}
Hãy chia nhỏ mã.
public static void main(String[] args) {
int[] numbers = {4, 10, 6, 14, 2, 1, 8, 5};
// 1, 2, 4, 5, 6, 8, 10, 14
mergeSort(numbers);
System.out.println("Sorted array:");
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
}Ở trên, chúng tôi đã tạo mảng số của mình. Sau đó, chúng tôi đã gọi cho mergeSort phương pháp sắp xếp các số. Sau đó, chúng tôi lặp qua mảng các số đã sắp xếp và in chúng ra bàn điều khiển.
private static void mergeSort(int[] inputArray) {
int arrayLength = inputArray.length;
if (arrayLength < 2) {
return;
}
int midPoint = arrayLength / 2;
int[] leftArray = new int[midPoint];
int[] rightArray = new int[arrayLength - midPoint];
for (int i = 0; i < midPoint; i++) {
leftArray[i] = inputArray[i];
}
for (int i = midPoint; i < arrayLength; i++) {
rightArray[i - midPoint] = inputArray[i];
}
mergeSort(leftArray);
mergeSort(rightArray);
merge(inputArray, leftArray, rightArray);
}Chúng tôi có điểm giữa của mảng bằng cách chia chiều dài mảng cho hai. Mảng bên trái bắt đầu từ chỉ mục đầu tiên đến điểm giữa trong khi mảng bên phải bắt đầu từ chỉ mục sau điểm giữa đến điểm kết thúc của mảng.
Sau đó, chúng tôi tạo hai vòng lặp để sao chép các phần tử vào mảng bên trái và bên phải tùy thuộc vào vị trí của các phần tử. Sau đó chúng tôi đã gọi mergeSort phương pháp trên mảng bên trái và bên phải. Điều này sẽ tiếp tục chia nhỏ mảng theo cách đệ quy cho đến khi các mảng được giảm xuống thành các đơn vị đơn lẻ (giống như chúng ta đã thấy trong các hình ảnh ở phần trước).
Cuối cùng, chúng tôi đã gọi merge phương thức hợp nhất các mảng thành một mảng theo thứ tự đã sắp xếp. Chúng ta hãy xem logic được sử dụng trong merge phương pháp.
private static void merge (int[] inputArray, int[] leftArray, int[] rightArray) {
int leftArrayLength = leftArray.length;
int rightArrayLength = rightArray.length;
int x = 0;
int y = 0;
int z = 0;
while (x < leftArrayLength && y < rightArrayLength) {
if (leftArray[x] <= rightArray[y]) {
inputArray[z] = leftArray[x];
x++;
}
else {
inputArray[z] = rightArray[y];
y++;
}
z++;
}
while (x < leftArrayLength) {
inputArray[z] = leftArray[x];
x++;
z++;
}
while (y < rightArrayLength) {
inputArray[z] = rightArray[y];
y++;
z++;
}
}
Nhớ các mũi tên từ các hình ảnh trong phần trước? Chúng tôi đã biểu thị chúng ở đây bằng cách sử dụng x và y sau đó z đối với mảng đã hợp nhất, nơi các số sẽ được đẩy vào theo thứ tự đã sắp xếp.
Các vòng lặp while được sử dụng để so sánh trên cả hai mảng và thay đổi vị trí của x, y và z khi các phần tử được đẩy vào mảng đã hợp nhất.
Ví dụ sắp xếp chèn trong Python
def mergeSort(array):
if len(array) > 1:
midPoint = len(array)//2
leftArray = array[:midPoint]
rightArray = array[midPoint:]
mergeSort(leftArray)
mergeSort(rightArray)
x = 0
y = 0
z = 0
while x < len(leftArray) and y < len(rightArray):
if leftArray[x] < rightArray[y]:
array[z] = leftArray[x]
x += 1
else:
array[z] = rightArray[y]
y += 1
z += 1
while x < len(leftArray):
array[z] = leftArray[x]
x += 1
z += 1
while y < len(rightArray):
array[z] = rightArray[y]
y += 1
z += 1
def printSortedArray(array):
for i in range(len(array)):
print(array[i], end=" ")
print()
if __name__ == '__main__':
numbers = [4, 10, 6, 14, 2, 1, 8, 5]
mergeSort(numbers)
print("Sorted array: ")
printSortedArray(numbers)Logic ở đây hoàn toàn giống như trong phần trước. Ở trên, chúng tôi đã triển khai thuật toán sắp xếp hợp nhất bằng Python. Bạn có thể tìm thấy lời giải thích về cách hoạt động của mã trong phần cuối cùng.
Độ phức tạp về thời gian của sắp xếp hợp nhất là O(n*Log n) cho mọi trường hợp (tốt nhất, trung bình và xấu nhất).
Phần kết luận
Trong bài viết này, chúng ta đã tìm hiểu cách thức hoạt động của thuật toán sắp xếp hợp nhất. Sau đó, chúng tôi đã xem một số ví dụ và cách áp dụng nó trong mã Java và Python của chúng tôi.
Chúc mừng mã hóa!
