[Học lại] Bài 2 - Sort Algorithm (Selection)

Theo wikipedia:

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số.

Mục đích của sắp xếp là để phục vụ cho các bài toán phức tạp hơn như truy xuất nhanh, thống kê ...
Vì có nhiều thuật toán nên mỗi bài mình sẽ tập trung vào 1 thuật toán duy nhất. Thử cài đặt từ đầu bằng Swift, visualize trên Xcode Playground, kèm theo phân tích độ phức tạp và các câu hỏi liên quan.

Link tham khảo:

https://www.geeksforgeeks.org/sorting-algorithms/

Hôm nay mình sẽ mở đầu bằng Selection Sort - Sắp xếp chọn:

Tìm phần tử nhỏ nhất trong mảng, đưa về đầu mảng, lặp lại với mảng không chứa phần tử đầu.

Ví dụ: [3, 2, 0, 1]
Bước 1: chạy qua từng phần tử để tìm phần tử nhỏ nhất, thấy 0
Bước 2: hoán đổi vị trí 0 và 3 -> [0, 2, 3, 1]
Bước 3: làm tương tự với mảng [2, 3, 1]
Kết thúc: [0, 1, 2, 3]

Cài đặt:

1. Không đệ quy
   Chúng ta cần 2 vòng lặp lồng nhau, 1 vòng lặp chạy ở ngoài để giới hạn mảng tìm min, vòng lặp ở trong để tìm min

func doSelectionSort(_ input: [Int]) -> [Int] {
    var result = input
    
    for i in 0..<result.count - 1 {
        
        var minIndex = i
        
        for j in i+1..<result.count {
            if result[j] < result[minIndex] {
                minIndex = j
            }
        }
        
        if minIndex != i {
            result.swapAt(i, minIndex)
        }
    }
    return result
}

2. Đệ quy
   Kết quả của Selection Sort chính là số nhỏ nhất ở đầu và Selection Sort mảng con không có số nhỏ nhất. sort(a) = min(a) + sort(a_without_min). thử cài đặt xem sao nhé:

func doSelectionSortRecursive(_ input: [Int]) -> [Int] {
    if input.count <= 1 {
        return input //already sorted
    }
    var subArray = input
    let min = dropMin(&subArray)
    return [min] + doSelectionSort(subArray)
}

//method hỗ trợ
func dropMin(_ input: inout [Int]) -> Int {
    var minIndex = 0
    for i in 1..<input.count {
        if input[i] < input[minIndex] {
            minIndex = i
        }
    }
    return input.remove(at: minIndex)
}

có thể tham khảo cách cài đặt đệ quy ở đây
https://www.geeksforgeeks.org/recursive-selection-sort/

Time Complexity: cả best và worst đều là O(n^2)

Tổng số lần đổi chỗ 2 phần tử khi cài đặt không đệ quy là n lần, ít hơn tất cả các phương pháp sắp xếp khác nên Selection cực kỳ hiệu quả nếu việc swap có chi phí (cost) lớn.

Selection Sort is an in-place algorithm having minimum number of swaps. It works on greedy approach and takes O(n) swaps to sort the array of n elements.

Hãy thử làm một số quiz liên quan đến selection sort để nhớ kỹ hơn.
https://www.geeksforgeeks.org/quiz-selectionsort-gq/

Visualize: clone source code ở đây:
https://github.com/haphanquang/sort-visualize-with-xcodeplayground