Viết ba chương trình mô phỏng các thuật toán sắp xếp chèn, sắp xếp

Câu hỏi số 769244:

Vận dụng

Viết ba chương trình mô phỏng các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt mà em đã biết. Cho biết thời gian thực hiện các chương trình trên với bộ dữ liệu đầu vào là dãy A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].

Quảng cáo

Xem lời giải

Câu hỏi:769244

Giải chi tiết

Chương trình gộp tính thời gian thực tế cho ba thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt như sau:

1 from time import perf_counter

2 def InsertionSort(A):

3 n = len(A)

4 for i in range(1,n):

5 value = A[i]

6 j = i-1

7 while j >= 0 and A[j] > value:

8 A[j+1] = A[j]

9 j = j – 1

10 A[j+1] = value

11 deft SelectionSort(A):

12 n = len(A)

13 for i in range(n-1):

14 iMin = i

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

16 if A[j] < A[iMin]:

17 iMin = j

18 A[i],A[iMin] = A[iMin],A[i]

19 deft BubbleSort(A):

20 n = len(A)

21 for i in range(n-1):

22 for j in range(n-1-i):

23 if A[j] > A[j+1]:

24 A[j],A[j+1] = A[j+1],A[j]

27 A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

28 A1,A2,A3 = A.copy(),A.copy(), A.copy()

29 t1 = perf_counter()

30 InsertionSort(A1)

31 t2 = perf_counter()

32 print("Sắp xếp chèn:",t2-t1)

33 t1 = perf_counter()

34 SelectionSort(A)

35 t2 = perf_counter()

36 print("sắp xếp chọn:",t2-t1)

37 t1 = perf_counter()

38 BubbleSort(A)

39 t2 = perf_counter()

40 print("sắp xếp nổi bọt:",t2-t1)

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.