Selection sort - Sắp xếp chọn

1.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ản. Thuật toán sắp xếp này là một thuật toán dựa trên so sánh tại chỗ, trong đó danh sách được chia thành hai phần, 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ải.

Ban đầu, phần được sắp xếp trống và phần chưa sắp xếp là toàn bộ danh sách.

Phần tử nhỏ nhất được chọn từ mảng chưa sắp xếp và hoán đổi với phần tử ngoài cùng bên trái và phần tử đó trở thành một phần của mảng được sắp xếp. 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 thành phần có khóa nhỏ nhất trên mảng là A[k].
• Tráo đổi A[0] với A[k], vậy thì lúc này ta sẽ nhận được A[0] là phần tử có khóa nhỏ nhất.
• Giả sử đến bước thứ i ta đã có A[0].key <= A[1].key <= … <= A[i-1].key. Bây giờ ta cần tìm thành phần có khóa nhỏ nhất trong các phần tử từ A[i] đến A[n-1].
• Giả sử thành phần đó là A[k] sao cho i <= k <= n-1. Ta lại tráo đổi A[i] với A[k], ta có A[0].key <= A[1].key <= … <= A[i-1].key <= A[i].key.
• Lặp lại cho tới i = n-1, ta có mảng A được sắp xếp.

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. Ý tưởng và mô tả thuật toán

Giải thuật Selection Sort

• Bước 1: Chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[0] đến a[n-1] và hoán vị nó với phần tử a[0].
• Bước 2: Chọn phần tử có khóa nhỏ nhất trong n–1 phần tử từ a[1] đến a[n-1] và hoán vị nó với a[1].
• 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[i] đến a[n-1] và hoán vị nó với a[i].
• Sau n–1 bước thì mảng đã được sắp xếp.

Phương pháp chọn khóa 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[i] (lowkey = a[i]key) 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[j] với j từ i+1 đến n-1, nếu khóa của a[j] nhỏ hơn khóa nhỏ nhất (a[j].key < lowkey) thì đặt lại khóa nhỏ nhất là là khóa của a[j] (lowkey = a[j].key). Và phần tử có khóa nhỏ nhất là j (lowkey = j).
• Bước 3: Khi đã xét hết các phần tử a[j] với j > n-1 thì phần tử có khóa nhỏ nhất là a[lowindex] ```java arr [] = 64 25 12 22 11

// Tìm phần tử nhỏ nhất trong arr [0 … 4] và đặt nó ở đầu 11 25 12 22 64

// Tìm phần tử nhỏ nhất trong arr [1 … 4] và đặt nó ở đầu arr [1 … 4] 11 12 25 22 64

// Tìm phần tử nhỏ nhất trong arr [2 … 4] và đặt nó ở đầu arr [2 … 4] 11 12 22 25 64

// Tìm phần tử nhỏ nhất trong arr [3 … 4] và đặt nó ở đầu arr [3 … 4] 11 12 22 25 64

### 3. Code demo
Từ ý tưởng và mô tả của mục 2 – bây giờ chúng ta cùng nhau chuyển nó sang code và thực thi xem kết quả có như mong đợi không nhé.
```java
public class SelectionSort {
    void sort(int arr[]) {
        int n = arr.length;

        // Duyệt qua từng phần tử của mảng
        for (int i = 0; i < n - 1; i++) {

            // Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Hoán đổi phần tử nhỏ nhất và phần tử đầu tiên
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    // Xuất mảng
    void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        SelectionSort ob = new SelectionSort();
        int arr[] = {64, 25, 12, 22, 11};
        System.out.println("Mảng ban đầu:");
        ob.printArray(arr);
        ob.sort(arr);
        System.out.println("Mảng sau khi sắp xếp:");
        ob.printArray(arr);
    }
}

Trong thực tế, chúng ta không cần tạo một danh sách mới cho các phần tử được sắp xếp, những gì chúng ta làm là coi phần ngoài cùng bên trái của danh sách là phân đoạn được sắp xếp. Sau đó chúng ta tìm kiếm phần tử nhỏ nhất trong toàn bộ danh sách đã cho và hoán đổi nó với phần tử đầu tiên.

Selection sort là một trong những thuật toán đơn giản nhất, dễ học và cũng dễ vận dụng vào các dự án thực tế. Tuy nhiên đừng nghĩ rằng nó đơn giản và bạn thường, hãy tìm hiểu và tập luyện thật tốt các thức cơ bản này để kết hợp chúng lại vào các thuật toán phức tạp và đồ sộ hơn trong môi trường dự án lớn.

Sự am hiểu thuật toán càng nhiều sẽ tăng giá trị của bạn trong mắt nhà tuyển dụng – đặc biệt là các bạn lần đầu đi phỏng vấn xin việc. Hãy cân nhắc và chuẩn bị thật kỹ nhé.

Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!

Happy coding! 😎 👍🏻 🚀 🔥