Sắp xếp hợp nhất DSA
Hợp nhất Sắp xếp
Thuật toán Sắp xếp Hợp nhất là một thuật toán chia để trị, sắp xếp một mảng bằng cách trước tiên chia nó thành các mảng nhỏ hơn, sau đó xây dựng mảng lại với nhau theo cách chính xác để nó được sắp xếp.
Tốc độ:
{{ msgDone }}Chia: Thuật toán bắt đầu bằng việc chia mảng thành các phần ngày càng nhỏ hơn cho đến khi một mảng con như vậy chỉ bao gồm một phần tử.
Chinh phục: Thuật toán hợp nhất các phần nhỏ của mảng lại với nhau bằng cách đặt các giá trị thấp nhất lên trước, dẫn đến một mảng được sắp xếp.
Việc chia nhỏ và xây dựng mảng để sắp xếp mảng được thực hiện đệ quy.
Trong hoạt ảnh ở trên, mỗi lần các thanh được đẩy xuống biểu thị một lệnh gọi đệ quy, chia mảng thành các phần nhỏ hơn. Khi các thanh được nhấc lên có nghĩa là 2 mảng con đã được gộp lại với nhau.
Thuật toán Sắp xếp Hợp nhất có thể được mô tả như sau:
Làm thế nào nó hoạt động:
- Chia mảng chưa sắp xếp thành hai mảng con, bằng một nửa kích thước của mảng ban đầu.
- Tiếp tục chia các mảng con miễn là phần hiện tại của mảng có nhiều hơn một phần tử.
- Hợp nhất hai mảng con lại với nhau bằng cách luôn đặt giá trị thấp nhất lên đầu tiên.
- Tiếp tục hợp nhất cho đến khi không còn mảng con nào.
Hãy xem bản vẽ bên dưới để biết cách Sắp xếp Hợp nhất hoạt động từ một góc nhìn khác. Như bạn có thể thấy, mảng được chia thành các phần ngày càng nhỏ hơn cho đến khi nó được hợp nhất lại với nhau. Và khi quá trình hợp nhất diễn ra, các giá trị từ mỗi mảng con sẽ được so sánh sao cho giá trị thấp nhất sẽ xuất hiện trước.
Chạy qua thủ công
Chúng ta hãy thử thực hiện việc sắp xếp theo cách thủ công, để hiểu rõ hơn về cách hoạt động của Sắp xếp Hợp nhất trước khi thực sự triển khai nó bằng ngôn ngữ lập trình.
Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp và chúng ta biết rằng nó sẽ chia đôi cho đến khi các mảng con chỉ bao gồm một phần tử. Hàm Sắp xếp Hợp nhất gọi chính nó hai lần, một lần cho mỗi nửa mảng. Điều đó có nghĩa là mảng con đầu tiên sẽ được chia thành các phần nhỏ nhất trước tiên.
[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]
Bước 2: Việc tách mảng con đầu tiên đã hoàn tất và bây giờ là lúc hợp nhất. 8 và 9 là hai phần tử đầu tiên được hợp nhất. 8 là giá trị thấp nhất, do đó nó đứng trước 9 trong mảng con được hợp nhất đầu tiên.
[ 12] [ 8 , 9 ] [ 3, 11, 5, 4]
Bước 3: Các mảng con tiếp theo cần gộp là [ 12] và [ 8, 9]. Giá trị trong cả hai mảng được so sánh ngay từ đầu. 8 nhỏ hơn 12 nên 8 đứng trước và 9 cũng thấp hơn 12.
[ 8 , 9 , 12 ] [ 3, 11, 5, 4]
Bước 4: Bây giờ mảng con lớn thứ hai được phân chia đệ quy.
[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
Bước 5: 3 và 11 được gộp lại với nhau theo đúng thứ tự hiển thị vì 3 nhỏ hơn 11.
[ 8, 9, 12] [ 3 , 11 ] [ 5, 4]
Bước 6: Tách mảng con có giá trị 5 và 4, sau đó hợp nhất sao cho 4 đứng trước 5.
[ 8, 9, 12] [ 3, 11] [ 5 ] [ 4 ]
[ 8, 9, 12] [ 3, 11] [ 4 , 5 ]
Bước 7: Hai mảng con bên phải được hợp nhất. Việc so sánh được thực hiện để tạo các phần tử trong mảng được hợp nhất mới:
- 3 thấp hơn 4
- 4 thấp hơn 11
- 5 thấp hơn 11
- 11 là giá trị cuối cùng còn lại
[ 8, 9, 12] [ 3 , 4 , 5 , 11 ]
Bước 8: Hai mảng con còn lại cuối cùng được hợp nhất. Chúng ta hãy xem cách so sánh được thực hiện chi tiết hơn để tạo mảng mới được hợp nhất và sắp xếp hoàn chỉnh:
3 thấp hơn 8:
Before [ 8 , 9, 12] [ 3 , 4, 5, 11]
After: [ 3 , 8 , 9, 12] [ 4, 5, 11]
Bước 9: 4 thấp hơn 8:
Before [ 3, 8 , 9, 12] [ 4 , 5, 11]
After: [ 3, 4 , 8 , 9, 12] [ 5, 11]
Bước 10: 5 thấp hơn 8:
Before [ 3, 4, 8 , 9, 12] [ 5 , 11]
After: [ 3, 4, 5 , 8 , 9, 12] [ 11]
Bước 11: 8 và 9 nhỏ hơn 11:
Before [ 3, 4, 5, 8 , 9 , 12] [ 11 ]
After: [ 3, 4, 5, 8 , 9 , 12] [ 11 ]
Bước 12: 11 nhỏ hơn 12:
Before [ 3, 4, 5, 8, 9, 12 ] [ 11 ]
After: [ 3, 4, 5, 8, 9, 11 , 12 ]
Việc phân loại đã hoàn tất!
Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:
{{ x.dieNmbr }}Chạy qua thủ công: Chuyện gì đã xảy ra?
Chúng ta thấy thuật toán có hai giai đoạn: đầu tiên là tách, sau đó hợp nhất.
Mặc dù có thể triển khai thuật toán Sắp xếp Hợp nhất mà không cần đệ quy nhưng chúng tôi sẽ sử dụng đệ quy vì đó là cách tiếp cận phổ biến nhất.
Chúng ta không thể nhìn thấy nó trong các bước trên, nhưng để chia một mảng thành hai, độ dài của mảng được chia cho hai, sau đó làm tròn xuống để nhận giá trị mà chúng ta gọi là "mid". Giá trị "giữa" này được sử dụng làm chỉ mục cho vị trí phân chia mảng.
Sau khi mảng được phân tách, hàm sắp xếp sẽ tự gọi mỗi nửa mảng để mảng có thể được phân tách lại theo cách đệ quy. Việc phân tách dừng lại khi một mảng con chỉ bao gồm một phần tử.
Khi kết thúc chức năng Sắp xếp Hợp nhất, các mảng con được hợp nhất để các mảng con luôn được sắp xếp khi mảng được xây dựng lại. Để hợp nhất hai mảng con sao cho kết quả được sắp xếp, các giá trị của từng mảng con được so sánh và giá trị thấp nhất được đưa vào mảng đã hợp nhất. Sau đó, giá trị tiếp theo trong mỗi mảng con trong số hai mảng con được so sánh, đặt giá trị thấp nhất vào mảng đã hợp nhất.
Thực hiện sắp xếp hợp nhất
Để thực hiện thuật toán Sắp xếp Hợp nhất, chúng ta cần:
- Một mảng có các giá trị cần được sắp xếp.
- Một hàm nhận vào một mảng, chia mảng đó thành hai và gọi chính nó với mỗi nửa mảng đó để các mảng được phân tách nhiều lần theo cách đệ quy, cho đến khi một mảng con chỉ bao gồm một giá trị.
- Một hàm khác hợp nhất các mảng con lại với nhau theo cách được sắp xếp.
Mã kết quả trông như thế này:
Ví dụ
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]
sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)
return merge(sortedLeft, sortedRight)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr) Chạy ví dụ »Trên dòng 6 , arr[:mid] lấy tất cả các giá trị từ mảng cho đến nhưng không bao gồm giá trị trên chỉ mục "mid".
Trên dòng 7 , arr[mid:] lấy tất cả các giá trị từ mảng, bắt đầu từ giá trị trên chỉ mục "mid" và tất cả các giá trị tiếp theo.
Trên các dòng 26-27 , phần đầu tiên của quá trình hợp nhất đã hoàn tất. Tại thời điểm này, các giá trị của hai mảng con được so sánh và mảng con bên trái hoặc mảng con bên phải đều trống, do đó mảng kết quả chỉ có thể được lấp đầy với các giá trị còn lại từ bên trái hoặc bên phải mảng phụ. Những dòng này có thể được hoán đổi và kết quả sẽ giống nhau.
Hợp nhất Sắp xếp mà không đệ quy
Vì Sắp xếp Hợp nhất là một thuật toán phân chia và chinh phục nên đệ quy là mã trực quan nhất được sử dụng để triển khai. Việc triển khai đệ quy của Sắp xếp Hợp nhất có lẽ cũng dễ hiểu hơn và nói chung sử dụng ít dòng mã hơn.
Nhưng Sắp xếp Hợp nhất cũng có thể được thực hiện mà không cần sử dụng đệ quy, do đó không có hàm nào tự gọi chính nó.
Hãy xem triển khai Sắp xếp Hợp nhất bên dưới, cách triển khai này không sử dụng đệ quy:
Ví dụ
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def mergeSort(arr):
step = 1 # Starting with sub-arrays of length 1
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
# Place the merged array back into the original array
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2 # Double the sub-array length for the next iteration
return arr
unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)
Chạy ví dụ »Bạn có thể nhận thấy rằng các hàm hợp nhất hoàn toàn giống nhau trong hai cách triển khai Sắp xếp hợp nhất ở trên, nhưng trong cách triển khai ngay phía trên ở đây, vòng lặp while bên trong hàm mergeSort được sử dụng để thay thế đệ quy. Vòng lặp while thực hiện việc phân tách và hợp nhất mảng tại chỗ và điều đó làm cho mã khó hiểu hơn một chút.
Nói một cách đơn giản, vòng lặp while bên trong hàm mergeSort sử dụng độ dài bước ngắn để sắp xếp các phần nhỏ (mảng phụ) của mảng ban đầu bằng hàm hợp nhất. Sau đó, độ dài bước được tăng lên để hợp nhất và sắp xếp các phần lớn hơn của mảng cho đến khi toàn bộ mảng được sắp xếp.
Hợp nhất độ phức tạp của thời gian sắp xếp
Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .
Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp Hợp nhất, hãy truy cập trang này .
Độ phức tạp về thời gian của Sắp xếp Hợp nhất là
\[ O( n \cdot \log n ) \]
Và độ phức tạp về thời gian là khá giống nhau đối với các loại mảng khác nhau. Thuật toán cần tách mảng và hợp nhất lại với nhau cho dù nó đã được sắp xếp hay xáo trộn hoàn toàn.
Hình ảnh bên dưới cho thấy độ phức tạp về thời gian của Sắp xếp Hợp nhất.
Chạy mô phỏng bên dưới cho số lượng giá trị khác nhau trong một mảng và xem số lượng thao tác Sắp xếp hợp nhất cần trên một mảng các phần tử \(n\) là \(O(n \log n)\):
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Nếu chúng ta giữ số giá trị \(n\) cố định thì số thao tác cần thiết cho "Ngẫu nhiên", "Giảm dần" và "Tăng dần" gần như giống nhau.
Sắp xếp hợp nhất thực hiện gần như giống nhau mọi lúc vì mảng được phân tách và được hợp nhất bằng cách sử dụng so sánh, cả khi mảng đó đã được sắp xếp hay chưa.
