Sắp xếp theo thùng
1. Ý tưởng của thuật toán sắp xếp theo thùng
Thuật toán sắp xếp theo thùng (Bucket Sort):
Phân tán các phần tử trong mảng cần sắp xếp vào các “thùng” khác nhau, sau đó sắp xếp các phần tử trong từng thùng riêng biệt.
2. Các bước của thuật toán sắp xếp theo thùng
- Xác định số lượng thùng: Dựa trên phạm vi giá trị của mảng cần sắp xếp, chia mảng thành thùng, mỗi thùng tương ứng với một khoảng giá trị.
- Phân phối các phần tử: Duyệt qua mảng cần sắp xếp và phân phối từng phần tử vào thùng tương ứng dựa trên giá trị của nó.
- Sắp xếp từng thùng: Sắp xếp các phần tử trong từng thùng riêng biệt (có thể sử dụng các thuật toán sắp xếp như sắp xếp chèn, sắp xếp trộn, sắp xếp nhanh, v.v.).
- Kết hợp các phần tử trong các thùng: Kết hợp các phần tử đã được sắp xếp trong các thùng theo thứ tự khoảng giá trị để tạo thành một mảng đã sắp xếp hoàn chỉnh.
Chúng ta lấy ví dụ với mảng để minh họa toàn bộ quá trình sắp xếp theo thùng.
3. Cài đặt thuật toán sắp xếp theo thùng
4. Phân tích thuật toán sắp xếp theo thùng
- Độ phức tạp thời gian: . Khi số lượng phần tử đầu vào là , số lượng thùng là , số lượng phần tử trong mỗi thùng là , thời gian sắp xếp trong mỗi thùng là . Tổng thời gian sắp xếp các thùng là . Khi số lượng thùng tiến dần đến số lượng phần tử , là một hằng số nhỏ, do đó thời gian sắp xếp theo thùng gần tiến đến .
- Độ phức tạp không gian: . Vì thuật toán sắp xếp theo thùng sử dụng không gian phụ, nên độ phức tạp không gian của thuật toán là .
- Tính ổn định của thuật toán: Tính ổn định của thuật toán sắp xếp theo thùng phụ thuộc vào thuật toán sắp xếp được sử dụng trong từng thùng. Nếu thuật toán sắp xếp trong từng thùng là ổn định (ví dụ: sắp xếp chèn), và giữ nguyên thứ tự tương đối của các phần tử bằng nhau trong quá trình kết hợp các phần tử từ các thùng, thì thuật toán sắp xếp theo thùng là một thuật toán ổn định. Ngược lại, nếu không giữ nguyên thứ tự tương đối của các phần tử bằng nhau trong quá trình kết hợp các phần tử từ các thùng, thì thuật toán sắp xếp theo thùng là một thuật toán không ổn định.