1. Sắp xếp chèn (Insertion Sort)

Ý tưởng: Insertion Sort lấy ý tưởng từ việc chơi bài, dựa theo cách người chơi "chèn" thêm một quân bài mới vào bộ bài đã được sắp xếp trên tay.

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.

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.

Chúng ta có thể bỏ hết các hàm trong một chương trình và thay thế bằng một khối lệnh lớn hơn để tạo thành một chương trình kiểu nguyên khối. Tuy nhiên, việc này không phải lúc nào cũng là tối ưu và có thể dẫn đến một số vấn đề như sau:

- Khó quản lý và bảo trì: Khi chương trình trở nên lớn hơn thì việc duy trì và sửa lỗi sẽ trở nên phức tạp và khó khăn hơn khi tất cả các lệnh được đặt trong một khối lệnh duy nhất.

- Không tái sử dụng được code: Nếu các phần code được sử dụng nhiều lần trong chương trình, việc đặt chúng vào các hàm riêng biệt sẽ giúp tiết kiệm thời gian và tối ưu hóa mã nguồn.

- Không tận dụng được tính mô đun của chương trình: Một chương trình mô đun có thể được chia thành các phần riêng biệt và phụ thuộc lẫn nhau. Việc bỏ hết các hàm và chuyển thành chương trình kiểu nguyên khối sẽ khiến chương trình mất đi tính mô đun và dễ dàng gây ra các vấn đề về phụ thuộc giữa các phần của chương trình.

Lập trình mô-đun hoá là một phương pháp trong phát triển phần mềm, trong đó toàn bộ hệ thống được chia thành các phần nhỏ hơn gọi là mô-đun, mỗi mô-đun có chức năng cụ thể và độc lập với các mô-đun khác. Việc phát triển phần mềm bằng phương pháp này giúp đơn giản hóa quá trình phát triển, bảo trì và nâng cấp phần mềm.

Lập trình mô-đun hoá giúp tăng tính tái sử dụng của các phần mềm vì mỗi mô-đun có thể được sử dụng lại trong các dự án khác. Việc tái sử dụng này giúp tiết kiệm thời gian và tài nguyên phát triển, đồng thời giảm thiểu số lượng lỗi liên quan đến việc lập trình lại các chức năng đã có sẵn.

Hơn nữa, lập trình mô-đun hoá giúp tăng tính bảo trì của các phần mềm bởi vì mỗi mô-đun được phát triển và kiểm thử độc lập với các mô-đun khác. Điều này giúp đơn giản hóa quá trình bảo trì và nâng cấp phần mềm vì chỉ cần sửa đổi một mô-đun cụ thể thay vì phải sửa đổi toàn bộ hệ thống.

Tóm lại, lập trình mô-đun hoá là một phương pháp quan trọng trong phát triển phần mềm, giúp tăng tính tái sử dụng, dễ bảo trì, dễ mở rộng và giảm thiểu các lỗi liên quan đến tính tương tác giữa các phần của hệ thống.

Theo em, đây là kết quả lập trình theo phương pháp mô đun hoá.

Vì bài toán được viết theo các bước từ việc lớn, thiết kế các hàm, viết các hàm, tiến hành viết chương trình.

Đúng vì khi phân tích ta đã sắp xếp theo các bước giải theo tuần tự bài toán.

Diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ khác với dùng phân đoạn Hoare. Sự khác biệt giữa phương pháp phân đoạn Lomuto và phân đoạn Hoare trong thuật toán QuickSort là ở việc chọn pivot, cách phân đoạn và cách sắp xếp các phần tử.

Cụ thể, phương pháp phân đoạn Lomuto sẽ chọn pivot là phần tử cuối cùng của mảng, phân đoạn theo pivot và sau đó đưa pivot về giữa hai phân đoạn, tiếp tục thực hiện thuật toán QuickSort trên hai phân đoạn trái và phải của pivot. Trong khi đó, phương pháp phân đoạn Hoare sẽ chọn pivot là phần tử ở giữa mảng, đưa hai con trỏ từ đầu và cuối mảng trỏ tới nhau và dịch chuyển chúng sao cho phần tử bên trái pivot lớn hơn pivot, phần tử bên phải pivot nhỏ hơn pivot, sau đó đưa pivot về vị trí mới và thực hiện QuickSort trên hai phân đoạn trái và phải của pivot.

THAM KHẢO!

Thuật toán QuickSort được xây dựng theo chiến lược "chia để trị" bởi vì nó phân chia dãy số cần sắp xếp thành các phần nhỏ hơn, sau đó sắp xếp từng phần đó và kết hợp các phần đã sắp xếp lại thành dãy số đã được sắp xếp.

Cụ thể, thuật toán QuickSort chia dãy số cần sắp xếp thành hai phần dựa trên một phần tử được gọi là pivot. Tất cả các phần tử nhỏ hơn pivot được đưa về bên trái pivot, còn các phần tử lớn hơn pivot được đưa về bên phải pivot. Sau đó, thuật toán đệ quy được áp dụng lên từng phần của dãy số này, cho đến khi các phần con chỉ còn duy nhất một phần tử. Cuối cùng, các phần đã sắp xếp lại với nhau để tạo ra dãy số đã được sắp xếp.

Vì vậy, chiến lược "chia để trị" của QuickSort cho phép thuật toán chia nhỏ vấn đề lớn hơn thành các vấn đề nhỏ hơn, giúp cho việc giải quyết các vấn đề này trở nên đơn giản và hiệu quả hơn."

Tham khảo:

a)Gợi ý

void swap(int *a,int *b){

int temp=*a;

*a=*b;

*b=temp;

}

void bubblesort(int arr[],int n){

for(int i=0; i<n-1; i++){

for(int j=0; j<n-i-1; j++){

if(arr[j]>arr[j+1]){

swap(&arr[j],&arr[j+1]);

}

}

}

}

b) Gợi ý

void quickSort(int a[], int l, int r){

int p = a[(l+r)/2];

int i = l, j = r;

while (i < j){

while (a[i] < p){

i++;

}

while (a[j] > p){

j--;

}

if (i <= j){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

}

if (i < r){

quickSort(a, i, r);

}

if (l < j){

quickSort(a, l, j);

}

}

Câu lệnh in ra màn hình: print(".....")

Các bước thực hiện

- Phân tích bài toán.

- Độ phức tạp thuật toán.

a. Dựa trên mã lệnh thuật toán cho trong Hình 3.

b) Dựa trên mã lệnh thuật toán cho trong Hình 5.