Mô phỏng thuật toán sắp xếp dãy số không giảm với N = 10 và dãy A : 6,1,5,3,7,8,10,7,12,4 . Hãy cho biết với lần duyệt thứ mấy để sắp xếp thành 1,3,4,5,6,7,7,8,10,12
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
1:
-Bước 1: Nhập n và nhập dãy số, nhập k
-Bước 2: dem←0; i←1;
-Bước 3: Nếu a[i]=k thì dem←dem+1;
-Bước 4: i←i+1;
-Bước 5: Nếu i<=n thì quay lại bước 3
-Bước 6: Xuất dem
-Bước 7: Kết thúc
#include <bits/stdc++.h>
using namespace std;
long long a[1000],n,i,tam,j;
int main()
{
cin>>n;
for (i=1; i<=n; i++)
cin>>a[i];
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
if (a[i]>a[j]) swap(a[i],a[j]);
for (i=1; i<=n; i++)
cout<<a[i]<<" ";
return 0;
}
*Thuật toán sắp xếp chèn (Insertion Sort):
import time
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chèn
insertion_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là 0 giây
*Thuật toán sắp xếp chọn:
import time
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chọn
selection_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây
*Thuật toán sắp xếp nổi bọt:
import time
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp nổi bọt
bubble_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây
#include <bits/stdc++.h>
using namespace std;
long long b[10],i,j,n;
int main()
{
n=10;
for (i=1; i<=n; i++)
cin>>b[i];
for (i=1; i<=n-1; i++)
for (j=i+1;j<=n;j++)
if (b[i]<=b[j]) swap(b[i],b[j]);
for (i=1; i<=n; i++)
cout<<b[i]<<" ";
return 0;
}
- Bước 1: i = 0;
- Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].
- Bước 3: Đổi chỗ a[min] và a[i].
- Bước 4: Nếu i < n-1 thì gán i = i+1; rồi lặp lại bước 2, ngược lại -> Dừng.
#include <bits/stdc++.h>
using namespace std;
long long a[1000],i,n;
int main()
{
cin>>n;
for (i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
for (i=1; i<=n; i++) cout<<a[i]<<" ";
return 0;
}