#### Ôn lý thuyết
##### 1* Trình bày mối quan hệ giữa cấu trúc dữ liệu và giải thuật, cho ví dụ minh hoạ.
Cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết.
+ Cấu trúc dữ liệu là cách tổ chức, lưu trữ dữ liệu trong máy tính điện tử một cách có thứ tự, có hệ thống nhằm sử dụng dữ liệu một cách hiệu quả.
+ Giải thuật là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số bước hữu hạn thực hiện thao tác đó, ta thu được kết quả mong muốn.
+ Cấu trúc dữ liệu và giải thuật có mối liên hệ chặt chẽ với nhau, chúng luôn tồn tại song song, đi kèm nhau theo công thức: CTDL + GT = chương trình.
- Bản thân các phần tử của dữ liệu thường có mối quan hệ với nhau, ngoài ra nếu biết tổ chức chúng theo các cấu trúc dữ liệu thích hợp thì việc thực hiện các phép toán xử lý trên các dữ liệu sẽ càng thuận lợi hơn, đạt hiệu quả cao hơn. Với cấu trúc dữ liệu đã chọn, ta sẽ có giải thuật tương ứng. Cấu trúc dữ liệu thay đổi thì giải thuật cũng thay đổi theo. Để có một chương trình tốt, ta cần phải chọn được cấu trúc dữ liệu phù hợp và chọn được một giải thuật đúng đắn.
- Vd: Giả sử ta có 1 danh sách các trường đại học và cao đẳng trên cả nước mỗi trường có các thông tin sau: Tên trường, địa chỉ, sđt phòng đào tạo. Ta muốn viết một chương trình trên máy tính điện tử để khi cho biết “tên trường” máy sẽ hiện ra màn hình cho ta: “địa chỉ” và “số điện thoại phòng đào tạo” của trường đó.
+ Một cách đơn giản là cứ duyệt tuần tự các tên trường trong danh sách cho tới khi tìm thấy trên trường cần tìm thì sẽ đói chiếu ra “địa chỉ” và “số điện thoại phòng đào tạo” của trường đó. Cách tìm tuần tự này rõ ràng chỉ chấp nhận được khi danh sách ngắn còn danh sách dài thì rất mất thời gian.
+ Nếu ta biết tổ chức lại danh sách bằng cách sắp xếp theo thứ tự từ điển của tên trường, thì có thể áp dụng 1 giải thuật tìm kiếm khác tốt hơn, tương tự như ta vẫn thường làm khi tra từ điển. Cách tìm này nhanh hơn cách trên rất nhiều nhưng không thể áp dụng được với dữ liệu chưa được sắp xếp.
+ Nếu lại biết tổ chức thêm 1 bảng mục lục chỉ dẫn theo chữ cái đầu tiên của tên trường, thì khi tìm “địa chỉ” và “số điện thoại phòng đào tạo” của Hvktmm ta sẽ bỏ qua được các tên trường mà chữ cái đầu không phải là “H”.
Như vậy giữa cấu trúc dữ liệu và gt có mqh mật thiết. Có thể coi chúng như hình với bóng, không thể nói tới cái này mà không nhắc tới cái kia.

##### 2* Trình bày mối quan hệ giữa cấu trúc dữ liệu và các phép toán trên cấu trúc dữ liệu.
- Đối với các bài toán phi số, đi đôi với cấu trúc dữ liệu mới, cũng xuất hiện các phép toán mới tác động trên các cấu trúc ấy. Thông thường có các phép toán như: phép tạo lập hoặc hủy bỏ một cấu trúc, phép truy nhập vào từng phần tử của cấu trúc, phép bổ sung hoặc loại bỏ một phẩn tử trên cấu trúc,...
- Các phép toán đó sẽ có những tác dụng khác nhau đối với từng cấu trúc. Có phép toán hữu hiệu đối với cấu trúc này nhưng lại tỏ ra không hữu hiệu trên các cấu trúc khác.
- Vì vậy, khi chọn một cấu trúc dữ liệu, ta phải nghĩ ngay tới các phép toán tác động trên cấu trúc ấy, và ngược lại, nói tới phép toán thì lại phải chú ý tới phép toán đó tác động trên các trúc dữ liệu nào. Cho nên người ta thường quan niệm: nói tới cấu trúc dữ liệu là bao hàm luôn cả phép toán tác động đến cấu trúc ấy.

##### 3* Trình bày sự khác nhau giữ cấu trúc dữ liệu và cấu trúc lưu trữ, cho ví dụ minh hoạ.
Cấu trúc lưu trữ là cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ máy tính điện tử. Đó chính là cách cài đặt cấu trúc ấy trên máy tính điện tử và trên cơ sở cấu trúc lưu trữ này mà thực hiện các phép xử lý.
Ta cần phân biệt giữa cấu trúc dữ liệu và cấu trúc lưu trữ tương ứng. Có thể có nhiều cấu trúc lưu trữ khác nhau cho cùng một cấu trúc dữ liệu, cũng như có thể có những cấu trúc dữ liệu khác nhau mà được thể hiện trong bộ nhớ bởi cùng một kiểu cấu trúc lưu trữ.
- Ví dụ: cấu trúc lưu trữ kế tiếp (mảng) và cấu trúc lưu trữ móc nối đều có thể được dùng để cài đặt cấu trúc dữ liệu ngăn xếp (stack). Mặt khác, các cấu trúc dữ liệu như: danh sách, ngăn xếp và cây đều có thể cài đặt trên máy tính thông qua cấu trúc dữ liệu móc nối.
##### 4* Trình bày những đặc điểm về cấu trúc dữ liệu trong các ngôn ngữ lập trình bậc cao, có liên hệ với ngôn ngữ C.
Trong các ngôn ngữ lập trình bậc cao, các dữ liệu được phân nhánh thành các kiểu dữ liệu. kiểu dữ liệu nhận của một biến được xác định bởi một tập các giá trị mà biến đó có thể nhận và các phép toán có thể thực hiện trên các giá trị đó.
Mỗi ngôn ngữ lập trình cung cấp cho chúng ta một số kiểu dữ liệu cơ bản. Trong các ngôn ngữ lập trình khác nhau, các kiểu dữ liệu cơ bản có thể khác nhau . Các ngôn ngữ lập trình như C, pascal… có các kiểu dữ liệu cơ bản rất phong phú.
Các kiểu dữ liệu được tạo thành từ nhiều kiểu dữ liệu khác nhau được gọi là kiểu dữ liệu có cấu trúc. Các dữ liệu thuộc kiểu dữ liệu cấu trúc được gọi là cấu trúc dữ liệu.
Từ các kiểu cơ bản, bằng cách sử dụng các quy tắc, cú pháp để kiến tạo các kiểu dữ liệu, người lập trình có thể xây dựng nên kiểu dữ liệu mới, được gọi là các kiểu dữ liệu xác định bởi người sử dụng.
=> Như vậy: một cấu trúc dữ liệu phức hợp gồm nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu cơ sở hoặc là cấu trúc dữ liệu đã đk xây dựng. Các thành phần dữ liệu tạo nên một cấu trúc dữ liệu đk liên kết với nhau theo một cách nào đó.
Trong ngôn ngữ lập trình C phương pháp để liên kết dữ liệu :
+) Liên kết dữ liệu cùng kiểu tạo thành mảng dữ liệu.
+) Liên kết các dữ liệu thành mảng cấu trúc trong C.
+) Sử dụng con trỏ để liên kết dữ liệu.

##### 5* Trình bày nguyên tắc thiết kế Top-Down, cho ví dụ minh hoạ.
- Ngày nay công nghệ thông tin đã và đang đóng góp trong mọi lĩnh vực của cuộc sống, bởi vậy các bài toán giải được trên máy tính điện tử rất đa dạng và phức tạp. Các giải thuật và chương trình được dùng để giải chúng cũng có quy mô ngày càng lớn, nên càng khó khi ta muốn tìm hiểu và thiết kế chúng.
- Tuy nhiên ta cũng thấy rằng mọi việc sẽ đơn giản hơn nếu như có thể phân chia bài toán lớn thành các bài toán nhỏ hơn. Điều đó cũng có nghĩa là nếu coi bài toán của ta như một mô đun chính thì cần chia nó thành các mô đun con, và dĩ nhiên, với tinh thần như thế, đến lượt nó, mỗi mô đun con này lại tiếp tục được chia tiếp cho tới những mô đun ứng với các phần việc cơ bản mà ta đã biết cách giải quyết. Như vậy việc tổ chức lời giải của các bài toán sẽ được thể hiện theo một cấu trúc nhân cấp có dạng như sau :
Cách giải quyết bài toán theo hình như vậy được gọi là chiến thuật “ chia để trị” . Để thể hiện chiến thuật đó, người ta dùng cách thiết kế “ đinh xuống” (top-down design). Đó là cách phân tích tổng quát toàn bộ vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra để đề cập đến những công việc chủ yếu trước, rồi sau đó mới đi dần vào giải quyết các phần việc cụ thể một cách chi tiết hơn, cũng vì vậy mà người ta còn gọi cách thiết kế này là cách thiết kế từ khái quát đến chi tiết.

- Ví dụ: (Ta nhận được từ Chủ tịch Hội đồng xét học bổng của trường một yêu cầu là:) Dùng máy tính điện tử để quản lý và bảo trì các hồ sơ học bổng của các sinh viên ở diện được tài trợ, đồng thời thường kì phải lập các báo cáo tổng kết để đệ trình lên Bộ.
- Như vậy trước hết ta phải hình dung được cụ thể hơn đầu vào và đầu ra của bài toán.
- Có thể coi như ta đã có một tập các hồ sơ (tệp - file) bao gồm các bản ghi (records) về các thông tin liên quan đến học bổng của sinh viên (chẳng hạn: số hiệu sinh viên, điểm trung bình (theo học kì), điểm đạo đức, khoản tiền trợ cấp). Và chương trình lập ra phải tạo điều kiện cho người sử dụng giải quyết được các yêu cầu sau:
+ Tìm lại và hiển thị được bản ghi của bất kỳ sinh viên nào tại thiết bị cuối của người dùng.
+ Cập nhật được bản ghi của một sinh viên cho trước bằng cách đổi điểm trung bình, điểm đạo đức, khoản tiền tài trợ, nếu cần.
+ In bản tổng kết chứa những thông tin hiện thời (đã được cập nhật mỗi khi có thay đổi) gồm số hiệu, điểm trung bình, điểm đạo đức, khoản tiền tài trợ.
- Xuất phát từ những nhận định trên, giải thuật xử lý sẽ phải giải quyết 3 nhiệm vụ chính như sau:
+ Những thông tin về sinh viên được học bổng lưu trữ trên đĩa phải được đọc vào bộ nhớ trong để có thể xử lý (đọc tệp)
+ Xử lý các thông tin này để tạo ra kết quả mong muốn (xử lý tệp)
+ Sao chép những thông tin đã được cập nhật vào tệp trên đĩa để lưu trữ cho việc xử lý sau này (ghi tệp)
Có thể hình dung, cách thiết kế này theo sơ đồ cấu trúc sau:
- Các nhiệm vụ ở mức ban đầu này thường tương đối phức tạp, cần phải chia thành các nhiệm vụ con. Chẳng hạn, nhiệm vụ "xử lý tệp" sẽ được phân thành ba, tương ứng với việc giải quyết ba yêu cầu chính đã được nếu ở trên.
+ Tìm lại bản ghi của một sinh viên cho trước
+ Cập nhật thông tin trong bản ghi sinh viên
+ In bảng tổng kết những thông tin về các sinh viên được học bổng
- Những nhiệm vụ con này cũng có thể chia thành các nhiệm vụ nhỏ hơn. Có thể hình dung theo sơ đồ cấu trúc sau:

- Cách thiết kế giải thuật theo kiểu top-down như trên giúp cho việc giải quyết bài toán được định hướng một cách rõ ràng, tránh sa đà ngay vào các phần việc phụ. Nó cũng là các nền tảng cho việc lập trình có cấu trúc.
- Thông thường, đối với các bài toán lớn, việc giải quyết nó phải do nhiều người cùng làm . Chính phương pháp mô đun hóa sẽ cho phép tách bài toán ra thành các phần độc lập, tạo điều kiện cho các nhóm giải quyết phần việc của mình mà không ảnh hưởng gì đến nhóm khác. Với chương trình được xây dựng trên cơ sở của các giải thuật được thiết kế theo cách này , thì việc tìm hiểu cũng như sửa chữa, chỉnh lý sẽ đơn giản hơn.
- Trong thực tế, việc phân tích bài toán thành các bài toán con như thế không phải là việc dễ dàng. Chính vì vậy mà có những bài toán, nhiệm vụ phân tích và thiết kế giải thuật giải bài toán còn mất nhiều thời gian và công sức hơn cả nhiệm vụ lập trình.

##### 6) Trình bày Phương pháp tinh chỉnh từng bước, cho ví dụ minh hoạ.
-Tinh chỉnh từng bước là phương pháp thiết kế giải thuật gắn liền với lập trình. Nó phản ánh tinh thần của quá trình mô đun hóa bài toán và thiết kế kiểu top-down.

- Ban đầu chương trình thể hiện giải thuật được trình bày bằng ngôn ngữ tự nhiên, phản ánh ý chính của của công việc cần làm. Từ các bước sau, những lời, những ý đó sẽ được chi tiết hóa dần dần tương ứng với những công việc nhỏ hơn. Ta gọi đó là các bước tinh chỉnh, sự tinh chỉnh này sẽ hướng về phía ngôn ngữ lập trình mà ta đã chọn. Càng ở các bước sau, các lời lẽ đặc tả công việc cần xử lý sẽ được thay thế dần bởi các câu lệnh hướng tới câu lệnh của ngôn ngữ lập trình. Muốn vậy, ở các giai đoạn trung gian người ta thường dùng pha tạp cả ngôn ngữ tự nhiên lẫn ngôn ngữ lập trình, mà người ta gọi là “ giả ngôn ngữ” hay “ giả mã”.

- Như vậy, quá trình thiết kế giải thuật và phát triển chương trình sẽ được thể hiện dần dần, từ dạng ngôn ngữ tự nhiên, qua giả ngôn ngữ, rồi đến ngôn ngữ lập trình, và đi từ mức "làm cái gì" đến mức "làm như thế nào", ngày càng sát với các chức năng ứng với các câu lệnh của ngôn ngữ lập trình đã chọn. Trong quá trình này dữ liệu cũng được “ tinh chế “ dần dần từ dạng cấu trúc dữ liệu đến dạng cấu trúc lưu trữ cụ thể trên máy.

Ví dụ

B1: trình bày giải thuật bằng ngôn ngữ tự nhiên:

Tính giai thừa qua đệ quy:

· Kiểm tra điều kiện cơ sở (nếu n = 0 thì giai thừa bằng 1)

· Gọi hàm đệ quy nếu ko đạt điều kiện cơ sở với n giảm đi 1

B2: Dùng cả ngôn ngữ tự nhiên và ngôn ngữ lập trình:

GiaiThua(int n)

{

If(n bằng 0) thì trả về 1

Else gọi lại hàm Giai Thừa với n -1đơn vị}

B3: Chỉ dùng ngôn ngữ lập trình:

GiaiThua(int n)

{

If (n==0) return 1;

Else return n*GiaiThua(n-1);

}

##### 7) Trình bày cách Phân tích thời gian thực hiện giải thuật. Định nghĩa O lớn.
Thời gian thực hiện một giải thuật phụ thuộc vào rất nhiều yếu tố. 1 yếu tố cần chú ý trước tiên đó là kích thước của dữ liệu đưa vào. Chẳng hạn thời gian sắp xếp 1 dãy số phải chịu ảnh hưởng của số lượng các số thuộc dãy số đó. Nếu gọi n là số lượng này thì thời gian thực hiện T của 1 giải thuật phải được biểu diễn như 1 hàm của n: T(n).
(80 từ - 6 dòng)

Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện, nhưng những yếu tố này không đồng đều với mọi loại máy trên đó cài đặt giải thuật, vì vậy không thể dựa vào chúng khi xác lập T(n). Điều đó cũng có nghĩa là T(n) không thể được biểu diễn thành đơn vị thời gian bằng giây, bằng phút.. được.
(82 từ - 7 dòng)

Tuy nhiên không phải vì thế mà không thể so sánh được các giải thuật về mặt tốc độ. Nếu thời gian thực hiện của 1 giải thuật là T1(n)=cn2 và thời gian thực hiện của 1 giải thuật khác là T2(n)=kn (với c và k là 1 hằng số nào đó) thì n khá lớn, thời gian thực hiện giải thuật T2 rõ ràng ít hơn so với giải thuật T1.
(72 từ - 6 dòng)

Và như vậy thì nếu nói thời gian thực hiện giải thuật T(n) tỉ lệ với n2 hay tỉ lệ với n cũng cho ta ý niệm về tốc độ thực hiện giải thuật đó khi n khá lớn (với n nhỏ thì việc xét T(n) không có ý nghĩa)
(50 từ - 4 dòng)

Định nghĩa O lớn: Giải sử f(n) và g((n) là hàm không âm của đối số nguyên không âm của n.Ta nói f(n) là O lớn của g(n) và viết là f(n)=O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho f(n)<=cg(n) với mọi n>=n0.Như vậy,f(n)=O(g(n)) có nghĩa là hàm f(n) bị chặn trên bởi hàm g(n) với một nhân tử hằng nào đó khi n đủ lớn.
(71 từ - 6 dòng)
##### 8) Trình bày cách Xác định độ phức tạp tính toán của giải thuật, với những nội dung: Qui tắc tổng, Phép toán tích cực, thời gian chạy của các câu lệnh lặp, cho ví dụ minh hoạ.
**Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan tới máy như vậy sẽ dẫn tới khái niệm về “cấp độ lớn của thời gian thực hiện giải thuật” hay còn gọi là “độ phức tạp tính toán của giải thuật”. **
(52 từ - 5 dòng)

Nếu thời gian thực hiện 1 giải thuật là T(n)=cn2 (c là hằng số) thì ta nói : độ phức tạp tính toán của giải thuật này có cấp là n2 và ta ký hiệu:

T(n) = O(n2) (ký hiệu chữ O lớn)
( 4 dòng )

Một cách tổng quát có thể định nghĩa: 1 hàm f(n) được xác định là O(g(n)). f(n) = O(g(n))và được gọi là có cấp g(n) nếu tồn tại các hằng số c và n0 sao cho: f(n)<=cg(n)(khi n>=n0 nghĩa là khi f(n) bị chặn trên bởi 1 hằng số nhân với g(n) với mọi giá trị của n từ một thời điểm nào đó).
(64 từ - 6 dòng )

**Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện của 1 đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 tiếp theo sẽ là: T1(n) + T2(n) = O(max(f(n),g(n)).**
(45 từ - 4 dòng )

VD: trong 1 chương trình có 3 bước thực hiện mà thời gian thực hiện từng bước lần lượt là O(n2), O(n3) và O(n log2n) thì thời gian thực hiện 2 bước đầu là O(max(n2,n3))=O(n3) thời gian thực hiện chương trình sẽ là: O(max(n3, n log2n))=O(n3).
(46 từ - 4 dòng)

**Phép toán tích cực (active operation ) là phép toán thuộc giải thuật mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác hay nói một cách khác là số lần thực hiện nó không kém gì các phép toán khác **

(49 từ - 4 dòng)

**Các câu lệnh lặp (Các câu lệnh lặp gồm: for, while, do-while) **
(2 dòng)

Để đánh giá thời gian thực hiện một câu lệnh lặp, trước hết ta cần đánh giá số tối đa các lần lặp, giả sử đó là L(n). Sau đó đánh giá thời gian chạy của mỗi lần lặp, chú ý rằng thời gian thực hiện thân của một lệnh lặp ở các lần lặp khác nhau có thể khác nhau, giả sử thời gian thực hiện thân lệnh lặp ở lần thứ i (i=1,2,..., L(n)) là Ti(n). Mỗi lần lặp, c lặphúng ta cần kiểm tra điều kiện, giả sử thời gian kiểm tra là T0(n). Như vậy thời gian chạy của lệnh lặp là:
(106 từ - 9 dòng)
(2 dòng)

Công đoạn khó nhất trong đánh giá thời gian chạy của một lệnh lặp là đánh giá số lần lặp. Trong nhiều lệnh lặp, đặc biệt là trong các lệnh lặp for, ta có thể thấy ngay số lần lặp tối đa là bao nhiêu. Nhưng cũng không ít các lệnh lặp, từ điều kiện lặp để suy ra số tối đa các lần lặp, ta cần phải tiến hành các suy diễn không đơn giản.Trường hợp hay gặp là: kiểm tra điều kiện lặp (thông thường là đánh giá một biểu thức) chỉ cần thời gian O(1), thời gian thực hiện các lần lặp là như nhau và giả sử ta đánh giá được là O(f(n)); khi đó, nếu đánh giá được số lần lặp là O(g(n)), thì thời gian chạy của lệnh lặp là O(g(n).f(n))
(137 từ - 12 dòng)

VD: giải sử có mảng A các số thực, cỡ n và ta cần tìm xem mảng có chứa số thực x không. Điều đó có thể thực hiện bởi giải thuật tìm kiếm tuần tự như sau:
(4 dòng)

1.i=0;
2.while(i<n&& x!=A[i])
3.i++;
(3 dòng)

lệnh gán (1) có thời gian chạy là O(1). Lệnh lặp (2)-(3) có số tối đa các lần lặp là n, đó là trường hợp x chỉ xuất hiện ở thành phần cuối cùng của mảng A[n-1] hoặc x không có trong mảng. Thân của lệnh lặp là lệnh (3) có thời gian chạy O(1). Do đó, lệnh lặp có thời gian chạy là O(n). Giải thuật gồm lệnh gán và lệnh lặp với thời gian là O(1) và O(n), nên thời gian chạy của nó là O(n).
(8 dòng)

##### 9** Trình bày ưu điểm, nhược điểm của ba phương pháp sắp xếp: sắp xếp nhanh (Quick - sort), sắp xếp kiểu vun đống (Heap - sort), sắp xếp kiểu hoà nhập (Merge - sort). Trình bày những nhận xét khi sử dụng các phương pháp sắp xếp.
Quicksort

Ưu điểm
Hiệu suất tốt nhất là : O(nLog2n)
Trung bình: O(nLog2n)
Xấu nhất: O(n^2)
Là thuật toán chạy nhanh nhất ở trường hợp trung bình, hiệu quả hơn với n khá lớn.
Không cần bộ nhớ phụ; dùng tốt cho danh sách liên kết.

Nhược điểm
Trường hợp xấu nhất chiếm hiệu xuất O(n^2)
Code khá phức tạp; không ổn định
Tốc độ thuật toán phụ thuộc vào cách chọn chốt.
Cần thêm không gian nhớ cho ngắn xếp
Khi n nhỏ thì tốn thời gian hơn với các sắp xếp khác.

Heapsort
ưu điểm
hiệu xuất cao: T(n) = O(nLog2n) trong mọi trường hợp.
nhược điểm
code phức tạp;
cần 1 nút nhớ phụ khi thực hiện đổi chỗ
khi dãy số đã sắp xếp có thứ tự thì giải thuật này không hiệu quả

Merge-sort
Ưu điểm
Hiệu suất cao; thời gian thực hiện: O(nLog2n)
Nhược điểm
đòi hỏi không gian bộ nhớ để lưu các dãy phụ
chi phí không gian khá lớn (đòi hỏi tới 2n phần tử nhớ, gấp đôi phương pháp thông thường) -> hạn chế này khó chấp nhận vì trong thực tế các dãy được sắp xếp thường có cấu trúc lớn hơn.

Nhận xét:
Khi sử dụng phương pháp sắp xếp: Cùng một mục đích sắp xếp như nhau mà có rất nhiều phương pháp và kỹ thuật giải quyết khác nhau. Cấu trúc dữ liệu được lựa chọn để hình dung đối tượng của sắp xếp đã ảnh hưởng rất sát tới giải thuật xử lý.
Các phương pháp sắp xếp đơn giản đã thể hiện 3 kỹ thuật cơ sở của sắp xếp, cấp độ lớn của thời gian thực hiện chung là O (n2 ) vì vậy chỉ nên sử dụng chúng khi n nhỏ, các giải thuật cải tiến như QS
HS đã đạt được hiệu quả cao nên đc sử dụng khi n lớn. MS cũng k kém hiệu lực về tgian thực hiện nhưng về không gian thì đòi hỏi của nó k thích nghi với sắp xếp trong . nếu bảng sắp xếp vốn có khuynh hướng hầu như đã đc sắp sẵn thì QS lại k nên dùng .
nhưng nếu ban đầu bảng có khuynh hướng ít nhiều có thứ tự ngược với thứ tự sắp xếp thì HS lại tỏ ra thuận lợi. Việc khẳng định 1 kỹ thuật sắp xếp nào vừa nói trên luôn tốt nhất với mọi kỹ thuật khác là điều k nên. Việc chọn 1 phương pháp thích hợp thường tùy thuộc vào từng yêu cầu , từng điều kiện cụ thể

PHẦN 2: GIẢI THUẬT
ảnh Đạo gửi (giống đề cương của Hải Anh) https://drive.google.com/drive/folders/1TDumOiNALTLo1_4xobX_mmfqO7j_hIdb
(tham khảo của Yến nha)
https://actvneduvn-my.sharepoint.com/:f:/g/personal/at180251_actvn_edu_vn/EmP-KO6lKGJNjaWgEiQ0B5MBAAVo_GQMgwxMBj5NogP9kQ?e=Lk6pJa