Thứ Năm, 27 tháng 6, 2013

Sắp xếp

Về vấn đề này, ta chỉ cần nắm 2 cách sắp xếp là:
  • Sắp xếp nổi bọt (Bubble Sort).
  • Sắp xếp nhanh (Quick Sort).
Trong đây đề cập đến việc sắp xếp tăng một mảng số nguyên.
  1. Sắp xếp nổi bọt:
  2. Độ phức tạp: O(n.n).
    Đánh giá: Đây là phương pháp sắp xếp đơn giản nhất. Nhưng với bài toán có dữ liệu lớn (n = 50000 chẳng hạn), phương pháp này không khả thi.
    Phân tích thuật toán:
    • Với hai phần tử a[i] và a[i + 1], nếu a[i] > a[i + 1] thì ta đổi chỗ hai phần tử này.
    • Với n phần tử, gọi k đi từ n về 2, i đi từ 1 tới k, nếu a[i] > a[i + 1] thì ta đổi chỗ. Sau mỗi vòng lặp của i, phần tử a[k] là phần tử lớn nhất trong đoạn [1, k].
    Áp dụng:
    • UVa 299 -  Train Swapping.
    • UVa 612 - DNA Sorting.
    • UVa 10327 - Flip Sort.
  3. Sắp xếp nhanh:
  4. Độ phức tạp trung bình: O(n log n).
    Độ phức tạp cao nhất: O(n.n).
    Đánh giá: Trong các điều kiện thích hợp, đây là phương pháp sắp xếp nhanh nhất trong các thuật toán sắp xếp thông dụng. Ngoài ra, với ngôn ngữ C/C++, ta có thể rút gọn hàm sắp xếp, giúp tiết kiệm thời gian làm bài cũng như tốc độ xử lý của chương trình.
    Phân tích thuật toán:
    1. Gọi d và c là hai biến lưu địa chỉ đầu và cuối của đoạn cần sắp xếp, k là giá trị của phần tử A[(d + c) / 2] (phần tử giữa đoạn).
    2. gán i = d, j = c.
    3. Trong khi A[i] < k thì tăng i 1 đơn vị (phần tử trước nhỏ hơn phần tử sau).
    4. Trong khi A[j] > k thì giảm j 1 đơn vị (phần tử sau lớn hơn phần tử trước).
    5. Nếu i ≤ j (gặp hai phần tử A[i] > a[j]) thì tiến hành đổi chỗ A[i], A[j], sau đó tăng i 1 đơn vị, giảm j 1 đơn vị.
    6. Nếu i > j thì thoát vòng lặp. Ngược lại quay về bước 3.
    7. Nếu i < c thì sắp xếp tiếp đoạn [i; h].
    8. Nếu d > j thì sắp xếp tiếp đoạn [d, j].
Áp dụng thường: Tìm kiếm nhị phân, thuật giải tham lam (nhằm ưu tiên chọn cái tốt nhất trước), bài toán sắp lịch, tìm đa giác lồi (thuật toán tìm bao lồi Graham), ...

Tham khảo thêm:

Không có nhận xét nào:

Đăng nhận xét