Author: Jack Võ
Ngoài thuật toán tìm kiếm, trong bài học tuần này, chúng ta sẽ làm quen thêm một thuật toán quan trọng khác trong đời sống đó là thuật toán sắp xếp.
1. Định nghĩa
Thuật toán sắp xếp là thuật toán dùng để xếp lại vị trí thứ tự của các giá trị trong một tập hợp hay chuỗi dữ liệu theo thứ tự từ bé đến lớn hay lớn đến bé hay theo yêu cầu của người dùng/khách hàng. Thuật toán sắp xếp không chỉ có thể dùng với số mà còn thể dùng với kí tự.
2. Các thuật toán sắp xếp
Những thuật toán sắp xếp phổ biến:
a. Bubble Sort Algorithm (sắp xếp sủi bọt):
Thuật toán này sẽ sắp xếp các cặp số hay giá trị liền kề nhau bằng cách so sánh và hoán đổi giá trị của 2 số đó, và sẽ lặp lại cho đến khi dãy dữ liệu hoặc tập hợp đã theo thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp sủi bọt bằng hình động dưới đây.
Tên của thuật toán xuất phát từ việc các số nhỏ nhất hoặc lớn nhất “sủi bọt” lên vị trí đầu trong dãy số. Thuật toán sắp xếp sủi bọt dễ sử dụng và lập trình. Tuy nhiên, thuật toán này rất không hiệu quả với dãy có nhiều số.
b. Insertion Sort Algorithm (sắp xếp chèn):
Thuật toán này hoạt động bằng cách so sánh và xếp số có giá trị nhỏ nhất hoặc lớn nhất về hướng bên trái, và lặp lại đến khi dãy số đã vào thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp chèn bằng hình động dưới đây.
Thuật toán sắp xếp di chuyển một phần tử của dãy số từ phần chưa được sắp xếp và chèn vào phần đã được sắp xếp. Đó cũng chính là một phần lý do về tên gọi của thuật toán này. Chúng ta chắc đã từng một vài lần sử dụng thuật toán này để sắp xếp các lá bài trên tay khi chơi cùng bạn bè. Thuật toán sắp xếp chèn không tốn nhiều bộ nhớ và dễ sử dụng cho các dãy số có ít phần tử.
c. Selection Sort Algorithm (sắp xếp chọn lọc):
Thuật toán này sẽ liên tục chọn phần tử hay dữ liệu có giá trị nhỏ và sẽ đưa nó lên đầu, và sẽ tiếp tục lặp lại việc chọn phần tử để sắp xếp dãy số theo thứ tự tăng dần. Tương tự thuật toán có thể được sử dụng để sắp xếp dãy số theo thứ tự giảm dần bằng cách chọn phần tử có giá trị lớn để đưa lên đầu. Chính vì thế thuật toán có tên gọi là sắp xếp chọn lọc. Chúng ta có thể hình dung thuật toán sắp xếp chọn lọc bằng hình động dưới đây.
Thuật toán sắp xếp chọn lọc nhanh và hữu ích cho dãy số có nhiều phần tử. Tuy nhiên, thuật toán sắp xếp chọn lọc cũng không hiệu quả với dãy số có nhiều phần tử.
d. Merge Sort Algorithm (sắp xếp trộn):
Thuật toán này sẽ chia tập hợp hay mảng dữ liệu ra làm 2 nửa, rồi tiếp tục chia nửa các mảng nhỏ đó, rồi sắp xếp các giá trị trong các mảng nhỏ đó, và sau cùng sẽ gộp các mảng đó lại thành một mảng giá trị đã được sắp xếp. Đó cũng là lý do thuật toán có tên là sắp xếp trộn. Chúng ta có thể hình dung thuật toán bằng hình động dưới đây.
Thuật toán sắp xếp trộn hoạt động tốt với các dãy số có nhiều phần tử. Tuy nhiên thuật toán tốn nhiều dung lượng.
Ngoài ra còn có các thuật toán sắp xếp khác gồm:
- Quick Sort Algorithm
- Heap Sort Algorithm
- Counting Sort Algorithm
- Radix Sort Algorithm
- Bucket Sort Algorithm
- Shell Sort Algorithm
Không có thuận toán nào thật sự hoàn hảo, tùy vào trường hợp và lượng dữ liệu/thông tin mà thuật toán đó có thể phù hợp và sắp xếp nhanh hơn các thuật toán còn lại
3. Ứng dụng thực tế
Các thuật toán sắp xếp được ứng dụng trong nhiều lĩnh vực và công nghiệp như ngân hàng dùng để sắp xếp thống kê sổ sách tiền tệ, phân tích dữ liệu sẽ dùng thuật toán để sắp các dữ kiện theo thứ tự thích hợp để tiện cho việc xử lý và đưa ra các biểu đồ cũng như thông tin cho công ty chủ quản.
4. Cách để viết các thuật toán bằng Python
- Bubble Sort Algorithm
Pseudo Code:
for i in range of sample_list:
for j in range of sample_list:
// so sánh 2 số liền kề
if sample_list[j] > sample_list[j+1]:
// đổi vị trí 2 số đó
Ví dụ: như sắp xếp cho các bạn trong một hàng theo thứ tự từ thấp đến cao thì mình sẽ so sánh chiều cao của 2 bạn liền kề rồi mình sẽ đổi vị trí 2 bạn, ai lùn hơn thì mình đổi qua trái ai cao thì sẽ đổi qua bên phải và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao.
- Insertion Sort Algorithm
Pseudo Code:
// đặt 2 giá trị
position // giá trị position để mình theo dõi vị trí của số mình sắp xếp
insert_value // giá trị số mình sắp xếp
for i in range of sample_list:
insert_value = sample_list[i]
position = i
// tìm vị trí để sắp xếp số
while position > 0 and sample_list[position – 1] > insert_value:
// hoán đổi vị trí các số
sample_list[position] = sample_list[position – 1]
position = position – 1
// bỏ số đó vào vị trí đúng
sample_list[position] = insert_value
Ví dụ: như mình sắp xếp các bạn trong một hàng theo thứ tự từ thấp đến cao thì nếu như bạn đầu tiên đã là lùn nhất rồi thì mình sẽ giữ nguyên vị trí bạn đầu tiên, sau đó mình bắt đầu so sánh như các mình làm với bubble sort nhưng thay vì mình so sánh 2 bạn một lần thì mình sẽ so sánh một bạn với tất cả các bạn ở bên tay trái để mình đưa bạn đó vào đúng vị trí, và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao.
— — —
STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.
— — —
📧Email: hello@steamforvietnam.org
🌐Website: www.steamforvietnam.org
🌐Fanpage: STEAM for Vietnam
📺YouTube: http://bit.ly/S4V_YT
🌐Zalo: Zalo Official
📍Donation: https://www.steamforvietnam.org/donation