Câu hỏi:
03/07/2023 253
Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương tình cài đặt ở trên cần thay đổi thế nào để sắp xếp một dãy theo thứ tự giám dần của giá trị.
Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương tình cài đặt ở trên cần thay đổi thế nào để sắp xếp một dãy theo thứ tự giám dần của giá trị.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Các thuật toán sắp xếp đơn giản như Bubble Sort, Insertion Sort . . . đều không thể xử lý được dữ liệu lớn. Thuật toán sắp xếp trộn lấy ý tưởng từ việc chia để trị để chia nhỏ bài toán thành các bài toán nhỏ hơn, sau đó giải quyết chúng. Từ đó sẽ giúp xử lý dữ liệu lớn một cách tốt hơn, tối ưu về mặt thời gian.
Ý tưởng đưa ra như sau:
Chia danh sách gồm n phần tử chưa được sắp xếp thành n danh sách con, mỗi danh sách chứa một phần tử (danh sách một phần tử được coi là đã sắp xếp).
Liên tục hợp nhất các danh sách con để tạo ra các danh sách con được sắp xếp mớ cho đến khi chỉ còn lại một danh sách. Đây sẽ là danh sách được sắp xếp.
Ví dụ:
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void InterchangeSort(int a[], int n){
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if(a[i] > a[j]) //nếu có nghịch thế thì đổi chỗ
Swap(a[i], a[j]);
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
Sách thầy cô Vietjack biên soạn:
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Giai đoạn I: Ở giai đoạn này. với mỗi lượt, mỗi dãy được chia làm hai dây nhỏ với mục tiêu sắp xếp tăng dần trên từng dãy nhỏ hình 1). Quá trình kết thúc khi mỗi
Lượt 1: Chia thành hai dãy, một dãy 2 bạn (Thi, An) và một dãy 3 bạn (Hoa, Lâm, Mai).
Lượt 2: Chia mỗi đây trong hai dây trên thành hai dãy nhỏ. lần hượt lá: (Thi), (An) (Hoa) và (Lâm, Mai).
Lượt 3: Chia dãy (Lâm, Mai) thành hai đây mỗi dãy có đúng một bạn: (Lâm), (Mai)
Lời giải
// Code from https://nguyenvanhieu.vn
#include<stdlib.h>
#include<stdio.h>
// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* Tạo các mảng tạm */
int L[n1], R[n2];
/* Copy dữ liệu sang các mảng tạm */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Gộp hai mảng tạm vừa rồi vào mảng arr*/
i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy các phần tử còn lại của mảng L vào arr nếu có */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy các phần tử còn lại của mảng R vào arr nếu có */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn
int m = l+(r-l)/2;
// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Hàm xuất mảng */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}// Code from https://nguyenvanhieu.vn
#include<stdlib.h>
#include<stdio.h>
// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* Tạo các mảng tạm */
int L[n1], R[n2];
/* Copy dữ liệu sang các mảng tạm */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Gộp hai mảng tạm vừa rồi vào mảng arr*/
i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy các phần tử còn lại của mảng L vào arr nếu có */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy các phần tử còn lại của mảng R vào arr nếu có */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn
int m = l+(r-l)/2;
// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Hàm xuất mảng */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 28 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 2: Tẩy xóa ảnh có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận