Mục lục
- Giới thiệu
- Hợp nhất sắp xếp trong C ++ là gì
- Phương pháp chia để trị
- Hợp nhất thuật toán sắp xếp
- Triển khai sắp xếp hợp nhất trong C ++
- Phần kết luận
1. Giới thiệu
Thuật toán sắp xếp trong khoa học máy tính được sử dụng để sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần. Có nhiều thuật toán sắp xếp với các thuộc tính riêng biệt có sẵn. Hợp nhất sắp xếp là một trong những phương thức trong C++ có thể sắp xếp các mảng.
2. Hợp nhất sắp xếp trong C++ là gì
Hợp nhất sắp xếp sử dụng kỹ thuật chia để trị có thể sắp xếp các phần tử của một mảng. Nó cũng có thể sắp xếp danh sách các phần tử trong C++. Nó chia đầu vào thành hai nửa, sắp xếp độc lập từng nửa và sau đó hợp nhất chúng theo đúng thứ tự.
3. Phương pháp chia để trị
Thuật toán sắp xếp áp dụng chiến lược chia để trị, đòi hỏi phải phân vùng mảng đầu vào thành các mảng con nhỏ hơn, giải quyết chúng một cách riêng biệt, sau đó hợp nhất các kết quả để tạo ra đầu ra được sắp xếp. Trong trường hợp sắp xếp hợp nhất, mảng được chia đệ quy thành hai nửa cho đến khi chỉ còn lại một phần tử trong mỗi nửa.
4. Thuật toán sắp xếp hợp nhất
Thuật toán sắp xếp hợp nhất bao gồm hai bước chính: chia và hợp nhất. Các bước thực hiện như sau:
4.1 Chia
Thuật toán sắp xếp hợp nhất tuân theo chiến lược chia để trị để sắp xếp các phần tử trong một mảng.
- Bước đầu tiên trong thuật toán sẽ kiểm tra các phần tử của mảng. Nếu nó chứa một phần tử, thì nó đã được coi là đã được sắp xếp và thuật toán sẽ trả về cùng một mảng mà không có bất kỳ thay đổi nào.
- Nếu mảng chứa nhiều hơn một phần tử, thuật toán tiến hành chia nó thành hai nửa: nửa bên trái và nửa bên phải.
- Sau đó, thuật toán sắp xếp hợp nhất được áp dụng đệ quy cho nửa bên trái và bên phải của mảng, phân chia chúng thành các mảng con nhỏ hơn một cách hiệu quả và sắp xếp chúng riêng lẻ.
- Quá trình đệ quy này tiếp tục cho đến khi các mảng con chỉ chứa một phần tử (theo bước 1), tại thời điểm đó, chúng có thể được hợp nhất để tạo ra một mảng đầu ra được sắp xếp cuối cùng.
4.2 Hợp nhất
Bây giờ chúng ta sẽ xem các bước để hợp nhất các mảng:
- Bước đầu tiên cho thuật toán sắp xếp hợp nhất liên quan đến việc tạo một mảng trống.
- Sau đó, thuật toán tiến hành so sánh các phần tử đầu tiên của nửa bên trái và bên phải của mảng đầu vào.
- Phần tử nhỏ hơn trong số hai phần tử được thêm vào mảng mới và sau đó bị xóa khỏi nửa tương ứng của mảng đầu vào.
- Các bước 2-3 sau đó được lặp lại cho đến khi hết một nửa.
- Mọi phần tử còn lại trong nửa không trống sẽ được thêm vào mảng mới.
- Mảng kết quả hiện đã được sắp xếp đầy đủ và biểu thị đầu ra cuối cùng của thuật toán sắp xếp hợp nhất.
5. Thực hiện Merge Sort trong C++
Để thực hiện sắp xếp hợp nhất trong C++, hai phương pháp khác nhau được tuân theo. Độ phức tạp về thời gian của cả hai phương pháp là tương đương, nhưng cách sử dụng các mảng con tạm thời của chúng khác nhau.
Phương thức đầu tiên để sắp xếp hợp nhất trong C++ sử dụng hai mảng con tạm thời, trong khi phương thức thứ hai chỉ sử dụng một. Điều đáng chú ý là tổng kích thước của hai mảng con tạm thời trong phương thức đầu tiên bằng với kích thước của mảng ban đầu trong phương thức thứ hai, do đó độ phức tạp của không gian không đổi.
Phương pháp 1 – Sử dụng hai mảng con tạm thời
Đây là một chương trình mẫu để hợp nhất sắp xếp trong C++ bằng Phương pháp 1, sử dụng hai mảng con tạm thời:
#includesử dụng không gian tên std ;
khoảng trống hợp nhất ( int mảng [ ] , int tôi , int tôi , int r )
{
int n1 = tôi - tôi + 1 ;
int n2 = r - tôi ;
int l [ n1 ] , r [ n2 ] ;
vì ( int Tôi = 0 ; Tôi < n1 ; Tôi ++ )
l [ Tôi ] = mảng [ tôi + Tôi ] ;
vì ( int j = 0 ; j < n2 ; j ++ )
r [ j ] = mảng [ tôi + 1 + j ] ;
int Tôi = 0 , j = 0 , k = tôi ;
trong khi ( Tôi < n1 && j < n2 ) {
nếu như ( l [ Tôi ] <= r [ j ] ) {
mảng [ k ] = l [ Tôi ] ;
Tôi ++;
}
khác {
mảng [ k ] = r [ j ] ;
j ++;
}
k ++;
}
trong khi ( Tôi < n1 ) {
mảng [ k ] = l [ Tôi ] ;
Tôi ++;
k ++;
}
trong khi ( j < n2 ) {
mảng [ k ] = r [ j ] ;
j ++;
k ++;
}
}
khoảng trống hợp nhấtSắp xếp ( int mảng [ ] , int tôi , int r )
{
nếu như ( tôi < r ) {
int tôi = tôi + ( r - tôi ) / 2 ;
hợp nhấtSắp xếp ( mảng , tôi , tôi ) ;
hợp nhấtSắp xếp ( mảng , tôi + 1 , r ) ;
hợp nhất ( mảng , tôi , tôi , r ) ;
}
}
int chủ yếu ( )
{
int mảng [ ] = { 12 , mười một , 13 , 5 , 6 , 7 } ;
int mảng_size = kích thước của ( mảng ) / kích thước của ( mảng [ 0 ] ) ;
cout << 'Mảng đã cho là \N ' ;
vì ( int Tôi = 0 ; Tôi < mảng_size ; Tôi ++ )
cout << mảng [ Tôi ] << '' ;
hợp nhấtSắp xếp ( mảng , 0 , mảng_size - 1 ) ;
cout << ' \N Mảng được sắp xếp là \N ' ;
vì ( int Tôi = 0 ; Tôi < mảng_size ; Tôi ++ )
cout << mảng [ Tôi ] << '' ;
trở lại 0 ;
}
Trong chương trình này, hàm hợp nhất nhận ba đối số arr, l và r, đại diện cho mảng cần sắp xếp và hiển thị các chỉ số của mảng con cần được hợp nhất. Trước tiên, hàm tìm kích thước của hai mảng con sẽ được hợp nhất, sau đó tạo hai mảng con tạm thời L và R để lưu trữ các phần tử của các mảng con này. Sau đó, nó so sánh các phần tử trong L và R và hợp nhất chúng thành mảng ban đầu có tên mảng theo thứ tự tăng dần.
Kỹ thuật chia để trị được sử dụng bởi hàm mergeSort để chia mảng thành hai nửa theo cách đệ quy cho đến khi chỉ còn lại một phần tử trong mảng con. Sau đó, nó hợp nhất hai mảng con thành một mảng con được sắp xếp. Hàm tiếp tục hợp nhất các mảng con trừ khi nó sắp xếp mảng hoàn chỉnh.
Trong hàm main, chúng ta định nghĩa một mảng arr có 6 phần tử và gọi hàm mergeSort để sắp xếp. Ở cuối đoạn mã, mảng đã sắp xếp được in ra.
Phương pháp 2 – Sử dụng One Temp Subarray
Đây là một chương trình mẫu để sắp xếp hợp nhất trong C++ bằng Phương pháp 2, sử dụng một mảng con tạm thời duy nhất:
#includesử dụng không gian tên std ;
khoảng trống hợp nhất ( int mảng [ ] , int tôi , int tôi , int r )
{
int Tôi , j , k ;
int n1 = tôi - tôi + 1 ;
int n2 = r - tôi ;
// Tạo mảng con tạm thời
int L [ n1 ] , r [ n2 ] ;
// Copy dữ liệu vào mảng con
vì ( Tôi = 0 ; Tôi < n1 ; Tôi ++ )
L [ Tôi ] = mảng [ tôi + Tôi ] ;
vì ( j = 0 ; j < n2 ; j ++ )
r [ j ] = mảng [ tôi + 1 + j ] ;
// Hợp nhất các mảng con tạm thời trở lại mảng ban đầu
Tôi = 0 ;
j = 0 ;
k = tôi ;
trong khi ( Tôi < n1 && j < n2 ) {
nếu như ( L [ Tôi ] <= r [ j ] ) {
mảng [ k ] = L [ Tôi ] ;
Tôi ++;
}
khác {
mảng [ k ] = r [ j ] ;
j ++;
}
k ++;
}
// Sao chép các phần tử còn lại của L[]
trong khi ( Tôi < n1 ) {
mảng [ k ] = L [ Tôi ] ;
Tôi ++;
k ++;
}
// Sao chép các phần tử còn lại của R[]
trong khi ( j < n2 ) {
mảng [ k ] = r [ j ] ;
j ++;
k ++;
}
}
khoảng trống hợp nhấtSắp xếp ( int mảng [ ] , int tôi , int r )
{
nếu như ( tôi < r ) {
int tôi = tôi + ( r - tôi ) / 2 ;
// Sắp xếp đệ quy nửa bên trái và bên phải
hợp nhấtSắp xếp ( mảng , tôi , tôi ) ;
hợp nhấtSắp xếp ( mảng , tôi + 1 , r ) ;
// Hợp nhất hai nửa đã sắp xếp
hợp nhất ( mảng , tôi , tôi , r ) ;
}
}
int chủ yếu ( )
{
int mảng [ ] = { 12 , mười một , 13 , 5 , 6 , 7 } ;
int mảng_size = kích thước của ( mảng ) / kích thước của ( mảng [ 0 ] ) ;
cout << 'Mảng đã cho là \N ' ;
vì ( int Tôi = 0 ; Tôi < mảng_size ; Tôi ++ )
cout << mảng [ Tôi ] << '' ;
hợp nhấtSắp xếp ( mảng , 0 , mảng_size - 1 ) ;
cout << ' \N Mảng được sắp xếp là \N ' ;
vì ( int Tôi = 0 ; Tôi < mảng_size ; Tôi ++ )
cout << mảng [ Tôi ] << '' ;
trở lại 0 ;
}
Chương trình này giống như chương trình trước, nhưng thay vì sử dụng hai mảng con tạm thời L và R, nó sử dụng một tạm thời mảng con tạm thời duy nhất. Chức năng hợp nhất hoạt động theo cách tương tự như trước đây, nhưng thay vì sao chép dữ liệu vào L và R, nó sao chép dữ liệu vào tạm thời. Sau đó, nó hợp nhất các phần tử mảng tạm thời trở lại vào mảng đó là mảng ban đầu.
Hàm mergeSort giống như trước đây, ngoại trừ việc nó sử dụng tạm thời thay vì L và R để lưu trữ mảng con tạm thời.
Trong hàm main, chúng ta định nghĩa một mảng arr có 6 phần tử và gọi hàm mergeSort để sắp xếp. Việc thực thi mã kết thúc bằng cách in mảng đã sắp xếp trên màn hình.
Phần kết luận
Hợp nhất sắp xếp là một thuật toán sắp xếp các phần tử mảng và nó sử dụng kỹ thuật chia để trị và so sánh giữa các phần tử. Hợp nhất sắp xếp trong C++ có độ phức tạp về thời gian là O(n log n) và đặc biệt hiệu quả để sắp xếp các mảng lớn. Mặc dù nó yêu cầu bộ nhớ bổ sung để lưu trữ các mảng con đã hợp nhất, nhưng tính ổn định của nó khiến nó trở thành lựa chọn phổ biến để sắp xếp.