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.

Chọn bước:

1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.

=> Như vậy dễ nắm được các bước thực hiện và giúp bài toán có phương pháp giải chính xác hơn.

Cả hai thuật toán sắp xếp nổi bọt và sắp xếp chèn đều đơn giản và dễ cài đặt. Tuy nhiên, thuật toán sắp xếp chèn có thể được coi là đơn giản hơn vì nó sử dụng ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp chèn thực hiện việc chèn một phần tử vào một mảng đã được sắp xếp trước đó. Với mỗi phần tử trong mảng, nó sẽ so sánh nó với các phần tử đã được sắp xếp trước đó, và chèn phần tử đó vào vị trí thích hợp trong mảng. Điều này đòi hỏi ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt, do đó thuật toán sắp xếp chèn có hiệu suất tốt hơn khi sắp xếp một mảng lớn.

Trong khi đó, thuật toán sắp xếp nổi bọt cần thực hiện nhiều phép so sánh hơn và có thể không hiệu quả khi sắp xếp mảng lớn. Nó hoạt động bằng cách so sánh các cặp phần tử liên tiếp trong mảng và đổi chỗ chúng nếu chúng không được sắp xếp đúng thứ tự. Vì vậy, trong nhiều trường hợp, thuật toán sắp xếp chèn được ưa chuộng hơn do hiệu quả và tính đơn giản của nó.

Tham khảo:

#include <stdio.h>

#define GIOI "\nXep loai gioi"

#define KHA "\nXep loai kha"

#define TB "\nXep loai trung binh"

#define YEU "\nXep loai yeu"

/*

    Format code: Alt + Shift + F

*/

int main()

{

    // Nhập điểm 3 môn

    float diemToan;

    float diemVan;

    float diemAnh;

    float dtb;

    printf("\nNhap diem toan = ");

    scanf("%f", &diemToan);

    printf("\nNhap diem van = ");

    scanf("%f", &diemVan);

    printf("\nNhap diem anh = ");

    scanf("%f", &diemAnh);

    dtb = (diemToan + diemVan + diemAnh) / 3;

    printf("\nDTB = %.2f", dtb);

    if (dtb < 4)

{

        printf(YEU);

    }else if (dtb < 6.5){

        printf(TB);

    }else if(dtb < 8.0){

        printf(KHA);

    }else{

        printf(GIOI);

    }

}

Tham khảo:

Viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học:

void Insertion_Sort(int a[], int n){

int pos, i;

int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử

for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp

x = a[i]; pos = i-1;

//tìm vị trí chèn x

while((pos>=0)&&(a[pos]>x)){

                //kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới

a[pos+1] = a[pos];

pos--;

}

a[pos+1] = x;//chèn x vào danh sách

}

}

void main()

{

int a[5] = {8, 4, 1, 6, 5};

Insertion_Sort(a, 5);

cout<<"Mang sau khi sap xep:"<<endl;

for(int i=0;i<5;i++){

cout<<a[i]<<" ";

}

system("pause");

def bubble_sort(arr):

     n = len(arr)

     for i in range(n):

          for j in range(i + 1, n):

               if arr[j] < arr[i]:

                    arr[i], arr[j] = arr[j], arr[i]

     return arr

arr = [64, 25, 12, 22, 11]

print("Mang chua sap xep la:", arr)

print("Mang da sap xep la:", bubble_sort(arr))