1. Selection Sort

Selection Sort là một thuật toán sắp xếp đơn giản và trực quan, hoạt động bằng cách liên tục tìm phần tử nhỏ nhất (hoặc lớn nhất, tùy cách sắp xếp) từ phần chưa sắp xếp của mảng và đặt nó vào vị trí đúng trong phần đã sắp xếp. Thuật toán này không yêu cầu bộ nhớ phụ và thực hiện sắp xếp tại chỗ (in-place).

2. Cách hoạt động của Selection Sort

1. Chọn phần tử đầu tiền là phần tử nhỏ nhất.

2. So sánh phần tử nhỏ nhất với phần tử thứ hai. Nếu phần tử thứ hai nhỏ hơn phần tử nhỏ nhất, gán phần tử thứ hai là phần tử nhỏ nhất.
   So sánh phần tử nhỏ nhất với phần tử thứ 3. Một lần nữa, nếu phần tử thứ 3 nhỏ hơn, gán phần tử nhỏ nhất là phần tử thứ 3 nếu không thì không làm gì cả. Quá trình tiếp tục cho đến phần tử cuối cùng.

3. Sau mỗi lần lặp, phần tử nhỏ nhất được đặt ở vị trí đầu tiên của mảng chưa được sắp xếp.

4. Đối với mỗi lần lặp lại bắt đầu từ nhưng phần tử chưa được sắp xếp. Lặp lại các bước từ bước 1 đến bước 3 cho đến khi mảng được sắp xếp.

3. Triển khai thuật toán

// Selection sort in Java
 
import java.util.Arrays;
 
class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;
 
    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;
 
      for (int i = step + 1; i < size; i++) {
 
        // To sort in descending order, change > to < in this line.
        // Select the minimum element in each loop.
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }
 
      // put min at the correct position
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }
 
  // driver code
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

4. Độ phức tạp thuật toán

Số lần thực hiện so sánh:

(n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2

gần bằng n²

Độ phức tạp thuật toán: O(n2)

Ngoài ra, ta có thể phân tích bằng cách quan sát có 2 vòng lặp lồng nhau nên độ phức tạp là: n*n=n2

4.1 Độ phức tạp về thời gian

• Trường hợp xấu nhất: Nếu chúng ta muốn sắp xếp mảng theo thứ tự tăng dần và mảng theo thứ tự giảm dần thì trường hợp xấu nhất xảy ra. O(n2)
• Trường hợp tốt nhất: Nó xảy ra khi mảng đã được sắp xếp O(n2)
• Trường hợp thường xảy ra: Khi các phần tử của mảng không theo thứ tự nhất định(không tăng dần hoặc giảm dần) O(n2)

Độ phức tạp thời gian của Selection Sort là như nhau trong mọi trường hợp. Ở mỗi bước, bạn cần tìm phần tử nhỏ nhất và đặt nó vào đúng vị trí. Phần tử nhỏ nhất không thể biết cho đến khi lặp đến cuối mảng.

4.2 Độ phức tạp không gian

Độ phức tạp không gian là: O(1) do min_idx sử dụng thêm 1 biến.