Bạn đang xem: Selection sort là gì
Selection Sort (sắp xếp chọn) là một thuật toán sắp xếp đơn giảndựa trên so sánh tại chỗ, trong đó:Danh sách được chia thành hai phần (Trái – Phải) (Vẫn là cùng một mảng nhé)Phần được sắp xếp ở đầu bên trái và phần chưa được sắp xếp ở đầu bên phảiLúc đầu thì phần bên phải là toàn bộ danh sách. (Vì phần bên trái chưa sắp xếp mà)Mỗi lần lặp chúng ta sẽ liên tục tìm giá trị nhỏ nhất ở phần bên phải, hoán đổi vị trí của nó cho phần tử ngoài cùng bên trái.
Xem thêm: Link Là Gì – đường Link
Quá trình này tiếp tục di chuyển qua lại mảng chưa được sắp xếp bởi một phần tử sang phải.Ý tưởng của thuật toán này cũng đơn giản không kém sắp xếp nổi bọt:
Giả sử, ta chọn được phần tử có giá trị nhỏ nhấtnhất trên mảng là A. với vị trí là k.Tráo đổi A với A, vậy thì lúc này ta sẽ nhận được A là phần tử có giá trị nhỏ nhất.Giả sử đến bước thứ i ta đã có A. Bây giờ ta cần tìm thành phần có giá trị nhỏ nhấttrong các phần tử từ A đến A.Giả sử phần tửđó có vị trí là tcó giá trịA sao cho i Ta lại tráo đổi A với A. Lặp lại cho tới i = n – 1Cuồi cùng, ta có mảng A được sắp xếp.
Xem thêm: Đắp Lá Gì Để Hút Mủ – 8 Cách Chữa Trị Ngay Tại Nhà Nhanh Chóng
Thuật toán này không phù hợp với các tập dữ liệu lớn vì độ phức tạp trung bình.Khi bạn sắp xếp với một cơ sở dữ liệu lớn thì quá trình này sẽ chậm và tốn nhiều bộ nhớ máy tính.Độ phức tạp của selection sort là: O(n2)
2.1. Giải thuật Selection Sort
Để bạn dần hiểu rõ hơn về thuật toán Selection Sort, hãy xem giải thuật của nó:Bước 1: Chọn phần tử có khóa nhỏ nhất trong n phần tử từ a đến a và hoán vị nó với phần tử a.Bước 2: Chọn phần tử có khóa nhỏ nhất trong n – 1 phần tử từ a đến a và hoán vị nó với a.Tổng quát ở bước thứ i chọn phần tử có khóa nhỏ nhất trong n – i phần tử từ a đến a và hoán vị nó với a.Sau n – 1 bước thì mảng đã được sắp xếp.
2.2. Phương pháp chọn khóa hoặc phần tử đầu tiên
Ý tưởng và giải thuật là thế, nhưng mình biết rằng có rất nhiều bạn chưa hình dung ra đâu, vì thế, hãy đi sâu hơn về cách làm. Phương pháp chọn key hoặc phần tử đầu tiên:Bước 1: Đầu tiên ta đặt khóa nhỏ nhất là khóa của a (lowkey = akey) và chỉ số của phần tử có khóa nhỏ nhất là là i (lowindex = i).Bước 2: Xét các phần tử a với j từ i + 1 đến n -1, nếu khóa của a nhỏ hơn khóa nhỏ nhất (a.key ) thì đặt lại khóa nhỏ nhất là là khóa của a (lowkey = a.key). Và phần tử có khóa nhỏ nhất là j (lowendex = j).Bước 3: Khi đã xét hết các phần tử a với j > n- 1 thì phần tử có khóa nhỏ nhất là aVí dụ, ta có một mảng như thế này:
Tìm phần tử nhỏ nhất trong arr và đặt nó ở đầu (Hoán đổi giá trị với phần tử đầu arr
Chuyên mục: Hỏi Đáp
