K
Khách

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.

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp

Bước 2: x = a[i];

Bước 3:

Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách.

Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].

Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.

Bước 5: i = i+1; nếu i < n -> lặp lại bước 2, ngược lại -> Dừng.

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

*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

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

- 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.

18 tháng 7 2023

THAM KHẢO!

1.Thuật toán sắp xếp chèn (Insertion Sort):

def insertion_sort(arr):

  for i in range(1, len(arr)):

   key = arr[i]

   j = i - 1

   while j >= 0 and arr[j] > key:

    arr[j + 1] = arr[j]

    j -= 1

   arr[j + 1] = key

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = insertion_sort(A)

print("Dãy A sau khi sắp xếp chèn:", sorted_A)

2. Thuật toán sắp xếp chọn (Selection Sort):

def selection_sort(arr):

  for i in range(len(arr)):

   min_idx = i

   for j in range(i + 1, len(arr)):

    if arr[j] < arr[min_idx]:

     min_idx = j

   arr[i], arr[min_idx] = arr[min_idx], arr[i]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = selection_sort(A)

print("Dãy A sau khi sắp xếp chọn:", sorted_A)

3.Thuật toán sắp xếp nổi bọt (Bubble Sort):

def bubble_sort(arr):

  n = len(arr)

  for i in range(n - 1):

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

    if arr[j] > arr[j + 1]:

     arr[j], arr[j + 1] = arr[j + 1], arr[j]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = bubble_sort(A)

print("Dãy A sau khi sắp xếp nổi bọt:", sorted_A)

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

- Bắt đầu từ vị trí đầu tiên của danh sách (bên trái), so sánh các cặp số với nhau, nếu không đúng thứ tự nhỏ-lớn thì đảo vị trí.
- Sau khi chạy tới cuối danh sách, tiếp tục chạy lại từ vị trí đầu danh sách cho đến khi hoàn thành so sánh và đảo vị trí.

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

Ý 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.

QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023

1. Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.

2. Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.

3. Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:

Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.

Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

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.

QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023

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.

19 tháng 8 2023

def nhap_day_so():
   """Hàm nhập dãy số từ bàn phím"""
   n = int(input("Nhập số lượng phần tử của dãy: "))
   a = []
   for i in range(n):
       a.append(int(input(f"Nhập phần tử thứ {i+1}: ")))
   return a

def sap_xep_chen(a):
   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp chèn"""
   for i in range(1, len(a)):
       key = a[i]
       j = i - 1
       while j >= 0 and key < a[j]:
           a[j+1] = a[j]
           j -= 1
       a[j+1] = key
   return a

def sap_xep_chon(a):
   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp chọn"""
   for i in range(len(a)):
       min_idx = i
       for j in range(i+1, len(a)):
           if a[j] < a[min_idx]:
               min_idx = j
       a[i], a[min_idx] = a[min_idx], a[i]
   return a

 

def sap_xep_noi_bot(a):
   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp nổi bọt"""
   for i in range(len(a)):
       for j in range(0, len(a)-i-1):
           if a[j] > a[j+1]:
               a[j], a[j+1] = a[j+1], a[j]
   return a