Sự khác biệt chính - Sắp xếp chèn so với Sắp xếp lựa chọn
Sắp xếp chèn và sắp xếp lựa chọn là hai thuật toán sắp xếp được sử dụng để sắp xếp một tập hợp dữ liệu. Đôi khi cần sắp xếp dữ liệu theo một thứ tự cụ thể. Các thuật toán sắp xếp là các cơ chế để sắp xếp một tập hợp dữ liệu. Trong phân loại, dữ liệu được sắp xếp theo thứ tự số hoặc từ điển. Nếu dữ liệu được sắp xếp đúng cách, thì sẽ dễ dàng tìm kiếm dữ liệu nhanh hơn. Nếu các số điện thoại trong danh bạ điện thoại không được sắp xếp theo cách sắp xếp, thì rất khó để tìm một số điện thoại cụ thể. Tương tự như vậy, nếu các từ trong từ điển không được sắp xếp theo thứ tự bảng chữ cái, bạn sẽ rất khó tìm từ. Vì vậy, việc phân loại rất hữu ích trong cuộc sống hàng ngày. Trong Khoa học Máy tính, có các thuật toán sắp xếp để sắp xếp một tập hợp dữ liệu. Hai thuật toán như vậy là sắp xếp chèn và sắp xếp lựa chọn. Sắp xếp chèn là thuật toán sắp xếp sắp xếp mảng bằng cách dịch chuyển từng phần tử một. Sắp xếp lựa chọn là thuật toán sắp xếp tìm phần tử nhỏ nhất trong mảng và trao đổi phần tử có vị trí đầu tiên, sau đó tìm phần tử nhỏ thứ hai và trao đổi nó với phần tử ở vị trí thứ hai và tiếp tục quá trình cho đến khi toàn bộ mảng được sắp xếp. Sự khác biệt chính giữa sắp xếp chèn và sắp xếp lựa chọn là sắp xếp chèn so sánh hai phần tử tại một thời điểm trong khi sắp xếp lựa chọn chọn phần tử tối thiểu từ toàn bộ mảng và sắp xếp nó.
Sắp xếp Chèn là gì?
Sắp xếp chèn là một thuật toán sắp xếp dựa trên so sánh tại chỗ. Trong phương pháp này, mảng được tìm kiếm từng bước. Các mục chưa được sắp xếp được di chuyển và chèn vào danh sách con đã sắp xếp của mảng. Thuật toán sắp xếp chèn có thể được giải thích bằng cách sử dụng ví dụ sau.
Ví dụ: lấy mảng ban đầu là 77, 33, 44, 11, 88. Trong thuật toán sắp xếp này, bước đầu tiên là chọn phần tử hiện tại.
Phần tử hiện tại là 77. Phần tử hiện tại được so sánh với tất cả các phần tử ở phía bên tay trái. 77, là phần tử đầu tiên và không có phần tử nào ở bên trái. Chỉ số của vị trí hiện tại là 0.
Sau đó, chỉ số của vị trí hiện tại được tăng thêm 1. Bây giờ chỉ số là 1 và phần tử hiện tại là 33. Khi so sánh nó với phần tử ở bên trái, nó nhỏ hơn 77. Khi đó cả hai giá trị này được hoán đổi. Bây giờ 33 ở chỉ mục 0 và 77 ở chỉ mục 1.
Bây giờ mảng là 33, 77, 44, 11, 88.
Một lần nữa, chỉ số được tăng lên. Chỉ số là 2 và phần tử hiện tại là 44. Nó được so sánh với các phần tử ở phía bên trái. 44 nhỏ hơn 77. Vì vậy, hai giá trị đó được đổi chỗ cho nhau. Bây giờ mảng là 33, 44, 77, 11, 88. Cần phải so sánh tất cả các phần tử bên trái. Vì vậy, 44 được so sánh với 33. 33 nhỏ hơn 44. Vì vậy, những yếu tố đó không cần phải trao đổi.
Bây giờ mảng là 33, 44, 77, 11, 88.
Một lần nữa, chỉ số được tăng lên. Chỉ số là 3 và phần tử hiện tại là 11. Nó được so sánh với tất cả các phần tử ở bên trái. 11 nhỏ hơn 77, vì vậy hai số đó được đổi chỗ cho nhau. Bây giờ mảng là 33, 44, 11, 77, 88. Khi so sánh 11 và 44, 11 nhỏ hơn 44. Vì vậy, hai cái đó được đổi chỗ cho nhau. Bây giờ các mảng là 33, 11, 44, 77, 88. Một lần nữa 11 được so sánh với 33. 11 nhỏ hơn 33, vì vậy hai giá trị đó được hoán đổi cho nhau.
Bây giờ mảng là 11, 33, 44, 77, 88.
Tăng chỉ số sẽ làm cho chỉ số lên 4. Giá trị là 88. Nó cao hơn 77. Vì vậy, không cần phải hoán đổi. Cuối cùng, mảng được sắp xếp là 11, 33, 44, 77, 88.
Hình 01: Ví dụ sắp xếp chèn
Việc thực hiện sắp xếp chèn như trên. Mảng ban đầu là 77, 33, 44, 11, 88. Sau khi sắp xếp, nó cho kết quả là 11, 33, 44, 77, 88.
Sắp xếp Lựa chọn là gì?
Sắp xếp lựa chọn là một thuật toán sắp xếp dựa trên so sánh tại chỗ. Các mảng được chia thành nhiều phần. Phần được sắp xếp nằm ở cuối bên trái. Phần không được sắp xếp nằm ở cuối bên phải. Đầu tiên, giá trị nhỏ nhất nên được tìm thấy. Sau đó, nó được hoán đổi với phần tử bên trái. Bây giờ phần tử đó nằm trong mảng đã sắp xếp. Quá trình này tiếp tục di chuyển ranh giới mảng chưa được sắp xếp từ một phần tử sang bên phải. Thuật toán sắp xếp lựa chọn có thể được giải thích bằng cách sử dụng ví dụ sau.
Ví dụ: lấy mảng ban đầu là 77, 33, 44, 11, 88, 22. Trong thuật toán sắp xếp này, mảng nhỏ nhất được tìm thấy. Phần tử nhỏ nhất là 11. Nó được hoán đổi với phần tử trong chỉ số 0 của mảng.
Bây giờ mảng là 11, 33, 44, 77, 88, 22.
Phần tử nhỏ nhất nằm trong chỉ số 0, vì vậy 11 bây giờ được sắp xếp. Từ các phần tử còn lại, phần tử nhỏ nhất là 22. Nó được hoán đổi với phần tử chỉ số 1st.
Bây giờ mảng là 11, 22, 44, 77, 88, 33.
Các phần tử 11 và 22 đã được sắp xếp. Từ phần còn lại, giá trị nhỏ nhất là 33. Nó được hoán đổi với phần tử chỉ số 2nd.
Bây giờ mảng là 11, 22, 33, 77, 88, 44.
Các phần tử 11, 22 và 33 đã được sắp xếp. Từ phần còn lại, giá trị nhỏ nhất là 44. Nó được hoán đổi với phần tử chỉ số 3rd.
Bây giờ mảng là 11, 22, 33, 44, 88, 66.
Các phần tử 11, 22, 33, 44 đã được sắp xếp. Các phần tử còn lại là 88 và 66. Phần tử 66 được hoán đổi với phần tử chỉ số 4th.
Bây giờ mảng là 11, 22, 33, 44, 66, 88.
Đây là mảng được sắp xếp sử dụng thuật toán sắp xếp lựa chọn.
Hình 02: Ví dụ về Sắp xếp Lựa chọn
Việc thực hiện sắp xếp chèn như trên. Mảng ban đầu là 77, 33, 44, 11, 88. Sau khi sắp xếp, nó cho kết quả 11, 33, 44, 77, 88.
Sự giống nhau giữa Sắp xếp Chèn và Sắp xếp Lựa chọn là gì?
Cả Sắp xếp Chèn và Sắp xếp Lựa chọn đều là các thuật toán sắp xếp
Sự khác biệt giữa Sắp xếp Chèn và Sắp xếp Lựa chọn là gì?
Sắp xếp chèn so với Sắp xếp lựa chọn |
|
| Sắp xếp chèn là thuật toán sắp xếp sắp xếp mảng bằng cách dịch chuyển từng phần tử một. | Sắp xếp lựa chọn là thuật toán sắp xếp tìm phần tử nhỏ nhất trong mảng và trao đổi phần tử có vị trí đầu tiên, sau đó tìm phần tử nhỏ thứ hai và trao đổi nó với phần tử ở vị trí thứ hai và tiếp tục quá trình cho đến toàn bộ mảng được sắp xếp. |
| Quy trình | |
| Sắp xếp chèn là sắp xếp danh sách con bằng cách so sánh hai phần tử cho đến khi toàn bộ mảng được sắp xếp. | Sắp xếp lựa chọn chọn phần tử tối thiểu và hoán đổi phần tử đó với vị trí đầu tiên, lại chọn phần tử tối thiểu cho phần còn lại và hoán đổi phần tử đó thành vị trí thứ hai và tiếp tục quá trình này cho đến khi kết thúc. |
| Ổn định | |
| Sắp xếp chèn là một thuật toán sắp xếp ổn định. | Sắp xếp lựa chọn không phải là một thuật toán sắp xếp ổn định. |
Tóm tắt - Sắp xếp chèn so với Sắp xếp lựa chọn
Đôi khi cần phải sắp xếp dữ liệu. Trong Khoa học Máy tính, có các thuật toán để sắp xếp dữ liệu. Bài viết này đã thảo luận về hai thuật toán sắp xếp là sắp xếp chèn và sắp xếp lựa chọn. Sắp xếp chèn là thuật toán sắp xếp sắp xếp mảng bằng cách dịch chuyển từng phần tử một. Sắp xếp lựa chọn là thuật toán sắp xếp tìm phần tử nhỏ nhất trong mảng và trao đổi phần tử có vị trí đầu tiên, sau đó tìm phần tử nhỏ thứ hai và trao đổi nó với phần tử ở vị trí thứ hai và tiếp tục quá trình cho đến khi toàn bộ mảng được sắp xếp. Sự khác biệt giữa sắp xếp chèn và sắp xếp lựa chọn là sắp xếp chèn so sánh hai phần tử tại một thời điểm trong khi sắp xếp lựa chọn chọn phần tử tối thiểu từ toàn bộ mảng và sắp xếp nó.
Tải xuống bản PDF Phân loại Chèn và Sắp xếp Lựa chọn
Bạn có thể tải xuống phiên bản PDF của bài viết này và sử dụng nó cho các mục đích ngoại tuyến theo ghi chú trích dẫn. Vui lòng tải xuống phiên bản PDF tại đây: Sự khác biệt giữa Sắp xếp Chèn và Sắp xếp Lựa chọn
