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.

23 tháng 8 2023

THAM KHẢO!

Nếu dãy ban đầu đã được sắp xếp, thì thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể, các bước của thuật toán sẽ được thực hiện như sau:

Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí của nó trong dãy đã được sắp xếp.

Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Nếu phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Tiếp tục kiểm tra và so sánh từng phần tử còn lại trong dãy với các phần tử trước nó. Nếu phần tử đang xét đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào được thực hiện trên dãy ban đầu, vì dãy đã được sắp xếp.

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

18 tháng 7 2023

Nếu muốn sắp xếp danh sách theo thứ tự giảm dần thay vì thứ tự tăng dần, ta cần thay đổi câu lệnh so sánh trong vòng lặp của thuật toán sắp xếp. Cụ thể,cần đảo ngược dấu so sánh.

 THAM KHẢO!
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

27 tháng 10 2021

Hai thuật toán đó sẽ ngược nhau

23 tháng 8 2023

1.Thuật toán tìm kiếm tuần tự:

- Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n)

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (106 us / phép tính) = 106

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (106us / phép tính) = 6 * 107

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính) = 3.6 * 109

2.Thuật toán sắp xếp chèn:

- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(102

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * (106us / phép tính)) =103

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 6 * 104

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106

3. Thuật toán sắp xếp chọn:

- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)

- Giá trị lớn nhất của n là: n = sqrt(1 giây * (106us / phép tính)) = 1000.

Thời gian thực thi là 1 phút:

Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 60000.

Thời gian thực thi là 1 giờ:

Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106

 

19 tháng 8 2023

Tham khảo:

Viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học:

void Insertion_Sort(int a[], int n){

int pos, i;

int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử

for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp

x = a[i]; pos = i-1;

//tìm vị trí chèn x

while((pos>=0)&&(a[pos]>x)){

                //kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới

a[pos+1] = a[pos];

pos--;

}

a[pos+1] = x;//chèn x vào danh sách

}

}

void main()

{

int a[5] = {8, 4, 1, 6, 5};

Insertion_Sort(a, 5);

cout<<"Mang sau khi sap xep:"<<endl;

for(int i=0;i<5;i++){

cout<<a[i]<<" ";

}

system("pause");

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)

22 tháng 8 2023

Cả hai thuật toán sắp xếp nổi bọt và sắp xếp chèn đều đơn giản và dễ cài đặt. Tuy nhiên, thuật toán sắp xếp chèn có thể được coi là đơn giản hơn vì nó sử dụng ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp chèn thực hiện việc chèn một phần tử vào một mảng đã được sắp xếp trước đó. Với mỗi phần tử trong mảng, nó sẽ so sánh nó với các phần tử đã được sắp xếp trước đó, và chèn phần tử đó vào vị trí thích hợp trong mảng. Điều này đòi hỏi ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt, do đó thuật toán sắp xếp chèn có hiệu suất tốt hơn khi sắp xếp một mảng lớn.

Trong khi đó, thuật toán sắp xếp nổi bọt cần thực hiện nhiều phép so sánh hơn và có thể không hiệu quả khi sắp xếp mảng lớn. Nó hoạt động bằng cách so sánh các cặp phần tử liên tiếp trong mảng và đổi chỗ chúng nếu chúng không được sắp xếp đúng thứ tự. Vì vậy, trong nhiều trường hợp, thuật toán sắp xếp chèn được ưa chuộng hơn do hiệu quả và tính đơn giản của nó.