Cả hai kỹ thuật sắp xếp, sắp xếp nhanh và sắp xếp hợp nhất đều được xây dựng trên phương pháp phân chia và chinh phục trong đó tập hợp các phần tử được tách ra và sau đó kết hợp lại sau khi sắp xếp lại. Sắp xếp nhanh thường đòi hỏi nhiều so sánh hơn so với sắp xếp hợp nhất để sắp xếp một tập hợp lớn các phần tử.
Biểu đồ so sánh
| Cơ sở để so sánh | Sắp xếp nhanh chóng | Hợp nhất sắp xếp |
|---|---|---|
| Phân vùng các phần tử trong mảng | Việc chia một danh sách các yếu tố không nhất thiết phải chia thành một nửa. | Mảng luôn được chia thành một nửa (n / 2). |
| Trường hợp phức tạp nhất | O (n2) | O (n log n) |
| Hoạt động tốt trên | Mảng nhỏ hơn | Hoạt động tốt trong bất kỳ loại mảng. |
| Tốc độ | Nhanh hơn các thuật toán sắp xếp khác cho tập dữ liệu nhỏ. | Tốc độ phù hợp trong tất cả các loại tập dữ liệu. |
| Yêu cầu không gian lưu trữ bổ sung | Ít hơn | Hơn |
| Hiệu quả | Không hiệu quả cho mảng lớn hơn. | Hiệu quả hơn. |
| Phương pháp sắp xếp | Nội bộ | Bên ngoài |
Định nghĩa sắp xếp nhanh
Sắp xếp nhanh là thuật toán sắp xếp được sử dụng phổ biến vì nó nhanh cho các mảng ngắn. Tập hợp các phần tử được chia thành nhiều phần cho đến khi không thể chia nó thêm nữa. Sắp xếp nhanh còn được gọi là sắp xếp trao đổi phân vùng . Nó sử dụng một yếu tố chính (được gọi là trục) để phân vùng các yếu tố. Một phân vùng chứa các phần tử nhỏ hơn phần tử chính. Một phân vùng khác chứa các phần tử lớn hơn phần tử chính. Các yếu tố được sắp xếp đệ quy.
Giả sử A là một mảng A [1], A [2], A [3], nam .., A [n] của số n phải được sắp xếp. Thuật toán sắp xếp nhanh bao gồm các bước sau.
- Phần tử đầu tiên hoặc bất kỳ phần tử ngẫu nhiên nào được chọn làm khóa, giả sử khóa = A (1).
- Con trỏ thấp ở mức thấp nhất được đặt ở con trỏ thứ hai và con trỏ lên trên được đặt ở phần tử cuối cùng của mảng, tức là low = 2 và up = n;
- Một cách nhất quán, tăng con trỏ thấp của người dùng trên một vị trí cho đến khi (phím A [thấp]>).
- Liên tục, giảm con trỏ của Up lên trên một vị trí cho đến khi (A [up] <= key).
- Nếu tăng lớn hơn trao đổi thấp A [thấp] với A [lên].
- Lặp lại bước 3, 4 và 5 cho đến khi điều kiện ở bước 5 không thành công (nghĩa là tăng <= thấp) sau đó trao đổi A [lên] bằng phím.
- Nếu các phần tử bên trái của khóa nhỏ hơn khóa và các phần tử bên phải của khóa lớn hơn khóa thì mảng được phân vùng thành hai mảng phụ.
- Quy trình trên được lặp đi lặp lại cho các tập hợp con cho đến khi toàn bộ mảng được sắp xếp.
Ưu điểm và nhược điểm
Nó có một hành vi trường hợp trung bình tốt. Độ phức tạp thời gian chạy của sắp xếp nhanh là tốt, nó nhanh hơn các thuật toán như sắp xếp bong bóng, sắp xếp chèn và sắp xếp lựa chọn. Tuy nhiên, nó phức tạp và rất đệ quy, đó là lý do nó không phù hợp với các mảng lớn.
Định nghĩa sắp xếp hợp nhất
Hợp nhất sắp xếp là một thuật toán bên ngoài cũng dựa trên chiến lược phân chia và chinh phục. Các phần tử được phân chia thành các mảng con (n / 2) nhiều lần cho đến khi chỉ còn một phần tử, điều này làm giảm đáng kể thời gian sắp xếp. Nó sử dụng lưu trữ bổ sung để lưu trữ các mảng phụ trợ. Hợp nhất sắp xếp sử dụng ba mảng trong đó hai mảng được sử dụng để lưu trữ mỗi nửa và mảng thứ ba được sử dụng để lưu trữ danh sách được sắp xếp cuối cùng. Mỗi mảng sau đó được sắp xếp đệ quy. Cuối cùng, các tập hợp con được hợp nhất để làm cho nó có kích thước phần tử n của mảng. Danh sách luôn được chia thành chỉ một nửa (n / 2) để sắp xếp nhanh chóng.
Đặt A là mảng gồm n số phần tử được sắp xếp A [1], A [2], Tiêu, A, n [n]. Sắp xếp hợp nhất theo các bước nhất định.
- Chia mảng A thành khoảng n / 2 mảng con được sắp xếp theo 2, có nghĩa là các phần tử trong (A [1], A [2]), (A [3], A [4]), (A [ các mảng con k [, A [k + 1]), (A [n-1], A [n]) phải theo thứ tự sắp xếp.
- Kết hợp mỗi cặp cặp để có được danh sách các tập hợp con được sắp xếp có kích thước 4; các phần tử trong các phần con cũng theo thứ tự được sắp xếp, (A [1], A [2], A [3], A [4]), Hay, (A [k-1], A [k], A [k + 1], A [k + 2]), Mạnh., (A [n-3], A [n-2], A [n-1], A [n]).
- Bước 2 được lặp đi lặp lại cho đến khi chỉ có một mảng được sắp xếp có kích thước n.
Ưu điểm và nhược điểm
Thuật toán sắp xếp hợp nhất thực hiện theo cách chính xác và chính xác bất kể số lượng phần tử liên quan đến việc sắp xếp. Nó hoạt động tốt ngay cả với tập dữ liệu lớn. Tuy nhiên, nó tiêu thụ phần lớn hơn của bộ nhớ.
Sự khác biệt chính giữa Sắp xếp nhanh và Sắp xếp hợp nhất
- Trong sắp xếp hợp nhất, mảng phải được chia thành hai nửa (tức là n / 2). Đối với, trong sắp xếp nhanh chóng, không có sự bắt buộc chia danh sách thành các yếu tố bằng nhau.
- Sự phức tạp tồi tệ nhất của sắp xếp nhanh là O (n2) vì nó cần nhiều so sánh hơn trong điều kiện tồi tệ nhất. Ngược lại, sắp xếp hợp nhất có cùng độ phức tạp và trường hợp xấu nhất, đó là O (n log n).
- Hợp nhất sắp xếp có thể hoạt động tốt trên bất kỳ loại tập dữ liệu nào cho dù nó lớn hay nhỏ. Ngược lại, sắp xếp nhanh không thể hoạt động tốt với các bộ dữ liệu lớn.
- Sắp xếp nhanh nhanh hơn sắp xếp hợp nhất trong một số trường hợp như đối với các tập dữ liệu nhỏ.
- Sắp xếp hợp nhất yêu cầu không gian bộ nhớ bổ sung để lưu trữ các mảng phụ trợ. Mặt khác, sắp xếp nhanh không cần nhiều không gian để lưu trữ thêm.
- Hợp nhất sắp xếp hiệu quả hơn sắp xếp nhanh chóng.
- Sắp xếp nhanh là phương pháp sắp xếp nội bộ trong đó dữ liệu sẽ được sắp xếp được điều chỉnh tại một thời điểm trong bộ nhớ chính. Ngược lại, sắp xếp hợp nhất là phương pháp sắp xếp bên ngoài, trong đó dữ liệu được sắp xếp không thể được cung cấp trong bộ nhớ cùng một lúc và một số phải được lưu trong bộ nhớ phụ.
Phần kết luận
Sắp xếp nhanh là trường hợp nhanh hơn nhưng không hiệu quả trong một số tình huống và cũng thực hiện rất nhiều so sánh so với sắp xếp hợp nhất. Mặc dù sắp xếp hợp nhất yêu cầu so sánh ít hơn, nó cần một không gian bộ nhớ bổ sung là 0 (n) để lưu trữ mảng bổ sung trong khi sắp xếp nhanh cần không gian của O (log n).
