Sắp xếp chọn – Selection Sort

Giới thiệu

Thuật toán sắp xếp chọn – Selection Sort là 1 trong các thuật toán sắp xếp kinh điển, cơ bản và dễ hiện thực, là thuật toán được tiếp cận sớm nhất khi bắt đầu học các giải thuật sắp xếp cơ bản. Trong 1 số trường hợp đơn giản, thuật toán này rất hữu hiệu, chẳng hạn với các mảng dữ liệu nhỏ không đòi hỏi phải tối ưu về thời gian.

Ý tưởng

Chọn phần tử nhỏ nhất đưa về vị trí đầu tiên của mảng hiện tại và không cần quan tâm đến nó nữa. Khi đó mảng chỉ còn lại n – 1 phần tử của mảng ban đầu, tiếp tục xét từ phần tử thứ 2 của mảng.

Lặp lại cho đến khi dãy hiện tại chỉ còn 1 phần tử.

Cài đặt

Bước 1: Chọn phần tử đầu tiên trong dãy là min.

Bước 2: So sánh min với phần tử thứ hai. Nếu phần tử thứ hai nhỏ hơn min, đánh dấu phần tử thứ hai là min.

Bước 3: Đổi chỗ a[i] và a[min].

Bước 4: Nếu i < n – 1 thì lặp lại bước 2 với i++ cho đến phần tử cuối cùng của dãy.

class SelectionSort 
{ 
    void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        // One by one move boundary of unsorted subarray 
        for (int i = 0; i < n-1; i++) 
        { 
            // Find the minimum element in unsorted array 
            int min = i; 
            for (int j = i+1; j < n; j++) 
                if (arr[j] < arr[min]) 
                    min = j; 
  
            // Swap the found minimum element with the first 
            // element 
            int temp = arr[min]; 
            arr[min] = arr[i]; 
            arr[i] = temp; 
        } 
    } 
  
    // Prints the array 
    void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
    // Driver code to test above 
    public static void main(String args[]) 
    { 
        SelectionSort ob = new SelectionSort(); 
        int arr[] = {64,25,12,22,11}; 
        ob.sort(arr); 
        System.out.println("Sorted array"); 
        ob.printArray(arr); 
    } 
}

Và kết quả là một mảng được sắp xếp hoàn chỉnh:

Sorted array: 
11 12 22 25 64Code language: PHP (php)

Đánh giá thuật toán sắp xếp chèn

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

• Trường hợp tốt: O(n²) (Mảng đã được sắp xếp)
• Trung bình: O(n²) 
• Trường hợp xấu: O(n²) (Mảng bị sắp xếp ngược)

Không gian bộ nhớ sử dụng: O(1)

Tại chỗ (In-place): Có

Cách sử dụng: 

Sắp xếp chọn được sử dụng khi:

• Dữ liệu đầu vào là 1 dãy nhỏ cần được sắp xếp
• Chi phí của việc đổi chỗ không đáng kể
• Kiểm tra toàn bộ phần tử trong dãy là cần thiết
• Chi phí ghi vào bộ nhớ quan trọng như trong bộ nhớ flash (số lần ghi/đổi chỗ là O(n) so với O(n²) của sắp xếp nổi bọt)