viết chương trình và mã giả của thuật toán
sắp xếp chèn tuyến tính
sắp xếp nhanh áp dụng phân đoạn Lomuto

Question

viết chương trình và mã giả của thuật toán 
sắp xếp chèn tuyến tính
sắp xếp nhanh áp dụng phân đoạn Lomuto

_End_ · Accepted Answer

Timi · Answer

Dưới đây là chương trình và mã giả của hai thuật toán bạn yêu cầu: sắp xếp chèn tuyến tính (Insertion Sort) và sắp xếp nhanh áp dụng phân đoạn Lomuto (Quick Sort với phân đoạn Lomuto). --- ### 1. Thuật toán sắp xếp chèn tuyến tính (Insertion Sort) #### Mã giả (Pseudocode): ``` InsertionSort(A) for i from 1 to length(A) - 1 key = A[i] j = i - 1 while j >= 0 and A[j] > key A[j + 1] = A[j] j = j - 1 A[j + 1] = key ``` #### Chương trình bằng ngôn ngữ Python: ```python def insertion_sort(A): for i in range(1, len(A)): key = A[i] j = i - 1 while j >= 0 and A[j] > key: A[j + 1] = A[j] j -= 1 A[j + 1] = key # Ví dụ sử dụng arr = [5, 2, 9, 1, 5, 6] insertion_sort(arr) print(arr) # Kết quả: [1, 2, 5, 5, 6, 9] ``` --- ### 2. Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto (Quick Sort với phân đoạn Lomuto) #### Mã giả (Pseudocode): ``` QuickSort(A, low, high) if low < high p = Partition(A, low, high) QuickSort(A, low, p - 1) QuickSort(A, p + 1, high) Partition(A, low, high) pivot = A[high] i = low - 1 for j from low to high - 1 if A[j] <= pivot i = i + 1 swap A[i] and A[j] swap A[i + 1] and A[high] return i + 1 ``` #### Chương trình bằng ngôn ngữ Python: ```python def partition(A, low, high): pivot = A[high] i = low - 1 for j in range(low, high): if A[j] <= pivot: i += 1 A[i], A[j] = A[j], A[i] A[i + 1], A[high] = A[high], A[i + 1] return i + 1 def quick_sort(A, low, high): if low < high: p = partition(A, low, high) quick_sort(A, low, p - 1) quick_sort(A, p + 1, high) # Ví dụ sử dụng arr = [10, 7, 8, 9, 1, 5] quick_sort(arr, 0, len(arr) - 1) print(arr) # Kết quả: [1, 5, 7, 8, 9, 10] ``` --- Nếu bạn cần giải thích chi tiết hơn hoặc muốn chương trình bằng ngôn ngữ khác, bạn có thể hỏi thêm nhé!

Quỳnh Anh · Answer

{"userId":5090991,"userName":"kimngan1008"}

1. Sắp xếp Chèn (Insertion Sort)

Mã giả

text

Thủ tục InsertionSort(A):

Cho i chạy từ 1 đến n-1:

key = A[i]

j = i - 1

Trong khi j >= 0 và A[j] > key:

A[j + 1] = A[j]

j = j - 1

A[j + 1] = key

Use code with caution.

Chương trình (Python)

python

def insertion_sort(arr):

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

key = arr[i]

j = i - 1

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

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

return arr

# Ví dụ

arr = [12, 11, 13, 5, 6]

print("Mảng sau khi sắp xếp chèn:", insertion_sort(arr))

Use code with caution.

________________________________________

2. Sắp xếp Nhanh (Quick Sort) dùng phân đoạn Lomuto

Mã giả

text

Hàm Partition(A, low, high):

pivot = A[high] // Chọn phần tử cuối làm chốt

i = low - 1

Cho j chạy từ low đến high - 1:

Nếu A[j] <= pivot:

i = i + 1

Hoán đổi A[i] và A[j]

Hoán đổi A[i + 1] và A[high]

Trả về i + 1

Thủ tục QuickSort(A, low, high):

Nếu low < high:

p = Partition(A, low, high)

QuickSort(A, low, p - 1)

QuickSort(A, p + 1, high)

Use code with caution.

Chương trình (Python)

python

def partition_lomuto(arr, low, high):

pivot = arr[high]

i = low - 1

for j in range(low, high):

if arr[j] <= pivot:

i += 1

arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return i + 1

def quick_sort(arr, low, high):

if low < high:

p = partition_lomuto(arr, low, high)

quick_sort(arr, low, p - 1)

quick_sort(arr, p + 1, high)

# Ví dụ

data = [10, 7, 8, 9, 1, 5]

quick_sort(data, 0, len(data) - 1)

print("Mảng sau khi sắp xếp nhanh (Lomuto):", data)

viết chương trình và mã giả của thuật toán sắp xếp chèn tuyến tính sắp xếp nhanh áp dụng phân đoạn Lomuto