Lập trình Python
4783
27/10/2023
Những điều bạn cần biết về thuật toán sắp xếp của Python
Thuật toán sắp xếp là một trong những thuật toán được sử dụng thường xuyên nhất trong Python. Có vô vàn cách triển khai và áp dụng thuật toán sắp xếp vào các chương trình khác nhau làm cho code hiệu quả hơn. Để làm được như vậy bạn cần hiểu chính xác về các thuật toán sắp xếp của Python. Từ đó, bạn sẽ biết cách sử dụng chúng để giải quyết hiệu quả các vấn đề.
1. Tầm quan trọng của thuật toán sắp xếp trong Python
Bạn có thể sử dụng thuật toán sắp xếp để giải quyết nhiều vấn đề tưởng chừng phức tạp trở nên đơn giản hơn như:
- Tìm kiếm một danh mục trong danh sách hoạt động
- Lựa chọn các danh mục từ danh sách dựa trên mối quan hệ của chúng với các mục còn lại.
- Tìm kiếm các giá trị trùng lặp trong danh sách
- Phân phối các danh mục trong danh sách
Từ các ứng dụng thương mại đến nghiên cứu học thuật hay bất kỳ lĩnh vực nào khác khác, có vô số cách bạn có thể sử dụng tính năng sắp xếp để tiết kiệm thời gian và công sức.
2. 6 thuật toán sắp xếp cơ bản của Python
Phần tiếp theo, chúng ta sẽ cùng nhau tìm hiểu 6 thuật toán sắp xếp cơ bản và phổ biến nhất của Python.
2.1. Bubble Sort (Thuật toán sắp xếp nổi bọt)
Bubble Sort (sắp xếp nổi bọt) là một thuật toán sắp xếp đơn giản nhưng không hiệu quả cho các danh sách lớn. Nó hoạt động bằng cách so sánh và hoán đổi các phần tử liên tiếp nếu chúng không ở trong thứ tự đúng. Thuật toán lặp qua danh sách nhiều lần cho đến khi không còn phần tử nào cần hoán đổi nữa. Dưới đây là mã giả của thuật toán bubble sort:
Ví dụ về cách sử dụng bubble sort:
def bubble_Sort(array):
length = len(array)
for iterator_1 in range(length):
for iterator_2 in range(0, length-iterator_1-1):
if array[iterator_2] > array[iterator_2 + 1] :
array[iterator_2], array[iterator_2 + 1] = array[iterator_2 + 1], array[iterator_2]
bubble_Sort([75,1,54,34,56,78])
print ("Array values after sorting:")
for i in range(len(array)):
print("%d" %array[i])
Kết quả có được
Array values after sorting:
1
34
54
56
75
78
2.2. Selection Sort
Selection Sort (sắp xếp lựa chọn) là một trong những thuật toán sắp xếp cơ bản nhất. Selection Sort liên quan đến việc tìm phần tử nhỏ nhất từ tập hợp chưa sắp xếp và định vị phần tử đó ở đầu tập hợp chưa sắp xếp. Khi các thao tác này lặp lại trên tất cả các phần tử trong tập hợp, bạn sẽ một tập hợp được sắp xếp hoàn chỉnh.
Mẫu ví dụ thuật toán selection sort:
def selection_sort(arr):
n = len(arr)
# Lặp qua từng phần tử của danh sách
for i in range(n):
# Tìm phần tử nhỏ nhất trong danh sách chưa được sắp xếp
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên chưa được sắp xếp
arr[i], arr[min_index] = arr[min_index], arr[i]
my_list = [64, 25, 12, 22, 11]
selection_sort(my_list)
print("Danh sách đã sắp xếp:")
for i in my_list:
print(i)
Kết quả:
Danh sách đã sắp xếp:
11
12
22
25
64
2.3. Insertion Sort (Thuật toán sắp xếp chèn)
Trong Insertion Sort (thuật toán sắp xếp chèn) cơ chế sắp xếp được thực hiện bằng cách xây dựng một mảng được sắp xếp với một danh mục, tại một thời điểm. Các phần tử của mảng được so sánh một cách tuần tự và được sắp xếp lại theo thứ tự cụ thể. Các thành phần của mảng cũng được so sánh tuần tự với từng phần tử và được sắp xếp đồng thời theo thứ tự.
Ví dụ về insertion sort trong Python:
def insertion_Sort(array):
for temp_element1 in range(1, len(array)):
key = array[temp_element1]
temp_element2 = temp_element1 -1
while temp_element2 >= 0 and key < array[temp_element2] :
array[temp_element2 + 1] = array[temp_element2]
temp_element2 -= 1
array[temp_element2 + 1] = key
array = [75,34,54,56,78,1]
insertion_Sort(array)
for i in range(len(array)):
print("% d" % array[i])
Kết quả đầu ra:
1
34
54
56
75
78
2.4. Merge Sort
Merge Sort (thuật toán sắp xếp hợp nhất) hoạt động dựa trên nguyên tắc của thuật toán chia để trị. Với thuật toán này, dữ liệu đầu vào đã cho được ghép thành hai nửa, các nửa đó được sắp xếp và hợp nhất lại với nhau. Trong Python, hàm merge() được sử dụng để có được kết quả quá trình hợp nhất.
Ví dụ code của merge sort:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Đệ quy sắp xếp từng phần
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
# Hợp nhất hai danh sách con đã sắp xếp
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
my_list = [38, 27, 43, 3, 9, 82, 10]
merge_sort(my_list)
print("Danh sách đã sắp xếp:")
for i in my_list:
print(i)
Kết quả:
Danh sách đã sắp xếp:
3
9
10
27
38
43
82
2.5. Heap Sort (Thuật toán sắp xếp vun đống)
Heap Sort (thuật toán sắp xếp vun đống) là một dạng của kỹ thuật sắp xếp chọn lọc. Heap sort liên quan đến việc phân tách dữ liệu đầu vào đã cho thành các phần tử được sắp xếp và không được sắp xếp. Thuật toán này lặp lại trên vùng chưa được sắp xếp sao cho ở mỗi vòng lặp, giá trị lớn nhất sẽ được đẩy vào vùng đã sắp xếp. Quá trình này được tiếp tục với tất cả các phần tử trong vùng chưa được sắp xếp.
Ví dụ về heap sort:
def heap_sort(Ordering, number, i):
largest = i
left= 2 * i + 1
right= 2 * i + 2
if left< number and Ordering[i] < Ordering[left]:
largest = left
if right< number and Ordering[largest] < Ordering[right]:
largest = right
if largest != i:
Ordering[i],Ordering[largest] = Ordering[largest],Ordering[i]
heap_sort(Ordering, number, largest)
def heapSort(Ordering):
number = len(Ordering)
for i in range(number, -1, -1):
heap_sort(Ordering, number, i)
for i in range(number-1, 0, -1):
Ordering[i], Ordering[0] = Ordering[0], Ordering[i]
heap_sort(Ordering, i, 0)
Ordering = [ 12, 11, 13, 5, 6, 7 ,56 ,45 ,67 ,78 ,34 ,4 ,33]
heapSort(Ordering)
number = len(Ordering)
print ( "Sorted Ordering value is" )
for i in range( number):
print ( " %d " %Ordering[i])
Kết quả:
Sorted Ordering value is
4
5
6
7
11
12
13
33
34
45
56
67
78
2.6. Radix Sort
Radix Sort (thuật toán sắp xếp cơ số) là một kỹ thuật sắp xếp mà không cần so sánh các phần tử được nhập vào. Điều này đạt được qua cách tạo một nhóm theo giá trị cơ số cho các phần tử có nhiều hơn một chữ số liên quan. Kỹ thuật này được áp dụng cho tất cả các chữ số trong phần tử.
Ví dụ thuật toán sắp xếp cơ số:
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# Đếm số lần xuất hiện của mỗi chữ số
for i in range(n):
index = (arr[i] // exp)
count[index % 10] += 1
# Tính toán vị trí chính xác của mỗi phần tử trong danh sách sắp xếp
for i in range(1, 10):
count[i] += count[i - 1]
# Sắp xếp danh sách dựa trên chữ số hiện tại
i = n - 1
while i >= 0:
index = (arr[i] // exp)
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copy danh sách đã sắp xếp vào danh sách ban đầu
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort(arr, exp)
exp *= 10
my_list = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(my_list)
print("Danh sách đã sắp xếp:")
print(my_list)
Kết quả:
Danh sách đã sắp xếp:
[2, 24, 45, 66, 75, 90, 170, 802]
3. Lời Kết
Với bài viết trên, chúng ta đã cùng tìm hiểu về thuật toán sắp xếp trong Python. Là một ngôn ngữ ổn định và linh hoạt, các thuật toán của Python thật sự hữu ích trong lĩnh vực khoa học máy tính. Hi vọng với những chia sẻ ở trên, bạn đã biết cách sử dụng các thuật toán này vào các dự án của mình.
Nếu bạn đang quan tâm đến học lập trình Python online thì hãy tham khảo ngay các khóa học lập trình tại ICANTECH nhé
Nguồn ảnh: ICANTECH.
Tags
Lập trình Python
