Merge sort là một trong những thuật toán khoa học máy tính cơ bản, được xây dựng từ năm 1945 bởi nhà toán học vĩ đại John von Neumann. Trong khi tham gia Dự án Manhattan, Neumann phải đối mặt với nhu cầu xử lý một cách hiệu quả lượng dữ liệu khổng lồ. Phương pháp do ông phát triển sử dụng nguyên tắc "chia để trị", giúp giảm đáng kể thời gian cần thiết cho công việc.
Nguyên tắc và sử dụng thuật toán
Phương pháp sắp xếp hợp nhất được sử dụng trong các bài toán sắp xếp cấu trúc có quyền truy cập theo thứ tự vào các phần tử, chẳng hạn như mảng, danh sách, luồng.
Trong quá trình xử lý, khối dữ liệu ban đầu được chia thành các thành phần nhỏ, tối đa một phần tử, trên thực tế, khối này đã là một danh sách đã được sắp xếp. Sau đó, nó được tập hợp lại theo đúng thứ tự.
Sắp xếp một mảng có độ dài nhất định yêu cầu một vùng nhớ bổ sung có cùng kích thước, trong đó mảng đã sắp xếp được thu thập thành từng phần.
Phương thức này có thể được sử dụng để sắp xếp bất kỳ kiểu dữ liệu có thể so sánh nào, chẳng hạn như số hoặc chuỗi.
Hợp nhất được sắp xếplô
Để hiểu thuật toán, hãy bắt đầu phân tích từ cuối - từ cơ chế hợp nhất các khối được sắp xếp.
Hãy tưởng tượng rằng chúng ta có hai mảng số được sắp xếp theo bất kỳ cách nào cần được kết hợp với nhau để việc sắp xếp không bị hỏng. Để đơn giản, chúng tôi sẽ sắp xếp các số theo thứ tự tăng dần.
Ví dụ cơ bản: cả hai mảng bao gồm một phần tử mỗi mảng.
int arr1={31}; int arr2={18};
Để hợp nhất chúng, bạn cần lấy phần tử 0 của mảng đầu tiên (đừng quên rằng việc đánh số bắt đầu từ 0) và phần tử 0 của mảng thứ hai. Đây lần lượt là 31 và 18. Theo điều kiện sắp xếp, số 18 nên đứng trước vì nó ít hơn. Chỉ cần đặt các số theo đúng thứ tự:
int result={18, 31};
Hãy xem một ví dụ phức tạp hơn, trong đó mỗi mảng bao gồm một số phần tử:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Thuật toán hợp nhất sẽ bao gồm việc so sánh tuần tự các phần tử nhỏ hơn và đặt chúng vào mảng kết quả theo đúng thứ tự. Để theo dõi các chỉ số hiện tại, hãy giới thiệu hai biến - index1 và index2. Ban đầu, chúng tôi đặt chúng bằng 0, vì các mảng được sắp xếp và các phần tử nhỏ nhất nằm ở đầu.
int index1=0; int index2=0;
Hãy viết toàn bộ quy trình hợp nhất từng bước:
- Lấy phần tử có index1 từ mảng arr1 và phần tử có index2 từ mảng arr2.
- So sánh, chọn cái nhỏ nhất trong số chúng và đưa vàomảng kết quả.
- Tăng chỉ số hiện tại của phần tử nhỏ hơn 1.
- Tiếp tục từ bước đầu tiên.
Trên quỹ đạo đầu tiên, tình hình sẽ như thế này:
index1=0; index2=0; arr1 [0]=2; arr2 [0]=5; arr1 [0] < arr2 [0]; index1 ++; kết quả [0]=arr1 [0]; // kết quả=[2]
Ở lượt thứ hai:
index1=1; index2=0; arr1 [1]=17; arr2 [0]=5; arr1 [1] > arr2 [0]; index2 ++; kết quả [1]=arr2 [0]; // kết quả=[2, 5]
Thứ ba:
index1=1; index2=1; arr1 [1]=17; arr2 [1]=6; arr1 [1] > arr2 [1]; index2 ++; kết quả [2]=arr2 [1]; // kết quả=[2, 5, 6]
Và cứ tiếp tục như vậy, cho đến khi kết quả là một mảng được sắp xếp hoàn chỉnh: {2, 5, 6, 17, 21, 19, 30, 45}.
Một số khó khăn có thể phát sinh nếu hợp nhất các mảng có độ dài khác nhau. Điều gì sẽ xảy ra nếu một trong các chỉ mục hiện tại đã đến phần tử cuối cùng và vẫn còn các thành viên trong mảng thứ hai?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 bước index1=0, index2=0; 1 2 kết quả={1, 2}; // 3 bước index1=1, index2=1; 4 < 5 result={1, 2, 4}; // 4 bước index1=2, index2=1 ??
Biến index1 đã đạt đến giá trị 2, nhưng mảng arr1 không có phần tử có chỉ số đó. Mọi thứ rất đơn giản ở đây: chỉ cần chuyển các phần tử còn lại của mảng thứ hai sang mảng kết quả, giữ nguyên thứ tự của chúng.
result={1, 2, 4, 5, 6, 7, 9};
Tình huống này cho chúng ta thấy sự cần thiếtkhớp chỉ số kiểm tra hiện tại với độ dài của mảng được hợp nhất.
Lược đồ hợp nhất cho các chuỗi có thứ tự (A và B) có độ dài khác nhau:
- Nếu độ dài của cả hai chuỗi lớn hơn 0, hãy so sánh A [0] và B [0] và di chuyển chuỗi nhỏ hơn vào bộ đệm.
- Nếu độ dài của một trong các dãy bằng 0, hãy lấy các phần tử còn lại của dãy thứ hai và di chuyển đến cuối bộ đệm mà không thay đổi thứ tự của chúng.
Thực hiện giai đoạn thứ hai
Ví dụ về việc nối hai mảng đã sắp xếp trong Java được đưa ra dưới đây.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int [a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) {int a=a2 [j]; a3 [k]=a; j ++; } else if (j > a2.length-1) {int a=a1 ; a3 [k]=a; i ++; } else if (a1 < a2 [j]) {int a=a1 ; a3 [k]=a; i ++; } else {int b=a2 [j]; a3 [k]=b; j ++; }}
Tại đây:
- a1 và a2 là các mảng được sắp xếp ban đầu sẽ được hợp nhất;
- a3 - mảng cuối cùng;
- i và j là chỉ số của các phần tử hiện tại cho mảng a1 và a2.
Điều kiện đầu tiên và thứ hai nếu đảm bảo rằng các chỉ mục không vượt quá kích thước của mảng. Các khối điều kiện thứ ba và thứ tư, tương ứng, được chuyển đến mảng kết quả của phần tử nhỏ hơn.
Chia cắt và Chinh phục
Vì vậy, chúng ta đã học cách hợp nhất cáctập hợp các giá trị. Có thể nói rằng phần thứ hai của thuật toán sắp xếp hợp nhất - chính là hợp nhất - đã được sắp xếp.
Tuy nhiên, bạn vẫn cần hiểu cách chuyển từ mảng số chưa được sắp xếp ban đầu thành một số dãy số đã được sắp xếp có thể được hợp nhất.
Hãy xem xét giai đoạn đầu tiên của thuật toán và tìm hiểu cách tách các mảng.
Điều này không khó - danh sách các giá trị ban đầu được chia đôi, sau đó mỗi phần cũng được chia đôi, và cứ tiếp tục như vậy cho đến khi thu được các khối rất nhỏ.
Độ dài của các phần tử tối thiểu như vậy có thể bằng một, tức là bản thân chúng có thể là một mảng đã sắp xếp, nhưng đây không phải là điều kiện cần. Kích thước của khối được xác định trước và bất kỳ thuật toán sắp xếp phù hợp nào hoạt động hiệu quả với các mảng có kích thước nhỏ (ví dụ: sắp xếp nhanh hoặc sắp xếp chèn) đều có thể được sử dụng để sắp xếp thứ tự.
Nó trông như thế này.
// mảng ban đầu {34, 95, 10, 2, 102, 70}; // lần chia đầu tiên {34, 95, 10} và {2, 102, 70}; // phần tách thứ hai {34} và {95, 10} và {2} và {102, 70}
Các khối kết quả, bao gồm 1-2 phần tử, rất dễ sắp xếp.
Sau đó, bạn cần hợp nhất các mảng nhỏ đã được sắp xếp theo cặp, bảo toàn thứ tự của các thành viên, điều mà chúng ta đã học cách làm.
Thực hiện giai đoạn đầu
Phân vùng đệ quy của một mảng được hiển thị bên dưới.
void mergeSort (T a , bắt đầu dài, kết thúc dài) {tách dài; nếu(bắt đầu < kết thúc) {split=(bắt đầu + kết thúc) / 2; mergeSort (a, bắt đầu, tách); mergeSort (a, split + 1, finish); hợp nhất (a, bắt đầu, tách, kết thúc); }}
Điều gì xảy ra trong mã này:
-
Hàm mergeSort nhận mảng ban đầu
a
và các đường viền trái và phải của vùng được sắp xếp (các chỉ số bắt đầu và
- kết thúc).
-
Nếu độ dài của phần này lớn hơn một (
start < finish
), thì nó được chia thành hai phần (theo chỉ mục
- split), và mỗi cái được sắp xếp đệ quy.
-
Trong lệnh gọi hàm đệ quy cho phía bên trái, chỉ số bắt đầu của biểu đồ và chỉ số
split
được chuyển. Đối với phần bên phải, tương ứng, phần đầu sẽ là
- (split + 1)và phần cuối sẽ là chỉ mục cuối cùng của phần gốc.
-
Hàm
merge
nhận hai chuỗi có thứ tự (
a [start]… a [split]
và
- a [split +1]… a [finish]) và hợp nhất chúng theo thứ tự sắp xếp.
Cơ chế của hàm hợp nhất đã được thảo luận ở trên.
Lược đồ chung của thuật toán
Phương pháp mảng sắp xếp hợp nhất bao gồm hai bước lớn:
- Tách mảng ban đầu chưa được sắp xếp thành nhiều phần nhỏ.
- Thu thập chúng theo cặp, tuân theo quy tắc sắp xếp.
Một nhiệm vụ lớn và phức tạp được chia thành nhiều nhiệm vụ đơn giản, được giải quyết tuần tự, dẫn đến kết quả mong muốn.
Đánh giá phương pháp
Độ phức tạp về thời gian của sắp xếp hợp nhất được xác định bởi chiều cao của cây táchthuật toán và bằng số phần tử trong mảng (n) nhân với logarit của nó (log n). Ước tính như vậy được gọi là lôgarit.
Đây vừa là ưu điểm vừa là nhược điểm của phương pháp. Thời gian chạy của nó không thay đổi ngay cả trong trường hợp xấu nhất, khi mảng ban đầu được sắp xếp theo thứ tự ngược lại. Tuy nhiên, khi xử lý dữ liệu được sắp xếp hoàn chỉnh, thuật toán không cung cấp thời gian tăng.
Cũng cần lưu ý chi phí bộ nhớ của phương pháp sắp xếp hợp nhất. Chúng bằng với kích thước của bộ sưu tập ban đầu. Trong khu vực được phân bổ bổ sung này, một mảng đã sắp xếp được ghép từ các mảnh.
Thực hiện thuật toán
Sắp xếp hợp nhất Pascal được hiển thị bên dưới.
Thủ tục MergeSort (tên: string; var f: text); Var a1, a2, s, i, j, kol, tmp: integer; f1, f2: text; b: boolean Begincol:=0; Assign (f, tên); đặt lại (f); While not EOF (f) do begin read (f, a1); inc (col); chấm dứt; đóng (f); Assign (f1, '{tên tệp bổ trợ thứ nhất}'); Assign (f2, '{tên tệp phụ thứ 2}'); s:=1; Trong khi (s<kol) bắt đầu Đặt lại (f); viết lại (f1); viết lại (f2); For i:=1 to kol div 2 do begin Read (f, a1); Viết (f1, a1, ''); chấm dứt; If (kol div 2) mod s0 then begin tmp:=kol div 2; Trong khi tmp mod s0 do begin Read (f, a1); Viết (f1, a1, ''); inc (tmp); chấm dứt; chấm dứt; While not EOF (f) do begin Read (f, a2); Viết (f2, a2, ''); chấm dứt; đóng (f); đóng (f1); đóng (f2); viết lại (f); đặt lại (f1); đặt lại (f2); Đọc (f1, a1); Đọc (f2, a2); While (not EOF (f1)) and (not EOF (f2)) do begin i:=0; j:=0; b:=true; Trong khi (b) và (không phải EOF (f1)) và (không phải EOF (f2)) bắt đầu Nếu (a1<a2) thì bắt đầuViết (f, a1, ''); Đọc (f1, a1); bao gồm (i); End else begin Write (f, a2, ''); Đọc (f2, a2); bao gồm (j); chấm dứt; If (i=s) hoặc (j=s) then b:=false; chấm dứt; Nếu không phải b thì bắt đầu Trong khi (i<s) và (không phải EOF (f1)) do bắt đầu Viết (f, a1, ''); Đọc (f1, a1); bao gồm (i); chấm dứt; While (j<s) và (không phải EOF (f2)) do begin Write (f, a2, ''); Đọc (f2, a2); bao gồm (j); chấm dứt; chấm dứt; chấm dứt; Trong khi không phải EOF (f1) do begin tmp:=a1; Đọc (f1, a1); If not EOF (f1) then Write (f, tmp, '') else Write (f, tmp); chấm dứt; Trong khi không phải EOF (f2) do begin tmp:=a2; Đọc (f2, a2); If not EOF (f2) then Write (f, tmp, '') else Write (f, tmp); chấm dứt; đóng (f); đóng (f1); đóng (f2); s:=s2; chấm dứt; Xóa (f1); Xóa (f2); Kết thúc;
Về mặt trực quan, hoạt động của thuật toán trông như thế này (trên cùng - trình tự không có thứ tự, dưới cùng - có thứ tự).
Sắp xếp dữ liệu bên ngoài
Rất thường xuyên có nhu cầu sắp xếp một số dữ liệu nằm trong bộ nhớ ngoài của máy tính. Trong một số trường hợp, chúng có kích thước ấn tượng và không thể được đặt trong RAM để thuận tiện cho việc truy cập chúng. Đối với những trường hợp như vậy, các phương pháp sắp xếp bên ngoài được sử dụng.
Nhu cầu truy cập phương tiện bên ngoài làm giảm hiệu quả thời gian xử lý.
Sự phức tạp của công việc là thuật toán chỉ có thể truy cập một phần tử của luồng dữ liệu tại một thời điểm. Và trong trường hợp này, một trong những kết quả tốt nhất được hiển thị bằng phương pháp sắp xếp hợp nhất, có thể so sánh tuần tự các phần tử của hai tệp với nhau.
Đọc dữ liệu từnguồn bên ngoài, việc xử lý và ghi chúng vào tệp cuối cùng được thực hiện trong các khối (chuỗi) có thứ tự. Theo cách làm việc với kích thước của chuỗi có thứ tự, có hai kiểu sắp xếp: đơn giản và hợp nhất tự nhiên.
Hợp nhất đơn giản
Chỉ với một phép hợp nhất đơn giản, độ dài của sê-ri được cố định.
Vì vậy, trong tệp chưa được sắp xếp ban đầu, tất cả các chuỗi đều bao gồm một phần tử. Sau bước đầu tiên, kích thước tăng lên hai. Tiếp theo - 4, 8, 16, v.v.
Nó hoạt động như thế này:
- Tệp nguồn (f) được chia thành hai tệp phụ - f1, f2.
- Chúng lại được hợp nhất thành một tệp (f), nhưng đồng thời tất cả các phần tử được so sánh theo từng cặp và tạo thành từng cặp. Kích thước sê-ri ở bước này trở thành hai.
- Bước 1 được lặp lại.
- Bước 2 được lặp lại, nhưng 2 bước đã có thứ tự sẽ được hợp nhất để tạo thành 4 bước được sắp xếp.
- Vòng lặp tiếp tục, tăng chuỗi trên mỗi lần lặp, cho đến khi toàn bộ tệp được sắp xếp.
Làm thế nào để bạn biết rằng việc phân loại bên ngoài với sự hợp nhất đơn giản đã hoàn tất?
- độ dài chuỗi mới (sau khi hợp nhất) không nhỏ hơn tổng số phần tử;
- chỉ còn một tập nữa thôi;
- Tệp bổ trợ f2 bị bỏ trống.
Nhược điểm của hợp nhất đơn giản là: vì thời lượng chạy được cố định trên mỗi lần hợp nhất, dữ liệu được sắp xếp từng phần sẽ mất nhiều thời gian để xử lý như dữ liệu hoàn toàn ngẫu nhiên.
Hợptự nhiên
Phương pháp này không giới hạn độ dàinhưng hãy chọn mức tối đa có thể.
Thuật toán sắp xếp:
- Đọc trình tự ban đầu từ tệp f. Phần tử nhận được đầu tiên được ghi vào tệp f1.
- Nếu mục tiếp theo thỏa mãn điều kiện sắp xếp, mục này sẽ được ghi ở đó, nếu không, thì vào tệp bổ trợ thứ hai f2.
- Theo cách này, tất cả các bản ghi của tệp nguồn được phân phối và một chuỗi có thứ tự được tạo thành f1, sẽ xác định kích thước hiện tại của chuỗi.
- Tệp f1 và f2 được hợp nhất.
- Chu kỳ lặp lại.
Do kích thước không cố định của dãy số nên đánh dấu cuối dãy bằng ký tự đặc biệt. Do đó, khi hợp nhất, số lượng so sánh tăng lên. Ngoài ra, kích thước của một trong các tệp bổ trợ có thể gần bằng kích thước của tệp gốc.
Trung bình, hợp nhất tự nhiên hiệu quả hơn so với hợp nhất đơn giản với sắp xếp bên ngoài.
Tính năng của thuật toán
Khi so sánh hai giá trị giống nhau, phương pháp giữ nguyên thứ tự ban đầu của chúng, tức là nó ổn định.
Quá trình sắp xếp có thể được chia thành nhiều chủ đề rất thành công.
Video minh họa rõ ràng hoạt động của thuật toán sắp xếp hợp nhất.
