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

Hello mọi người, hôm nay chúng ta sẽ cùng tiếp tục với series Giải thuật sắp xếp nhe mọi người. Và vị khách mời ngày hôm nay

Selection sort, 1 giải thuật khá là quen mặt và đơn giản trong làng sorting phải không? Nếu không thì cùng nhau tìm hiểu về Selection sort nhé

Selection sort là gì?

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

tìm phần tử nhỏ nhất (hoặc lớn nhất) trong một mảng chưa sắp xếp và sau đó đặt nó vào vị trí chính xác của nó trong một mảng được sắp xếp.

Selection sort hoạt động như thế nào?

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é.

Code như thế nào?

Hãy cùng nhau implement xem như thế nào nhé.

bằng 1 cách nào đó tui không làm đc code snippet nên tui chụp tấm hình, ae thông cảm:)

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.

Time Complexity

Đú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 🙈🙈🙈🙈 .

Kết

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 ❤️❤️❤️.

hehe