Selection Sort - Deft Blog

Mục lục

1 Implementation
2 Minh hoạ:

Selection sort là thuật toán sắp xếp bằng cách lập lại nhiều lần tìm kiếm phần tử lớn nhất hoặc nhỏ nhất từ mảng chưa được sắp xếp và đẩy nó vào mảng đã được sắp xếp.

Thuật toán này rất đơn giản, ngày xưa mình học vòng for là mình đã tự nghĩ ra thuật toán này rồi chứ không hề biết nó là một thuật toán đã có từ trước, mình véo von thuật toán này như sau: Cô giáo thảo cần xếp các em học sinh nhỏ thành một hàng thẳng, và cô mong muốn các em học sinh trong lớp sắp xếp sao cho từ thấp đến bé, mà khổ nỗi cô không biết chính xác chiều cao của từng em, chỉ biết là có tất cả 40 em trong lớp, thế là với mỗi vị trí từ 0 – 40 cô phải dò từng em một trong số các em chưa được sắp vào hàng
để tìm ra học sinh thích hợp =))).

Các bước chạy của thuật toán cho trường hợp sắp xếp tăng dần:
– Giả định ta có mảng arr với size = n chưa được sắp xếp.
– Biến i: biến chỉ định phần tử cuối cùng đã được sắp xếp trong mảng arr.
– Biến j: loop trên mảng con chưa được sắp xếp và tìm ra phần tử nhỏ nhất trong mảng.

Bước 1: Loop i từ 0 đến n – 2, min_index = i;
Bước 2: Với mỗi giá trị i: Loop j từ i + 1 đến n – 1:
- Nếu arr[j] index_min = j
- Nếu arr[j] > arr[index_min] => bỏ qua
Bước 3: Hoán đổi arr[i] với arr[index_min]
Bước 4: Lặp lại Bước 1, 2, 3 cho đến i = n – 2

Implementation

/*
 * The selection sort algorithm sorts an array by repeatedly finding the minimum
 * element(considering ascending order) from an unsorted part and putting it at the beginning
 * O(n^2)
 */
public class SelectionSort
{
    public static<T extends Comparable<T>> void sort(T[] arr, int n)
    {
        for (int i = 0; i < n - 1; i++)
        {
            int index_min = i;
            for (int j = i + 1; j < n; j++)
            {
                /*
                 * Use codition arr[j] with a[index_min]
                 * Sort by ASC => Compare "<"
                 * Sort by DESC => Compare ">"
                 */
                if (arr[j].compareTo(arr[index_min]) < 0)
                {
                    index_min = j;
                }
            }
            T tmp = arr[index_min];
            arr[index_min] = arr[i];
            arr[i] = tmp;
        }
    }
}

Ta thấy trong moi dữ liệu thì selection sort vẫn loop 2 vòng for nên độ phức tạp của nó là: θ(n²)

Minh hoạ:

arr[] = {3, 1, 6, 8, 4}, n = 5

i = 0; loop j: 0 – 4 => min_index = 1
swap arr[i] và arr[min_index] => arr[] = {1, 3, 6, 8, 4}

i = 1; loop j: 1 – 4 => min_index = 1
swap arr[i] và arr[min_index] => arr[] = {1, 3, 6, 8, 4}

i = 2; loop j: 2 – 4 => min_index = 4
swap arr[i] và arr[min_index] => arr[] = {1, 3, 4, 8, 6}

i = 3; loop j: 3 – 4 => min_index = 4
swap arr[i] và arr[min_index] => arr[] = {1, 3, 4, 8, 6}

link source code: Selection Sort