Cách làm bài so sánh n 1
Cuộc sống luôn chứa đựng quá nhiều vấn đề khiến chúng ta mệt mỏi. Dẹp hết đi hoặc sắp xếp lại mọi thứ, biết đâu bạn sẽ cảm thấy ổn hơn
Chủ đề "thuật toán sắp xếp" đã nảy ra trong đầu mình theo dòng suy nghĩ ấy. Tuy rằng không phải sở trường nhưng mình sẽ cố gắng để bài viết này có ích Cùng mình tìm hiểu nhé!1. Ừ là Khái niệmBài toán sắp xếp là bài toán giải quyết việc tổ chức dữ liệu theo một trật tự nhất định, thường là tăng dần hoặc giảm dần. Tóm tắt bài toán sắp xếp tăng dần: Input: Một mảng n phần tử A = (a1,a2,a3,...,ana_1, a_2, a_3, ..., a_n) Output: Một hoán vị của A là mảng A' = (a1′,a2′,a3′,...,an′a'_1, a'_2, a'_3, ..., a'_n), thỏa mãn điều kiện: a1′<=a2′<= a3′<=...<=an′a'_1 <= a'_2 <= a'_3 <= ... <= a'_n 2 phép toán cơ bản cho bài toán sắp xếp: 1. Phép toán đổi chỗ: Là phép toán đảo giá trị 2 biến
2. Phép toán so sánh: Trả về
2. Ba thuật toán sắp xếp cơ bản2.1. Sắp xếp chèn (Insertion Sort)Ý tưởng: Insertion Sort lấy ý tưởng từ việc Thuật toán:
Ví dụ: Đánh giá:
2.2. Sắp xếp lựa chọn (Selection Sort)Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị A' cần tìm. Thuật toán:
Ví dụ: Đánh giá:
2.3. Sắp xếp nổi bọt (Bubble Sort)Ý tưởng: Bubble Sort, như cái tên của nó, là thuật toán đẩy phần tử lớn nhất xuống cuối dãy, đồng thời những phần tử có giá trị nhỏ hơn sẽ dịch chuyển dần về đầu dãy. Tựa như sự nổi bọt vậy, những phần tử nhẹ hơn sẽ nổi lên trên và ngược lại, những phần tử lớn hơn sẽ chìm xuống dưới. Thuật toán: Duyệt mảng từ phần tử đầu tiên. Ta sẽ so sánh mỗi phần tử với phần tử liền trước nó, nếu chúng đứng sai vị trí, ta sẽ đổi chỗ chúng cho nhau. Quá trình này sẽ được dừng nếu gặp lần duyệt từ đầu dãy đến cuối dãy mà không phải thực hiện đổi chỗ bất kì 2 phần từ nào (tức là tất cả các phần tử đã được sắp xếp đúng vị trí).
Ví dụ: Đánh giá: Tuy đơn giản nhưng Bubble là thuật toán kém hiệu quả nhất trong 3 thuật toán ở mục này
So sánh 3 thuật toán 3. Merge SortSắp xếp trộn (merge sort) là một thuật toán sắp xếp loại so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị của John von Neumann:
Thuật toán:
Thuật toán trộn: Giả sử có hai dãy đã được sắp xếp L[1..n1n_1 ] và R[1..n2n_2]. Ta có thể trộn chúng lại thành một dãy mới M[1..n1+n2n_1 + n_2] được sắp xếp theo cách sau:
Khi đó, ta sẽ thu được dãy cần tìm.
Đánh giá: O(n*logn) Ví dụ: 4. Quick SortQuick Sort (QS) được phát triển bởi Hoare năm 1960. Theo thống kê tính toán, QS là thuật toán sắp xếp nhanh nhất hiện nay.
Tương tự như Merge sort, Quick sort là thuật toán sắp xếp được phát triển dựa trên kỹ thuật chia để trị:
Thuật toán:
Chọn phần tử chốt: Việc chọn phần tử chốt nắm vai trò quyết định đối với hiệu năng của thuật toán. Tốt nhất là chọn phần tử chốt là trung vị của danh sách. Tuy nhiên cách này rất khó nên ta có thể chọn phần tử chốt theo những cách sau:
Thuật toán Phân đoạn Partition: Mục đích của hàm
Ví dụ của QS: Đánh giá: Thời gian tính của Quick-Sort phụ thuộc vào việc phép phân đoạn là cân bằng (balanced) hay không cân bằng (unbalanced), và điều này lại phụ thuộc vào việc chọn phần tử chốt.
5. Heap SortĐịnh nghĩa Heap (đống) là cây nhị phân gần hoàn chỉnh có hai tính chất:
Biểu diễn đống dưới dạng mảng, ta có:
Phân loại: Có 2 loại
Phép toán khôi phục tính chất max-heap (Vun lại đống) Xét bài toán: Giả sử có nút i với giá trị bé hơn con của nó và cây con trái và cây con phải của i đều là max-heaps Thuật toán đệ quy:
Ví dụ: Thuật toán Heapsort Ý tưởng: Với A là một max-heap, nếu mỗi cây con có node cha từ 1 đến n/2 đều là max-heaps thì A là một mảng sắp xếp giảm dần.
Ví dụ: Trên đây là một số những thuật toán sắp xếp mình đã tìm hiểu, nếu có gì sai sót, bạn góp ý cho mình nhé. Hi vọng bài viết này có ích với bạn. Hẹn gặp lại bạn ở những bài viết tiếp theo. Tài liệu tham khảo: Cấu trúc dữ liệu và thuật toán - Nguyễn Đức Nghĩa, nhà xuất bản Bách Khoa Hà Nội, 2013 Mergesort Quicksort Heap sort |