[Thuật toán sắp xếp CHỌN (Selection Sort)]

Nội Dung:
   1. Thuật toán hoạt động như thế nào.
   2. Cài đặt thuật toán.
   3. Bình luận.

#1. Thuật toán hoạt động như thế nào?

    Sắp xếp chọn (selection sort) là một trong số những thuật toán sắp xếp kinh điển và cách thức hoạt động của thuật toán này khá đơn giản. Các bạn để ý cái tên của nó "sắp xếp CHỌN". Câu hỏi là chọn cái gì? Nếu trả lời được câu hỏi này các bạn sẽ dễ dàng nắm được thuật toán này.

    Để dễ hình dung thì trước tiên các bạn có thể coi một đoạn animation mô tả thuật toán này như sau:

Màu xanh lá: là biến chạy để tìm phần tử nhỏ hơn phần tử đang xét trên tập chưa được sắp xếp.
Màu đỏ: là vị trí của phần tử nhỏ hơn phần tử đang xét được cập nhật khi xanh lá chạy

Màu cam: là các phần tử đã được sắp xếp.

     Như vậy chúng ta thấy rằng thuật toán này chia tập dữ liệu thành hai phần. Một phần là các phần tử đã được sắp xếp, một phần là các phần tử chưa được sắp xếp.

     Sẽ có một phần tử đang được xét (phần tử màu cam cuối cùng). Màu đỏ sẽ đánh dấu VỊ TRÍ của phần tử nhỏ nhất trên tập chưa được sắp xếp. Màu xanh là biến chạy dùng để duyệt qua tập chưa sắp xếp và tìm phần tử nhỏ nhất để so sánh với phần tử ở vị trí màu đỏ.

     Khi màu xanh chạy hết một lần trên tập các phần tử chưa sắp xếp chúng ta sẽ có được VỊ TRÍ của phần tử nhỏ nhất trên tập đó.

     Ta thực hiện đồi chỗ phần tử ở vị trí đó cho phần tử đang xét ban đầu (nếu tìm thấy một phần tử nhỏ hơn phần tử đang xét ban đầu)

     Nói một cách đơn giản, ban đầu ta coi phần tử đầu tiên là nhỏ nhất (nhưng chưa chắc nó nhỏ nhất, vậy ta phải tìm xem trên tập chưa xét có phần tử nào nhỏ hơn nó không). Vấn đề là ta có thể tìm thấy nhiều thằng nhỏ hơn nó. Câu hỏi lúc này  tìm được thằng nhỏ nhất trong số những thằng nhỏ hơn.

"Đây chính là CÂU TRẢ LỜI cho câu hỏi "CHỌN CÁI GÌ?". Đó chính là chọn thằng NHỎ NHẤT TRONG SỐ NHỮNG THẰNG NHỎ HƠN."

#2. Cài đặt thuật toán.

Cài đặt bằng C++

1. #include<iostream>  
2. using namespace std;  
3.   
4. int main(){  
5.     int data[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 44, 46, 38, 47, 50, 58};  
6.     int size = sizeof(data) / sizeof(int);  
7.     for(int i = 0; i < size; i++) {  
8.         int index = i;  
9.         for(int j = i+1; j < size; j++){  
10.             if(data[j] < data[index]){  
11.                 index = j;  
12.             }  
13.         }  
14.         swap(data[index], data[i]);  
15.     }  
16.     for(int k = 0; k < size; k++)  
17.         cout << data[k] << " ";  
18.     return 0;  
19. }  

Cài đặt bằng Java

1. public class SelectionSort {  
2.     public static void main(String[] args) {  
3.         int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 44, 46, 38, 47, 50, 58};  
4.         for (int i = 0; i < data.length-1; i++){  
5.             int index = i;  
6.             for (int j = i + 1; j < data.length; j++){  
7.                 if (data[j] < data[index]){  
8.                     index = j;  
9.                 }  
10.             }  
11.             //swap  
12.             int temp = data[i];  
13.             data[i] = data[index];  
14.             data[index] = temp;  
15.         }  
16.         for (int i = 0; i < data.length; i++){  
17.             System.out.print(data[i] + " ");  
18.         }  
19.     }  
20. }  

Cài đặt bằng Python

1. def selection_sort():  
2.     data = [3, 44, 38, 5, 47, 15, 36, 26, 27, 44, 46, 38, 47, 50, 58]  
3.     for i in range(0, len(data) - 1):  
4.         index = i  
5.         for j in range(i + 1, len(data)):  
6.             if data[j] < data[index]:  
7.                 index = j  
8.         data[i], data[index] = data[index], data[i]  
9.     for i in range(0, len(data)):  
10.         print(data[i])  
11. selection_sort()  

     Ok! Cùng mình đọc qua code một lượt để xem việc triển khai thuật toán như thế nào nhé. Ở đây mình triển khai bằng C++, Java, Python để bạn nào quen với ngôn ngữ nào có thể dễ dàng hiểu được 

     Chúng ta có:

     - Input: là một mảng các phần tử chưa được sắp xếp (ở đây mình đặt tên là data)

     - Output: là một mảng các phần tử sau khi được sắp xếp theo chiều tăng dần.

[3, 5, 15, 26, 27, 36, 38, 38, 44, 44, 46, 47, 47, 50, 58] 

     Ở đây chúng ta sử dụng hai vòng lặp for. Mục đích thì như mình nói ban đầu là chia tập dữ liệu ra làm hai. Vòng for đầu tiên sẽ lặp từ i = 0 -> i = sizeof(data) - 1. Tại sao? Nguyên nhân là vòng for bên trong sẽ chạy từ j = i + 1 -> sizeof(data) vậy nên nếu bạn cho vòng for ngoài chạy đến sizeof(data) thì trong một số trường hợp sẽ bị lỗi tràn mảng do j = i+1 nếu bạn không khai báo mảng đủ rộng. Hai nữa biến j không cần chạy đến phần tử cuối cùng vì đó hiển nhiên là phần tử lớn nhất (hoặc nhỏ nhất nếu sắp xếp giảm dần)

     Ok! Xong hai cái for, ở đây các bạn thấy biến index. Nó để làm gì? Nó chính là dùng để đánh dấu vị trị của phần tử nhỏ hơn phần tử đang xét mà mình đã nói ở trên, cũng chính là mấu chốt cho thuật toán này.

     Tiếp theo là câu lệnh if dùng để kiểm tra và cập nhật giá trị cho biến index với mục đích là sau khi lặp hết tập chưa sắp xếp thì sẽ có được index của phần tử nhỏ nhất trong những phần tử nhỏ hơn phần tử đang xét. (Nếu muốn sắp xếp giảm dần bạn chỉ cần đổi thành data[j] > data[index])

    Sau đó là đoạn code dùng để đổi chỗ cho phần tử đang xét và phần tử có vị trí index tìm được sau khi chạy xong vòng for bên trong.

     Cuối cùng ta in ra kết kết quả sau khi sắp xếp. Cũng khá là dễ hiểu nhỉ!

#3. Bình luận.

   Như mình đã trình bày lúc đầu, sắp xếp chọn là một trong số những thuật toán sắp xếp kinh điển, nó không quá khó, dễ cài đặt nhưng lại là nền tảng để các bạn tiếp cận những thuật toán khác.

    Bây giờ chúng ta bàn chút về độ phức tạp của thuật toán này. (Cái này mình sẽ nói rõ hơn khi compare sắp xếp chọn với những thuật toán khác). Ở đây tạm thời chỉ đưa ra để các bạn hình dung được.

     + Độ phức tạp thời gian:
           - Trường hợp tốt nhất: Ω(n^2)
           - Trường hợp xấu nhất: O(n^2)
     + Độ phức tạp không gian: O(1)