Giải Thuật sắp xếp: Selection Sort

Selection sort là 1 giải thuật dựa trên ý tưởng :

Ví dụ: chúng ta có 1 array gồm có 3 phần tử 5,3 và 9 và sẽ sắp xếp theo thứ tự tăng dần. Vậy đầu tiên chúng ta cần tìm phần tử nhỏ nhất trong array để có thể mang nó lên vị trí đầu tiên. *tìm kiếm các thứ* À phần tử nhỏ nhất là 3 chúng ta sẽ hoán đổi 3 và phần tử ở ô đầu tiên của array 3 sẽ đổi chỗ với 5.

Và đây là array sau khi hoán đổi vị trí. Sau đó lại tiếp tục lặp qua array tìm phần tử nhỏ nhất (không tính số 3 vì nó đã đúng vị trí rồi). Đó là số 4 chúng ta tiếp tục hoán đổi vị trí của 4 và số ở ô thứ 2. 1 lần nữa lại là số 5, đổi chỗ nào.

Alright!! Có vẻ như gần xong rồi, anh em đã hiểu hết chưaaa? Cùng chạy lần nữa để có 1 array đẹp nhé 🙃 🙃. Vẫn với vòng lặp chúng ta lại tìm số nhỏ nhất (ngoại trừ 3 và 4).

Tìm thấy rồi nó là số 5 huyền thoại. Vậy công việc là swap số 5 và 9 thôi.

*Taa đaa* công trình hoàn tất rồi, chúng ta đã có 1 array đã được sắp xếp theo thứ tự tăng dần rồi nhé.

chúng ta sẽ sử dụng 2 vòng lặp. Vòng lặp ngoài sẽ chạy từ đầu đến phần tử cuối cùng của mảng, vòng lặp thứ 2 sẽ chạy từ vị trí hiện tại của vòng lặp ngoài + 1. Tìm phần tử nhỏ nhất, rồi swap chúng với nhau. Có thể swap bằng cách khác không sử dụng biến tạm (mình có comment đó đó). Vậy thôi đó. hihi.

Đúng là 1 phương pháp sort rất đơn giản và dễ hiểu. Nhưng dễ ta thì chậm máy, đúng như vậy, giải thuật này sử dụng 2 vòng lặp lồng nhau. Vì vậy trường hợp xấu nhất Time Complexity sẽ là O(n²). Vì vậy đây là 1 giải thuật có performance rất kém 🙈🙈🙈🙈 .

Trong bài viết của mình hôm nay thì chúng ta đã cùng nhau đi qua giải thuật Selection sort, xem cách thức hoạt động cũng như triển khai nó. thật sự là mình cũng chỉ mới tập tành viết lách nên có thể không thật sự mạch lạc, và có nhiều sai sót. Anh em bỏ qua hen. Chúc anh em 1 ngày tốt lành ❤️❤️❤️.