Thuật toán trong Python là gì? Những điều bạn cần biết về các thuật toán trong Python

1. Thuật toán trong Python là gì?

Thuật toán là một dòng code hữu hạn được phát triển để thực thi theo trình tự xác định. Thuật toán dùng để giải quyết vấn đề nhằm tạo ra kết quả như mong muốn. Một thuật toán thường được viết theo một ngôn ngữ chung pseudo-code (tạm dịch là mã giả) và sau đó sẽ được triển khai bằng bất kỳ ngôn ngữ lập trình nào. Các lập trình viên thường sẽ viết mã giả của thuật toán ra giấy và thực hiện kiểm thử trước khi thực hiện chính thức.

Hiểu đơn giản thì thuật toán trong Python là gì? Đó là các đoạn code được phát triển để giải quyết một vấn đề cụ thể. Bạn có thể viết một thuật toán bằng nhiều ngôn ngữ lập trình khác nhau. 

2. Các bước viết thuật toán hiệu quả

Ở phần trên chúng ta đã cùng nhau tìm hiểu thuật toán trong Python là gì. Tiếp theo, bạn hãy xem các bước để viết thuật toán hiệu quả:

• Tìm hiểu vấn đề: trước khi viết một thuật toán, bạn hãy dành thời gian để phân tích các yêu cầu, yếu tố ràng buộc, đầu vào và đầu ra dự kiến.

• Lựa chọn cấu trúc dữ liệu phù hợp: đây là bước khá quan trọng để bạn thuật toán bạn viết được hiệu quả.
• Phân tích mức độ phức tạp về thời gian và không gian của vấn đề bạn đang cần xử lý.
• Thiết kế và kiểm tra thuật toán: bạn có thể viết các thuật toán bằng mã giả hoặc sơ đồ và thực hiện kiểm tra với nhiều đầu vào khác nhau.
• Tối ưu hóa thuật toán và kiểm tra lại: tối ưu hóa các thuật toán để giảm các bước tính toán dư thừa và cả các bước không cần thiết.
• Ghi lại thuật toán: bạn hãy ghi lại các thuật toán, kèm theo là chú thích chi tiết về logic, đầu vào, đầu ra, độ phức tạp về không gian và thời gian của chúng.

 3. Các thuật toán trong Python phổ biến

Tiếp theo, chúng ta hãy cùng tìm hiểu về các thuật toán phổ biến trong Python qua nội dung ngay sau đây.

3.1. Thuật toán Binary Search

Thuật toán Binary Search (Tìm kiếm nhị phân) là một thuật toán hiệu quả để tìm kiếm một phần tử trong một dãy dữ liệu đã được sắp xếp. Dãy dữ liệu có thể là một mảng hoặc danh sách. Thuật toán này hoạt động bằng cách chia nhỏ dãy dữ liệu ban đầu thành các phần nhỏ hơn và tiến hành tìm kiếm trong phần nào có khả năng chứa giá trị cần tìm. Nếu giá trị đích lớn hơn giá trị ở giữa, nó sẽ tìm kiếm ở nửa bên phải của mảng con. Ngược lại, nếu giá trị đích nhỏ hơn giá trị ở giữa, nó sẽ tìm kiếm ở nửa bên trái của mảng con.

Bạn hãy xem ví dụ về cách viết thuật toán Binary Search:

def binary_search(array, x):  

lower = 0  

higher = len(array) - 1  

middle = 0  

while lower <= higher:  

middle = (higher + lower) // 2  

if array[middle] < x:  

lower = middle + 1  

elif array[middle] > x:  

higher = middle - 1  

    else:  

return middle  

return -1  

array = [5, 8, 16, 37, 59, 80]  

x = 59  

index = binary_search(array, x)  

print(f"Array = {array}")  

if index != -1:  

print(f"The given element {x} is present at the index", str(index))  

else:  

print(f"The given element {x} is not present in the array")  

x = 35  

index = binary_search(array, x)  

if index != -1:  

print(f"The given element {x} is present at the index", str(index))  

else:  

print(f"The given element {x} is not present in the array") 

Kết quả có được:

Array = [5, 8, 16, 37, 59, 80]

The given element 59 is present at the index 4

The given element 35 is not present in the array

3.2. Thuật toán Linear Search

Thuật toán Linear Search là thuật toán tìm kiếm đơn giản nhất. Tìm kiếm tuyến tính thường được sử dụng khi dữ liệu chưa được sắp xếp hoặc trong không gian tìm kiếm phạm vi nhỏ. Linear Search hoạt động theo nguyên tắc kiểm tra lần lượt từng phần tử trong cấu trúc dữ liệu cho đến khi tìm ra kết quả là khớp hoặc không khớp.

Ví dụ thuật toán Linear Search:

def linear_search(array, x):    

 for i in range(len(array)):    

  if array[i] == x:    

return i 

return -1    

array = [5, 8, 16, 37, 59, 80]  

print(f"Array = {array}")   

x = 59    

index = linear_search(array, x)    

if index != -1:    

print(f"The given element {x} is present at the index", str(index))    

else:    

print(f"The given element {x} is not present in the array")    

x = 35    

index = linear_search(array, x)    

if index != -1:    

print(f"The given element {x} is present at the index", str(index))    

else:    

print(f"The given element {x} is not present in the array")  

Từ ví dụ chúng ta có được kết quả như sau:

Array = [5, 8, 16, 37, 59, 80]

The given element 59 is present at the index 4

The given element 35 is not present in the array

3.3. Các thuật toán sắp xếp Python

Các thuật toán sắp xếp hoạt động theo nguyên tắc sắp xếp các phần tử theo một thứ tự cụ thể, chẳng hạn như tăng dần hoặc giảm dần. Chúng ta sẽ cùng tìm hiểu về một số thuật toán sắp xếp Python cơ bản: insertion sort, merge sort và quick sort.

3.3.1. Thuật toán Insertion Sort

Thuật toán Insertion Sort (Sắp xếp chèn) là một thuật toán sắp xếp đơn giản và hiệu quả, thường được sử dụng để sắp xếp danh sách hoặc mảng các phần tử. Thuật toán này hoạt động bằng cách chia dãy thành hai phần: một phần đã được sắp xếp và một phần chưa được sắp xếp. Ban đầu, phần đã sắp xếp chứa một phần tử đầu tiên của dãy, và phần chưa sắp xếp chứa các phần tử còn lại. Thuật toán tiếp tục chọn phần tử từ phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp cho đến khi toàn bộ dãy đã được sắp xếp. Tương tự như cách chúng ta sắp xếp các lá bài, thuật toán Insertion Sort lọc các phần tử chưa được sắp xếp trong danh sách và chèn từng phần tử vào đúng vị trí.

Ví dụ về thuật toán Insertion Sort: 

def insertion_sort(array):  

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

key = array[i]

c = i-1
while c >= 0 and key < array[c]:  
array[c + 1] = array[c]  

c -= 1  

array[c + 1] = key  

array = [23, 42, 3, 83, 36, 49, 19]  

print("Unsorted array:", array)  

array = [23, 42, 3, 83, 36, 49, 19]  

print("Unsorted array:", array)  

Kết quả chúng ta có được như sau:
Unsorted array: [23, 42, 3, 83, 36, 49, 19]

Sorted array: [3, 19, 23, 36, 42, 49, 83]

3.3.2. Merge Sort trong Python

Merge Sort trong Python là thuật toán sắp xếp, dùng để hợp nhất một thuật toán chia để trị Python. Thuật toán này chia các mảng đầu vào thành hai nửa, sắp xếp từng nửa một cách độc lập và sau đó kết hợp chúng lại với nhau theo thứ tự. 

Bạn hãy xem ví dụ thuật toán Merge Sort trong Python sau đây:

def merge_sort(arr):  

 if len(arr) <= 1:  

return arr  

mid = len(arr) // 2  

left_half = arr[:mid]  

right_half = arr[mid:]  

merge_sort(left_half)  

merge_sort(right_half)  

  merge(arr, left_half, right_half)  

def merge(arr, left, right):  

i = j = k = 0  

while i < len(left) and j < len(right):  

if left[i] < right[j]:  

arr[k] = left[i]  

i += 1  

else:  

arr[k] = right[j]  

  j += 1  

k += 1  

while i < len(left):  

arr[k] = left[i]  

i += 1  

k += 1  

while j < len(right):  

arr[k] = right[j]  

 j += 1  

  k += 1  

array = [23, 42, 3, 83, 36, 49, 19]    

print("The given array is:", array)    

merge_sort(array)    

print("The sorted array is:", array)  

Kết quả:
The given array is: [23, 42, 3, 83, 36, 49, 19]

The sorted array is: [3, 19, 23, 36, 42, 49, 83]

3.3.3. Thuật toán Quick Sort Python

Thuật toán Quick Sort Python là một thuật toán sắp xếp hiệu quả và thường được sử dụng để sắp xếp danh sách hoặc mảng các phần tử. Nó thuộc loại thuật toán chia để trị và hoạt động dựa trên nguyên tắc chọn một phần tử chốt (pivot) từ dãy dữ liệu và sau đó chia dãy thành hai phần: một phần có các phần tử nhỏ hơn hoặc bằng pivot và một phần có các phần tử lớn hơn pivot. Sau đó, thuật toán được áp dụng đệ quy cho cả hai phần này.
Ví dụ thuật toán Quick Sort Python:

def quick_sort(arr, low, high):  

if low < high:  

pivot_index = partition(arr, low, high)  

quick_sort(arr, low, pivot_index - 1)  

quick_sort(arr, pivot_index + 1, high)  

def partition(arr, low, high):  

pivot = arr[high]  

pivot_index = low  

for i in range(low, high):  

if arr[i] <= pivot:  

arr[i], arr[pivot_index] = arr[pivot_index], arr[i]  

pivot_index += 1  

arr[pivot_index], arr[high] = arr[high], arr[pivot_index]  

return pivot_index  

array = [23, 42, 3, 83, 36, 49, 19]  

print("The unsorted array is:", array)  

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

print(f'The sorted array is: {array}') 

Kết quả:  

The unsorted array is: [23, 42, 3, 83, 36, 49, 19]

The sorted array is: [3, 19, 23, 36, 42, 49, 83]

4. Lời Kết

Hy vọng rằng qua những nội dung chia sẻ ở trên, bạn đã hiểu được thuật toán trong Python là gì. Thông qua bài viết, chúng ta đã cùng nhau khám phá về các thuật toán tìm kiếm và các thuật toán sắp xếp Python. Những thuật toán này sẽ giúp việc viết code của bạn hiệu quả hơn, đồng thời giúp bạn có nền tảng vững chắc để giải quyết vấn đề.

Nếu bạn đang quan tâm đến lập trình Python thì hãy tham khảo ngay khóa học Python tại ICANTECH nhé!

Nguồn ảnh: ICANTECH.