HomeLập trìnhPythonHợp nhất thuật...

Hợp nhất thuật toán sắp xếp – Các ví dụ về Python và Java với độ phức tạp về thời gian


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”:

hợp nhất-sắp xếp-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:

hợp nhất-sắp xếp-hợp nhất

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:

Đọc thêm  Python Slicing – Cách cắt một mảng và tác dụng của nó [::-1] Bần tiện?
hợp nhất-sắp xếp-mũi tên

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à:

hợp nhất-sắp xếp-mũi tên2

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:

hợp nhất-sắp xếp-mũi tên3

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.

Đọc thêm  Sê-ri và DataFrame trong Python

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 xy 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, yz khi các phần tử được đẩy vào mảng đã hợp nhất.

Đọc thêm  Lập trình hướng đối tượng trong Python

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!



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status