Sắp xếp Chọn - Selection Sort

Thuật toán sắp xếp chọn - Selection Sort 

Sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con trong một mảng nhất định.

1) Mảng con đã được sắp xếp.
2) Mảng con còn lại chưa được sắp xếp.

Trong mỗi lần lặp lại sắp xếp lựa chọn, phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ mảng con chưa được sắp xếp sẽ được chọn và chuyển đến mảng con đã sắp xếp.

Diễn giải một cách đơn giản hơn thì thuật toán sắp chọn diễn ra như sau:

• Tìm phần tử nhỏ nhất đưa vào vị trí 1
• Tìm phần tử nhỏ thứ 2 đưa vào vị trí 2
• Tìm phần tử nhỏ thứ 3 đưa vào vị trí 3
• .... 
• Tìm phần tử nhỏ thứ n đưa vào vị trí n trong mảng

Ví dụ sau giải thích các bước trên:

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 

Ví dụ sắp xếp chọn trong C++

Hàm xử lý sắp xếp chọn 

void selectionSort(int arr[], int n)

{

    int i, j, min_index;

    // One by one move boundary of unsorted subarray

    for (i = 0; i < n-1; i++)

    {

        // Find the minimum element in unsorted array

        min_index = i;

        for (j = i+1; j < n; j++)

        if (arr[j] < arr[min_index])

            min_index = j;

        // Swap the found minimum element with the first element

        swap(&arr[min_index], &arr[i]);

    }

}

Phân tích thuật toán

- Best Case: 0 đổi chỗ (n-1 như trong đoạn mã), /2 so sánh. 

- Worst Case: n-1 đổi chỗ và /2 so sánh 

- Average Case: O(n) đổi chỗ và /2 so sánh. 

Ưu điểm nổi bật của sắp xếp chọn là số phép đổi chỗ ít. Điều này có ý nghĩa nếu như việc đổi chỗ là tốn kém.