Giải thuật Quicksort

Trong phân tích thuật toán, để giải quyết một bài toán kích thước n, ta chia bài toán này thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải ban đầu. Trong bài giảng này sẽ trình bày một số bài toán chia để trị tiêu biểu như: MergeSort và QuickSort, nhân số nguyên lớn, xếp lịch thi đấu thể thao, bài toán con cân bằng. Mời các bạn cùng tham khảo.

7p namthangtinhlang_04 22-11-2015 141 14   Download

Quicksort- ý tưởng • Ðể sắp xếp dãy a1, a2, ..., an giải thuật QuickSort dựa trên việc phân hoạch dãy ban đầu thành hai ph ần : • Dãy con 1: Gồm các phần tử a1.. ai có giá trị không lớn hơn x • Dãy con 2: Gồm các phần tử ai .. an có giá trị không nhỏ hơn x • với x là giá trị của một phần tử tùy ý trong dãy ban đầu.

15p miendl91 02-12-2013 333 13   Download

Cài đặt các giải thuật sắp xếp theo các phương pháp: 1. Chọn trực tiếp. 2. Chèn trực tiếp. 3. Đổi chỗ trực tiếp. 4. Nổi bọt. 5. Quicksort. ....

6p xitin10 13-06-2011 308 73   Download

ĐỀ CƯƠNG ÔN TẬP THI TUYỂN SINH TRÌNH ĐỘ THẠC SĨ MÔN THI: KỸ THUẬT LẬP TRÌNH I. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1.1 Phân tích thuật toán, độ phức tạp thuật toán, phân lớp thuật toán. 1.2 Một số cấu trúc dữ liệu cơ bản Danh sách tuyến tính, danh sách móc nối. Ngăn xếp, hàng đợi (stack, queue). 1.3 Cây Cây nhị phân, cây nhị phân tìm kiếm Cây nhị phân cân bằng chiều cao (cây AVL) B-cây Chọn trực tiếp (Selection), Chèn (Insertion), Đổi chỗ liên tiếp (Bubble). Sắp nhanh (Quicksort), Vun đống (Heap sort), Trộn (Merge). So...

2p duongdinhcanh 05-05-2010 666 169   Download

Hiệu qủa thực hiện của giải thuật QuickSort phụ thuộc vào việc chọn giá trị mốc. Trường hợp tốt nhất xảy ra nếu mỗi lần phân hoạch đều chọn được phần tử median (phần tử lớn hơn (hay bằng) nửa số phần tử, và nhỏ hơn (hay bằng) nửa số phần tử còn lại) làm mốc, khi đó dãy được phân chia thành 2 phần bằng nhau và cần log2(n) bước phân hoạch thì sắp xếp xong.

15p vilocpro 16-11-2009 1639 210   Download