- SẮP XẾP THỨ TỰ.
- Bài toán sắp xếp thứ tự.
- Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử..
- Sắp xếp dãy số a 1 , a 2.
- ,a N là thực hiện việc bố trí lại các phần tử sao cho hình thành được dãy mới a k1 , a k2.
- Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh.
- Giải thuật.
- Ta thấy rằng, nếu mảng có thứ tự, phần tử a i luôn là min(a i , a i+1.
- Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành.
- sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2.
- đến khi dãy hiện hành chỉ còn 1 phần tử.
- Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
- Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N].
- //N-1 phần tử đã nằm đúng vị trí..
- chỉ số phần tử nhỏ nhất trong dãy hiện hành for (int i=0.
- ghi nhận vị trí phần tử hiện nhỏ nhất.
- Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành.
- ,a n trong đó i phần tử đầu tiên a 1 , a 2.
- Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực tiếp là tìm cách chèn phần tử a i vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a 1 , a 2.
- Vị trí này chính là vị trí giữa hai phần tử a k-1 và a k thỏa a k-1 ? a i <.
- ,a n , ta có thể xem như đã có đoạn gồm một phần tử a 1.
- Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].
- int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử..
- kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới.
- dời các phần tử sẽ đứng sau x.
- Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng.
- Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
- Nếu a[j]<a[j-1]: a[j]?a[j-1];//xét cặp phần tử kế cận.
- Cài đặt thuật toán sắp xếp theo kiểu nổi bọt thành hàm BubbleSort:.
- Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm..
- Ðể sắp xếp dãy a 1 , a 2.
- Ðây chính là hướng tiếp cận của thuật toán sắp xếp theo phương pháp trộn..
- Nghĩa là dãy ban đầu đã được sắp xếp..
- Việc phân hoạch thành các dãy con đơn giản chỉ là tách dãy gồm n phần tử thành n dãy con.
- a n thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử:.
- Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a..
- Giải thuật Sắp xếp cây.
- Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1.
- Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp..
- Trong đó một phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i+1, do đó phần tử ở mức 0 (nút gốc của cây) luôn là phần tử lớn nhất của dãy.
- Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớn nhất về đúng vị trí), thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác được bảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả so sánh ở bước hiện tại.
- Có thể nhận thấy toàn bộ nhánh trái của gốc 8 cũ được bảo toàn, do vậy bước kế tiếp để chọn được phần tử lớn nhất hiện hành là 6, chỉ cần làm thêm một phép so sánh 1 với 6..
- Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là.
- khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp.
- Trên đây là ý tưởng của giải thuật sắp xếp cây..
- Tuy nhiên, để cài đặt thuật toán này một cách hiệu quả, cần phải tổ chức một cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n ô nhớ thay vì 2n-1 như trong ví dụ .
- Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử a l , a 2.
- (a i ,a 2i+1 ) là các cặp phần tử liên đới.
- a r là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap..
- a n là một heap thì phần tử a 1 (đầu heap) luôn là phần tử lớn nhất trong heap..
- Giai đoạn 2: Sắp xếp dãy số dựa trên heap:.
- o Bước 1: Ðưa phần tử nhỏ nhất về vị trí đúng ở cuối dãy:.
- o Bước 2: Loại bỏ phần tử nhỏ nhất ra khỏi heap: r = r-1;.
- o Bước 3: Nếu r>1 (heap còn phần tử.
- a n , lần lượt thêm vào các phần tử a n/2 , a n/2-1.
- Giai đoạn 2: Sắp xếp dãy số dựa trên heap.
- Ðể làm điều này, ta lần lượt xét quan hệ của một phần tử a i nào đó với các phần tử liên đới của nó trong dãy là a 2i và a 2i+1 , nếu vi phạm điều kiện quan hệ của heap, thì đổi chỗ a i với phần tử liên đới thích hợp của nó.
- nếu có đủ 2 phần tử liên đới.
- xác định phần tử liên đới lớn nhất j = j+1;.
- Ghép thêm phần tử a n/2 vào bên trái heap hiện hành và hiệu chỉnh lại dãy a n/2 , a n/2+1.
- a[l] là phần tử ghép thêm while (l >.
- r là vị trí đúng cho phần tử nhỏ nhất while(r >.
- Dãy con 1: Gồm các phần tử a 1.
- a i có giá trị không lớn hơn x Dãy con 2: Gồm các phần tử a i.
- a n 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.
- trong đó dãy con thứ 2 đã có thứ tự, nếu các dãy con 1 và 3 chỉ có 1 phần tử thì chúng cũng đã có thứ tự, khi đó dãy ban đầu đã được sắp.
- Ngược lại, nếu các dãy con 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các dãy con 1, 3 được sắp.
- Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, l ? k ? r:.
- Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ.
- Về nguyên tắc, có thể chọn giá trị mốc x là một phần tử tùy ý trong dãy, nhưng để đơn giản, dễ diễn đạt giải thuật, phần tử có vị trí giữa thường được chọn, khi đó k = (l +r)/ 2?.
- Số lần phân hoạch sẽ ít nhất nếu ta chon được x là phần tử median của dãy.
- Tuy nhiên do chi phí xác định phần tử median quá cao nên trong thực tế người ta không chọn phần tử này mà chọn phần tử nằm chính giữa dãy làm mốc với hy vọng nó có thể gần với giá trị median.
- Giải thuật phân hoạch dãy sắp xếp dãy a l , a l+1.
- Có thể phát biểu giải thuật sắp xếp QuickSort một cách đệ qui như sau.
- Dãy con 1 : a l.
- Dãy con 2 : a j+1.
- a i-1 = x - Dãy con 1 : a i.
- dãy con 1 có nhiều hơn 1 phần tử Phân hoạch dãy a l.
- dãy con 3 có nhiều hơn 1 phần tử Phân hoạch dãy a i.
- chọn phần tử giữa làm giá trị mốc i =l.
- 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 log 2 (n) lần phân hoạch thì sắp xếp xong.
- Nhưng nếu mỗi lần phân hoạch lại chọn nhằm phần tử có giá trị cực đại (hay cực tiểu) là mốc, dãy sẽ bị phân chia thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại gồm (n-1) phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong..
- Khác với sắp xếp dãy trên bộ nhớ có số lượng phần tử nhỏ và truy xuất nhanh, tập tin có thể có số lượng phần tử rất lớn và thời gian truy xuất chậm.
- Run là một dãy liên tiếp các phần tử được sắp thứ tự..
- Ví dụ là một run gồm có 5 phần tử.
- Chiều dài run chính là số phần tử trong Run.
- Như vậy, mỗi phần tử của dãy có thể xem như là 1 run có chiều dài là1.
- Hay nói khác đi, mỗi phần tử của dãy chính là một run có chiều dài bằng 1..
- Hiển nhiên, run được tạo từ hai run ban đầu là một dãy các phần tử đã được sắp thứ tự..
- Giải thuật:.
- Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau:.
- Giả sử các phần tử trên f0 là:.
- Thực hiện phân bố m=1 phần tử lần lượt từ f0 vào f1 và f2:.
- -Phân bố m=2 phần tử lần lượt từ f0 vào f1 và f2:.
- Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau:.
- Phân bố m=8 phần tử lần lượt từ f0 vào f1 và f2:.
- a=fopen("d:\ctdl\sortfile\bang.int","rb");.
- a=fopen("d:\ctdl\sortfile\bang.int","wb");.
- b=fopen("d:\ctdl\sortfile\bang1.int","rb");.
- Cài đặt các thuật toán sắp xếp đã trình bày