5
0
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
7
2
#include <iostream>
using namespace std;
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
// In ra mỗi bước chèn phần tử
cout << key << " " << j + 1 << endl;
}
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
insertion_sort(arr, n);
return 0;
}
Trong đó, hàm insertion_sort là hàm thực hiện thuật toán sắp xếp chèn và in ra từng bước chèn phần tử. Cụ thể, mỗi bước sẽ lấy phần tử thứ i trong mảng arr làm phần tử cần chèn. Sau đó, với j chạy từ i-1 đến 0, ta sẽ dịch chuyển các phần tử lớn hơn key một vị trí sang phải để tạo chỗ cho key. Cuối cùng, key sẽ được chèn vào vị trí j+1. Mỗi lần chèn, ta sẽ in ra giá trị của phần tử key và vị trí j+1 mà nó được chèn vào.
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin