Khác biệt giữa Bubble Sort và Selection Sort

Hiểu sự khác biệt giữa Bubble Sort và Selection Sort.

Bubble Sort

• Thuật toán sắp xếp đơn giản.
• Duyệt danh sách, so sánh cặp phần tử liền kề để sắp xếp.
• Hoán đổi dựa trên phần tử liền kề.
• Hiệu quả hơn selection sort (theo bài gốc).
• Chậm hơn selection sort (theo bài gốc).
• Dùng trao đổi item (item exchanging).
• Lặp lại hoán đổi cho đến khi tất cả phần tử đúng thứ tự.

Thuật toán Bubble Sort

begin BubbleSort(list)
    for all elements of list
        if list[i] > list[i+1]
            swap(list[i], list[i+1])
        end if
    end for
    return list
end BubbleSort

Selection Sort

• Tìm min/max từ danh sách.
• Sắp xếp tăng/giảm dần.
• Chọn min/max từ mảng chưa sắp xếp, đặt vào vị trí tiếp theo của mảng đã sắp xếp.
• Coi là thuật toán không ổn định (unstable).
• Độ phức tạp thời gian mọi trường hợp O(n^2).
• Kém hiệu quả hơn insertion sort.
• Số so sánh nhiều hơn số hoán đổi.
• Vị trí mọi phần tử đã biết trước.
• Chỉ tìm phần tử cần chèn tại vị trí cụ thể.
• Hiệu quả hơn bubble sort.
• Nhanh hơn bubble sort.
• Dùng chọn item (item selection).

Thuật toán Selection Sort

Step 1 - Set MIN to location 0
Step 2 - Search the minimum element in the list
Step 3 - Swap with value at location MIN
Step 4 - Increment MIN to point to next element
Step 5 - Repeat until list is sorted