Cách thực hiện Sắp xếp Hợp nhất trong C ++ với các ví dụ

Sắp xếp hợp nhất là gì? Sắp xếp hợp nhất là một thuật toán sắp xếp dựa trên so sánh thuộc về loại chia và chinh phục. Sắp xếp hợp nhất được sử dụng để sắp xếp một mảng dựa trên chiến lược chia và chinh phục sẽ được đề cập ngắn gọn trong bài đăng này cùng với các khái niệm khác như thuật toán của nó với một ví dụ. Chúng ta cũng sẽ xem xét độ phức tạp về thời gian của sắp xếp hợp nhất trong C ++

Các gợi ý sau sẽ được đề cập trong bài viết này,

• Thuật toán Chia và Chinh phục
• Tìm hiểu Thuật toán sắp xếp hợp nhất với một ví dụ
• Mã giả để Hợp nhất Sắp xếp
• Chương trình trong C ++ cho Merge Sort
• Sự phức tạp về thời gian đối với Sắp xếp Hợp nhất

Tiếp tục với bài viết này về Merge Sort trong C ++

Thuật toán phân chia và chinh phục

Nếu bạn đã quen với cách hoạt động của quicksort, bạn có thể biết về chiến lược phân chia và chinh phục. Chia và Chinh phục bao gồm ba bước chính. Để hiểu các bước này, chúng ta hãy xem xét một mảng Xin chào [] có chỉ mục bắt đầu là ‘a’ và chỉ mục kết thúc là ‘n’ do đó chúng ta có thể viết mảng của mình theo cách sau Xin chào [a & hellip..n]

Chia - Bước đi chính hay bước chính của chia và chinh phục là chia bài toán đã cho thành các bài toán con hoặc phần phụ. Điểm bắt buộc ở đây là các bài toán con phải tương tự như bài toán ban đầu và có kích thước nhỏ hơn. Trong trường hợp của chúng tôi, chúng tôi sẽ chia mảng của chúng tôi thành 2 nửa [a & hellip.m] [m + 1 & hellip..n] m nằm ở giữa chỉ mục a và n

Chinh phục- Khi chúng ta hoàn thành việc chia vấn đề của mình thành các vấn đề phụ. Chúng tôi giải quyết các bài toán con này một cách đệ quy.

Kết hợp - Trong bước này, chúng tôi kết hợp tất cả các giải pháp của các vấn đề phụ của chúng tôi theo một cách thích hợp. Nói cách khác, chúng tôi kết hợp 2 mảng được sắp xếp khác nhau để tạo thành một mảng được sắp xếp. Ở đó, chúng tôi có mảng được sắp xếp của chúng tôi.

Tiếp tục với bài viết này về Merge Sort trong C ++

Tìm hiểu thuật toán sắp xếp hợp nhất với ví dụ

Tại thời điểm này, chúng tôi biết cách tiếp cận sẽ được sử dụng bởi sắp xếp hợp nhất. Vì vậy, hãy xem xét một ví dụ và đi qua từng bước từ Hello [] không được sắp xếp đến một mảng được sắp xếp.
Ví dụ- Xin chào [10, 3, 7, 1, 15, 14, 9, 22]

Trong hình trên, chúng tôi coi là một mảng chưa được sắp xếp và sử dụng sắp xếp hợp nhất để có được một mảng đã sắp xếp. Bây giờ, hãy xem xét từng bước và hiểu toàn bộ thuật toán

1. Đầu tiên, chúng tôi xem xét mảng Hello [10, 3, 7, 1, 15, 14, 9, 22] trong mảng này có tổng số 8 phần tử

cách đảo ngược một số

2. Như chúng ta đã thấy trước đó, sắp xếp hợp nhất sử dụng cách tiếp cận chia và chinh phục để sắp xếp các phần tử. Chúng tôi tìm thấy m nằm ở giữa mảng của chúng tôi và chia mảng của chúng tôi từ giữa trong đó m = (a - n) / 2 'a' là chỉ số của phần tử ngoài cùng bên trái và n là chỉ số của phần tử ngoài cùng bên phải của mảng của chúng tôi .

3. Sau lần chia thứ nhất, ta có 2 phần gồm 4 phần tử mỗi phần. Hãy nhìn vào nửa đầu [10, 3, 7, 1].

4. Chúng tôi chia [10, 3, 7, 1] thành 2 phần [10, 3] và [7, 1]. Sau đó, chúng tôi chia chúng thành [10], [3], [7], [1]. Không thể phân chia thêm vì chúng ta không thể tính được m. danh sách chứa một phần tử duy nhất luôn được coi là đã sắp xếp.

5. Việc hợp nhất diễn ra như thế nào? Hãy cùng tìm hiểu. Đầu tiên [10] và [3] được so sánh và hợp nhất theo thứ tự tăng dần [3, 10] theo cùng một cách mà chúng ta nhận được [1, 7]

6. Sau đó, chúng tôi so sánh [3, 10] và [1, 7]. Sau khi so sánh, chúng tôi hợp nhất chúng theo thứ tự tăng dần và Chúng tôi nhận được [1, 3, 7, 10].

7. [15, 14, 9, 2] cũng được chia và kết hợp theo cách tương tự để tạo thành [9, 14, 15, 22].

8. Trong bước cuối cùng, chúng tôi so sánh và kết hợp [15, 14, 9, 2] [9, 14, 15, 22] để cung cấp cho chúng tôi mảng đã sắp xếptức là [1, 3, 7, 9, 10, 14, 15, 22].

Tiếp tục với bài viết này về Merge Sort trong C ++

Mã giả để Hợp nhất Sắp xếp

Bắt đầu nếu còn lại
Hàm mergeSort () gọi đệ quy chính nó để chia mảng của chúng ta cho đến khi nó trở thành một phần tử duy nhất và hàm merge () được sử dụng để hợp nhất các mảng đã sắp xếp.
  Tiếp tục với bài viết này về Merge Sort trong C ++
 Hợp nhất chương trình sắp xếp trong C ++ 
#include #include #include using namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // hợp nhất các mảng con được tạo trong khi phân chia void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Xin chào [size], tôi cout<<'Enter the elements of the array one by one:n' for(i=0 i>Xin chào [i] mergeSort (Xin chào, 0, size - 1) cout<<'The Sorted List isn' for(i=0 i
 Đầu ra- 
hướng dẫn máy chủ microsoft sql cho người mới bắt đầu
Tiếp tục với bài viết này về Merge Sort trong C ++
 Thời gian phức tạp 
Độ phức tạp về thời gian là một khía cạnh quan trọng cần được xem xét khi chúng ta nói về các thuật toán. Sắp xếp hợp nhất được coi là có độ phức tạp về thời gian lớn so với các thuật toán sắp xếp khác.
Thời gian chạy trường hợp xấu nhất- O (n log n) 
Thời gian chạy trường hợp tốt nhất- O (n log n) 
Thời gian chạy trung bình- O (n log n)
Với điều này, chúng ta sẽ kết thúc bài viết Merge Sort in C ++ này. Nếu bạn muốn tìm hiểu thêm, hãy xem   bởi Edureka, một công ty học trực tuyến đáng tin cậy. Khóa học đào tạo và cấp chứng chỉ Java J2EE và SOA của Edureka được thiết kế để đào tạo bạn về cả khái niệm Java cốt lõi và nâng cao cùng với các khung Java khác nhau như Hibernate & Spring.
 Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần nhận xét của blog này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.