Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn.
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.
Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán.
Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp.
Tham khảo:
Xác định cách thức sắp xếp chèn: Sắp xếp chèn là một thuật toán đơn giản, trong đó từng phần tử của dãy đang xét được chèn vào vị trí đúng của dãy con đã được sắp xếp trước đó. Bước này định nghĩa cách thức sắp xếp chèn, bao gồm quá trình so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng.
1. Bước này đã định nghĩa cách thức sắp xếp chèn, bao gồm cách thức so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.
2. Kết quả của bước này khác với kết quả của bước trước đó về cách thức sắp xếp chèn được định nghĩa và thực hiện. Bước này tập trung vào việc định nghĩa và triển khai thuật toán sắp xếp chèn cụ thể, trong khi bước trước đó có thể là các bước chuẩn bị dữ liệu, định nghĩa bài toán, hoặc thiết kế các thuật toán phụ trợ khác.
Thuật toán sắp xếp nổi bọt hoạt động bằng cách so sánh các phần tử kế tiếp trong danh sách và hoán đổi chúng nếu chúng không được sắp xếp theo thứ tự. Quá trình lặp sẽ tiếp tục cho đến khi tất cả các phần tử đều được sắp xếp. Vì vậy khi màu của tất cả các mũi tên đều đỏ trong sơ đồ mô phỏng thì có nghĩa là không còn phần tử nào được sắp xếp theo thứ tự tăng dần hoặc giảm dần và không cần thực hiện bất kỳ hoán đổi nào nữa.
Ý tưởng: Sau khi nhập dãy xong rồi chúng ta sẽ xét từng phần tử trong dãy nếu có phần tử nào chia 10 dư 0 hoặc 5 thì tăng dem lên, và dem chính là két quả của đề bài
#include <bits/stdc++.h>
using namespace std;
long long a,b;
int main()
{
cin>>a>>b;
cout<<a<<" "<<b<<endl;
swap(a,b);
cout<<a<<" "<<b;
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
Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.