Sự khác biệt giữa Sắp xếp chèn và Sắp xếp lựa chọn

Sự khác biệt chính - Chèn Sắp xếp so với Lựa chọn Sắp xếp
 

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 bộ sưu tập dữ liệu. Đôi khi cần phải 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 việc sắp xếp, dữ liệu được sắp xếp theo thứ tự số hoặc từ vựng. Nếu dữ liệu được sắp xếp hợp lý, thì nó 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 thứ tự, thì thật khó để tìm thấy một số điện thoại cụ thể. Theo cùng một cách, nếu các từ trong từ điển không được sắp xếp theo thứ tự bảng chữ cái, sẽ rất khó để tìm từ. Do đó, phân loại là 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 bộ sưu tậ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ử với 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 . Các 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ử cùng một lúc 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ó.

NỘI DUNG

1. Tổng quan và sự khác biệt chính
2. Sắp xếp chèn là gì
3. Sắp xếp lựa chọn là gì
4. Điểm tương đồng giữa Sắp xếp chèn và Sắp xếp lựa chọn
5. So sánh cạnh nhau - Sắp xếp chèn so với Sắp xếp lựa chọn ở dạng bảng
6. Tóm tắt

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 sắp xếp được di chuyển và chèn vào danh sách con được 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 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 trái. 77, là yếu tố đầu tiên và không có yếu tố nào ở phía 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. Sau đó cả hai giá trị này được hoán đổi. Bây giờ 33 ở chỉ số 0 và 77 ở chỉ số 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 hoán đổi. Bây giờ mảng là 33,44,77,11,88. Nó là cần thiết để so sánh tất cả các yếu tố bên trái. Vì vậy, 44 được so sánh với 33. 33 nhỏ hơn 44. Vì vậy, các 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 cái đó được hoán đổi. 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 hoán đổi. 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.

Bây giờ mảng là 11,33,44,77,88.

Tăng chỉ số sẽ làm cho chỉ số thành 4. Giá trị là 88. Nó cao hơn 77. Vì vậy, không cần phải trao đổ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 đầu ra 11,33,44,77,88.

Lựa chọn sắp xếp là gì?

Lựa chọn sắp xếp 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 các phần. Phần được sắp xếp nằm ở cuối bên trái. Phần chưa 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 các yếu tố bên trái. Bây giờ phần tử đó nằm trong mảng được 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 yếu tố sang phải. Thuật toán sắp xếp lựa chọn có thể được giải thích bằ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, nhỏ nhất trong mảng đượ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ỉ mục 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ỉ mục 0, vì vậy 11 hiện được sắp xếp. Từ các phần tử còn lại, nhỏ nhất là 22. Nó được hoán đổi với 1^thứ yếu tố chỉ số.

Bây giờ mảng là 11,22,44,77,88,33.

Các yếu 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 2^thứ yếu tố chỉ số.

Bây giờ mảng là 11,22,33,77,88,44.

Các yếu 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 3^{lần thứ} yếu tố chỉ số.

Bây giờ mảng là 11,22,33,44,88,66.

Các yếu 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 4^{thứ tự} yếu tố chỉ số.

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ụ 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 đầu ra 11,33,44,77,88.

Điểm giống nhau giữa Sắp xếp chèn và Sắp xếp lựa chọn?

• Cả Sắp xếp chèn và Sắp xếp lựa chọn đều là 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ử với 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.
Quá trình
Sắp xếp chèn là sắp xếp danh sách phụ 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 nó với vị trí đầu tiên, một lần nữa chọn mức tối thiểu cho phần còn lại và hoán đổi 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.	Lựa chọn sắp xếp không phải là một thuật toán sắp xếp ổn định.

Tóm tắt - Chèn Sắp xếp so với Lựa chọn Sắp xếp 

Đô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ử với 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 của Sắp xếp chèn so với 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 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

Tài liệu tham khảo:

1. Điểm, Hướng dẫn. Cấu trúc dữ liệu và các thuật toán chèn sắp xếp. Www.tutorialspoint.com, Điểm hướng dẫn, ngày 8 tháng 1 năm 2018. Có sẵn tại đây
2. Sắp xếp sắp xếp trong cấu trúc dữ liệu | Hướng dẫn cấu trúc dữ liệu | Học tập Có sẵn ở đây
3. Lý thuyết. Lựa chọn, chèn và sắp xếp bong bóng. TheoryApp, ngày 20 tháng 1 năm 2014. Có sẵn tại đây
4. Sắp xếp sắp xếp trong cấu trúc dữ liệu | Hướng dẫn cấu trúc dữ liệu | Học tập Có sẵn ở đây