Đây là báo cáo của môn Phân Tích Thiết Kế Kế Hướng Đối Tượng

MÔN HỌC:

PHÂN TÍCH THIẾT KẾ VÀ GIẢI THUẬT

ĐỀ TÀI:

ĐÁNH GIÁ VÀ SO SÁNH ĐỘ PHỨC TẠP GIỮA 2 THUẬT TOÁN INSERTION SORT VÀ QUICKSORT

PHẦN A: NỀN TẢNG LÝ THUYẾT

1. Mô tả chức năng và yêu cầu

1.1. Khái quát về sắp xếp:

Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếm dữ liệu dễ dàng và nhanh chóng,thong thường trước khi thao tác thì dữ liệu trên mảng,trên tập tin đã có thứ tự.Do vậy thao tác sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ,quản lý dữ liệu

Có rất nhiều cách sắp xếp dữ liệu,nhưng ở đây ta chỉ quan tâm đến 2 thuật toán là sắp xếp bằng phương pháp chèn (Insertion Sort) và sắp xếp dựa trên sự phân hoạch (Quick Sort).Ta sẽ đi phân tích hai thuật toán sắp xếp này để so sánh và đánh giá độ phức tạp của chúng.

1.2. Mục tiêu của bài toán:

Phân tích,đánh giá và so sánh độ phức tạp(trên lý thuyết) và so sánh thời gian tính toán(trên thực nghiệm) của 2 giải thuật.

2. Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn (Insertion Sort)

2.1. Ý tưởng thuật toán:

Giả sử ta có dãy a1, a2, , an trong đó i phần tử đầu tiên a1, a2, , ai đã có thứ tự. Ý tưởng của thuật toán là tìm vị trị thích hợp và chèn phần tử ai+1 vào dãy đã có thứ tự trên để có được một dãy mới có thứ tự. Cứ thế, làm đến cuối dãy ta sẽ được một dãy có thứ tự.

Với dãy ban đầu a1, a2, , an ta có thể coi đoạn chỉ có một phần tử a1 là một đoạn đã có thứ tự, sau đó ta chèn phần tử a2 vào dãy a1 để có dãy a1a2 có thứ tự. Tiếp đó, ta lại chèn phần tử a3 vào dãy a1a2 để có dãy a1a2a3 có thứ tự. Cứ thế, đến cuối cùng ta chèn phần tử an vào dãy a1a2 an-1 ta sẽ được dãy a1a2 an có thứ tự