Thuật toán bố trí merge sort là một trong những thuật toán có độ phức hợp ở mức mức độ vừa phải và thuộc sử dùng phương thức chia để trị giống thuật toán thu xếp nhanh quick sort. Thuật toán này không chỉ có áp dụng trong thu xếp mà còn nghỉ ngơi nhiều câu hỏi khác. Hãy thuộc tìm tôi mày mò nhé.

Bạn đang xem: Thuật toán merge sort c++

Chào mừng các bạn quay quay lại với blog của Nguyễn Văn Hiếu. Đây là một nội dung bài viết trong series các thuật toán sắp tới xếp có minh họa code sử dụng ngữ điệu lập trình C++.

Ở bài viết này Nguyễn Văn Hiếu xin reviews tới những bạn thuật toán sắp xếp merge sort. Đây là một trong thuật toán rất sắp tới xếp rất thú vị và bao gồm độ phức hợp thấp hơn.

Lưu ý: bài viết chỉ diễn đạt cho việc sắp xếp dãy số tăng dần. Việc thu xếp dãy số bớt dần sẽ tương tự và độc giả tự tìm hiểu


NỘI DUNG BÀI VIẾT

Toggle


Ý tưởng của thuật toán merge sort

Giống như Quick sort, Merge sort là 1 trong thuật toán chia để trị. Thuật toán này phân chia mảng cần sắp xếp thành 2 nửa. Tiếp tục lặp lại bài toán này ở các nửa mảng vẫn chia. Cuối cùng gộp những nửa đó thành mảng đã sắp xếp. Hàm merge() được thực hiện để gộp nhì nửa mảng. Hàm merge(arr, l, m, r) là tiến trình đặc trưng nhất đã gộp nhì nửa mảng thành 1 mảng chuẩn bị xếp, những nửa mảng là arr và arr sau khoản thời gian gộp đã thành một mảng độc nhất đã sắp xếp.

Hãy xem ý tưởng phát minh triển khai code sau đây để gọi hơn

merge
Sort(arr<>, l, r)If r > l 1. Tra cứu chỉ số nằm trong lòng mảng để chia mảng thành 2 nửa: middle m = (l+r)/2 2. điện thoại tư vấn đệ quy hàm merge
Sort đến nửa đầu tiên: merge
Sort(arr, l, m) 3. Call đệ quy hàm merge
Sort mang đến nửa vật dụng hai: merge
Sort(arr, m+1, r) 4. Gộp 2 nửa mảng đã bố trí ở (2) cùng (3): merge(arr, l, m, r)Hình ảnh dưới trên đây từ wikipedia sẽ hiển thị cho chính mình toàn cỗ sơ đồ các bước của thuật toán merge sort cho mảng 38, 27, 43, 3, 9, 82, 10. Nếu quan sát kỹ hơn vào sơ trang bị này, chúng ta cũng có thể thấy mảng ban sơ được lặp lại hành động chia tính đến khi size các mảng sau phân tách là 1. Khi kích cỡ các mảng nhỏ là 1, quy trình gộp sẽ ban đầu thực hiện tại gộp lại các mảng này cho tới khi ngừng và chỉ từ một mảng đã sắp tới xếp.

*
Minh họa thuật toán bố trí merge sort

Cách hàm merge hoạt động khi gộp nhị mảng con

Với trường phù hợp khi 2 mảng con chỉ có một trong những phần tử, ta chỉ việc xem phần tử nào bé dại hơn và đẩy lên đầu, bộ phận còn lại để phía sau. Do vậy, các mảng con yêu cầu gộp lại có tính chất luôn luôn được sắp tăng dần.

Giả sử ta tất cả 2 mảng nhỏ lần lượt là:arr1 = <1 9 10 10> , n1 = 4 // chiều dài của mảng conarr2 = <3 5 7 9>, n2 = 4sort_arr = <> // Mảng lưu giữ lại quá trình gộp
Khởi chế tạo i = 0, j = 0 tương xứng là chỉ số bước đầu của arr1 và arr2Xét thấy arr1 chèn arr1 vào thời điểm cuối mảng sort_arr, tăng i lên 1 đối chọi vị=> sort_arr = <1>, i = 1Xét thấy arr1 > arr2 => chèn arr2 vào cuối mảng sort_arr, tăng j lên 1 1-1 vị=> sort_arr = <1, 3>, i = 1, j = 1Xét thấy arr1 > arr2 => chèn arr2 vào thời điểm cuối mảng sort_arr, tăng j lên 1 đơn vị => sort_arr = <1, 3, 5>, i = 1, j = 2Xét thấy arr1 > arr2 => chèn arr2 vào thời gian cuối mảng sort_arr, tăng j lên 1 đơn vị => sort_arr = <1, 3, 5, 7>, i = 1, j = 3Xét thấy arr1 = arr2 => chèn arr1 hoặc arr2 vào thời điểm cuối mảng sort_arr

Minh họa thuật toán thu xếp quick sort sử dụng C/C++

// Code from https://blog.luyencode.net#include#include // Gộp nhì mảng con arr cùng arrvoid merge(int arr<>, int l, int m, int r){ int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* Tạo các mảng trợ thời */ int L, R; /* Copy tài liệu sang các mảng trợ thì */ for (i = 0; i

Đánh giá bán thuật toán sắp xếp merge sort

Độ tinh vi thuật toán

Trường hòa hợp tốt: O(nlog(n))Trung bình: O(nlog(n))Trường phù hợp xấu: O(nlog(n))

Không gian bộ nhớ sử dụng: O(n)

Chào ace, bài bác này họ sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong thiết kế và thực tiễn nhất đó là Merge Sort, sau đây eivonline.edu.vn sẽ ra mắt và share chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Merge Sort thông qua những phần sau.


1. Giới thiệu

Giống như Quick
Sort, Merge Sort là một thuật toán phân tách và Chinh phục. Nó chia mảng nguồn vào thành hai nửa, gọi chính nó đến hai nửa và tiếp đến hợp duy nhất hai nửa đã sắp xếp. Hàm merge () được sử dụng để hợp tuyệt nhất hai nửa. Hợp duy nhất (arr, l, m, r) là quá trình đặc biệt quan trọng giả định rằng arr với arr được sắp xếp và hợp nhất hai mảng con đã thu xếp thành một. Coi cách triển khai C sau để hiểu thêm chi tiết.

Merge
Sort (arr <>, l, r)Nếu r> l 1. Tìm điểm giữa để chia mảng thành nhì nửa: Ở giữa m = (l + r) / 2 2. Hợp nhất cuộc gọi sắp xếp cho nửa đầu: điện thoại tư vấn merge
Sort(arr, l, m) 3. Hợp tuyệt nhất cuộc gọi sắp xếp cho nửa sau: gọi merge
Sort(arr, m + 1, r) 4. Hợp tốt nhất hai nửa được sắp xếp ở bước 2 và 3: call merge(arr, l, m, r)Sơ đồ tiếp sau đây từ wikipedia cho thấy thêm quy trình sắp xếp hợp nhất hoàn hảo cho một mảng ví dụ 38, 27, 43, 3, 9, 82, 10. Nếu họ xem xét kỹ hơn sơ đồ, bạn có thể thấy rằng mảng được phân tách đệ quy làm cho hai nửa cho đến khi form size trở thành 1. Khi form size trở thành 1, các quy trình hợp nhất sẽ chuyển động và bắt đầu hợp nhất các mảng trở lại cho đến khi mảng hoàn chỉnh đã đúng theo nhất.

Hình ảnh minh hoạ


*

2. Code lấy một ví dụ trên những ngôn ngữ

C++

// C++ program for Merge Sort #include using namespace std; // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; // Create temp arrays int L, R; // Copy data lớn temp arrays L<> and R<> for(int i = 0; i C

/* C program for Merge Sort */#include #include // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L, R; /* Copy data to lớn temp arrays L<> và R<> */ for (i = 0; i Java

/* Java program for Merge Sort */class Merge
Sort { // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { // Find sizes of two subarrays to lớn be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L<> = new int; int R<> = new int; /*Copy data lớn temp arrays*/ for (int i = 0; i Python3

# Python program for implementation of Merge
Sort def merge
Sort(arr): if len(arr) >1: mid = len(arr)//2 # Finding the mid of the array L = arr<:mid> # Dividing the array elements R = arr # into 2 halves merge
Sort(L) # Sorting the first half merge
Sort(R) # Sorting the second half i = j = k = 0 # Copy data to lớn temp arrays L<> & R<> while i Kết quả


Given array is12 11 13 5 6 7Sorted array is5 6 7 11 12 13

3. Độ phức tạp

Độ phức tạp về thời gian: Sắp xếp các mảng trên các máy không giống nhau. Merge Sort là một trong những thuật toán đệ quy cùng độ phức tạp thời gian có thể được bộc lộ như sau.

Xem thêm: Bật Mí 11+ Quán Cafe Tình Nhân Ở Sài Gòn, Top 9 Quán Cafe Tình Nhân Lãng Mạn Ở Sài Gòn

T (n) = 2T (n / 2) + θ (n)Sự lặp lại trên rất có thể được giải quyết bằng cách sử dụng cách thức tree lặp lại hoặc phương pháp Master. Nó phía trong trường vừa lòng II của cách thức Master cùng nghiệm của việc tái diễn là θ (n
Logn). Độ phức hợp thời gian của thu xếp hợp nhất(Merge Sort) là θ (n
Logn) vào cả 3 trường phù hợp (xấu nhất, trung bình và giỏi nhất) vì thu xếp hợp nhất luôn luôn chia mảng thành nhị nửa cùng mất thời hạn tuyến tính để hợp nhất hai nửa.

Không gian phụ trợ: O (n)

Mô hình thuật toán: chia và Chinh phục

Ổn định: Có

4. Ứng dụng

Merge Sort rất có lợi để sắp đến xếp các danh sách được links trong thời gian O (n
Logn). Trong trường hợp danh sách được liên kết, trường đúng theo này khác biệt chủ yếu bởi vì sự khác biệt trong phân bổ bộ nhớ lưu trữ của mảng và list được liên kết. Không y như mảng, những nút danh sách liên kết có thể không sát trong bộ nhớ. Không hệt như một mảng, trong list liên kết, bạn có thể chèn các mục vào thân trong O (1) không gian thừa và O (1) thời gian. Vị đó vận động hợp duy nhất của sắp xếp hợp nhất hoàn toàn có thể được thực hiện mà không tồn tại thêm dung lượng cho list được liên kết. Vào mảng, chúng ta cũng có thể thực hiện truy cập ngẫu nhiên khi các bộ phận nằm kề nhau trong bộ nhớ. Trả sử chúng ta có một mảng A số nguyên (4 byte) và đặt add của A <0> là x thì để truy cập A , bạn có thể truy cập trực tiếp vào bộ nhớ lưu trữ tại (x + i * 4). Không y như mảng, họ không thể thực hiện truy cập tự dưng trong danh sách liên kết. Sắp xếp nhanh yêu thương cầu tương đối nhiều loại tróc nã cập. Trong danh sách liên kết để truy vấn chỉ mục lắp thêm i, họ phải dịch rời từng nút từ đầu đến nút thiết bị i vì họ không bao gồm khối bộ lưu trữ liên tục. Vì đó, ngân sách tăng đối với nhanh chóng. Sắp xếp hợp nhất truy vấn dữ liệu một biện pháp tuần từ và nhu cầu truy cập thốt nhiên thấp.Vấn đề đảo ngược số lượng
Được áp dụng trong sắp xếp bên ngoài

Nguồn cùng Tài liệu tiếng anh tham khảo:

Tài liệu từ bỏ eivonline.edu.vn:

Nếu chúng ta thấy hay cùng hữu ích, chúng ta cũng có thể tham gia những kênh sau của eivonline.edu.vn nhằm nhận được không ít hơn nữa: