- Sắp xếp nổi bọt (Bubble Sort).
- Sắp xếp nhanh (Quick Sort).
- Sắp xếp nổi bọt:
- 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].
- UVa 299 - Train Swapping.
- UVa 612 - DNA Sorting.
- UVa 10327 - Flip Sort.
- Sắp xếp nhanh:
- 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).
- gán i = d, j = c.
- Trong khi A[i] < k thì tăng i 1 đơn vị (phần tử trước nhỏ hơn phần tử sau).
- 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).
- 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ị.
- Nếu i > j thì thoát vòng lặp. Ngược lại quay về bước 3.
- Nếu i < c thì sắp xếp tiếp đoạn [i; h].
- Nếu d > j thì sắp xếp tiếp đoạn [d, j].
Độ 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:
Đá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:
Độ 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:
Độ 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:
Tham khảo thêm:
- Sắp xếp nổi bọt: http://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_n%E1%BB%95i_b%E1%BB%8Dt.
- Sắp xếp nhanh: http://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_nhanh.
- Hàm qsort (sắp xếp nhanh) trong C/C++ (Lưu ý: phải hiểu được cách sử dụng con trỏ trong C/C++ trước khi sử dụng): http://www.cplusplus.com/reference/cstdlib/qsort/.
Không có nhận xét nào:
Đăng nhận xét