Tầm quan trọng của thuật toán sắp xếp trong Python
Bạn có biết rằng thuật toán sắp xếp trong Python có thể giúp bạn giải quyết nhiều vấn đề phức tạp một cách đơn giản? Đó là sự thật! Thuật toán sắp xếp có thể được sử dụng để:
- 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, bạn có thể sử dụng tính năng sắp xếp của Python để tiết kiệm thời gian và công sức.
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 về 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)
Thuật toán Bubble Sort (sắp xếp nổi bọt) là một trong những 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 này sẽ 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:
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 ("Các giá trị sau khi sắp xếp:") for i in range(len(array)): print("%d" %array[i])Kết quả sẽ là:
Các giá trị sau khi sắp xếp: 1 34 54 56 75 782.2 Selection Sort (Sắp xếp lựa chọn)
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. Thuật toán này 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à đặt 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ẽ được một tập hợp đã được sắp xếp hoàn chỉnh.
Dưới đây là một ví dụ về thuật toán Selection Sort:
def selection_sort(arr): n = len(arr) for i in range(n): min_index = i for j in range(i+1, n): if arr[j] arr[min_index]: min_index = j 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ả sẽ là:
Danh sách đã sắp xếp: 11 12 22 25 642.3 Insertion Sort (Sắp xếp chèn)
Trong thuật toán Insertion Sort (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 đã sắp xếp với một phần tử tại một thời điểm. Các phần tử của mảng được so sánh 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ự.
Dưới đây là một ví dụ về thuật toán 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) print("Các giá trị sau khi sắp xếp:") for i in range(len(array)): print("% d" % array[i])Kết quả sẽ là:
Các giá trị sau khi sắp xếp: 1 34 54 56 75 782.4 Merge Sort (Sắp xếp hợp nhất)
Merge Sort (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 chia thành hai nửa, mỗi 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 để thực hiện quá trình hợp nhất.
Dưới đây là một ví dụ về thuật toán Merge Sort:
def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half) merge_sort(right_half) i = j = k = 0 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ả sẽ là:
Danh sách đã sắp xếp: 3 9 10 27 38 43 822.5 Heap Sort (Sắp xếp vun đống)
Heap Sort (sắp xếp vun đống) là một dạng của kỹ thuật sắp xếp chọn lọc. Thuật toán này liên quan đến việc chia dữ liệu đầu vào thành hai phần, một phần được sắp xếp và một phần không được sắp xếp. Quá trình này được 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.
Dưới đây là một 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 ( "Giá trị trong Ordering đã được sắp xếp theo thứ tự tăng dần:" ) for i in range( number): print ( " %d " %Ordering[i])Kết quả sẽ là:
Giá trị trong Ordering đã được sắp xếp theo thứ tự tăng dần: 4 5 6 7 11 12 13 33 34 45 56 67 782.6 Radix Sort (Sắp xếp cơ số)
Radix Sort (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ử. Điều này được thực hiện bằng cách tạo ra các nhóm dựa trên giá trị cơ số của các phần tử liên quan. Kỹ thuật này được áp dụng cho tất cả các chữ số trong phần tử.
Dưới đây là một ví dụ về Radix Sort:
def counting_sort(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 for i in range(n): index = (arr[i] // exp) count[index % 10] += 1 for i in range(1, 10): count[i] += count[i - 1] i = n - 1 while i >= 0: index = (arr[i] // exp) output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 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ả sẽ là:
Danh sách đã sắp xếp: [2, 24, 45, 66, 75, 90, 170, 802]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. Python, với tính ổn định và linh hoạt, các thuật toán của nó thực sự hữu ích cho việc phân tích dữ liệu và giải quyết các vấn đề trong lĩnh vực khoa học máy tính. Hi vọng rằng với những chia sẻ trên, bạn đã nắm bắt được cách sử dụng các thuật toán trong dự án của mình.
Nếu bạn đang quan tâm đến việc lập trình python online' class='hover-show-link replace-link-1794'> học lập trình python online , hãy tham khảo ngay các khóa học lập trình tại ICANTECH để bắt đầu hành trình của bạn.
Nguồn ảnh: ICANTECH.