Thuật toán sắp xếp trong Python
Có nhiều thuật toán sắp xếp khác nhau có thể được sử dụng để hoàn thành thao tác này. Và, chúng ta có thể sử dụng bất kỳ thuật toán nào dựa trên yêu cầu Show
Các thuật toán sắp xếp khác nhauĐộ phức tạp của thuật toán sắp xếpHiệu quả của bất kỳ thuật toán sắp xếp nào được xác định bởi độ phức tạp thời gian và độ phức tạp không gian của thuật toán 1. Thời gian phức tạp. Độ phức tạp về thời gian đề cập đến thời gian mà một thuật toán thực hiện để hoàn thành việc thực thi nó đối với kích thước của đầu vào. Nó có thể được đại diện trong các hình thức khác nhau 2. Độ phức tạp không gian. Độ phức tạp của không gian đề cập đến tổng dung lượng bộ nhớ được sử dụng bởi thuật toán để thực thi hoàn chỉnh. Nó bao gồm cả bộ nhớ phụ và đầu vào Bộ nhớ phụ là không gian bổ sung chiếm bởi thuật toán ngoài dữ liệu đầu vào. Thông thường, bộ nhớ phụ được xem xét để tính toán độ phức tạp không gian của thuật toán Hãy xem phân tích độ phức tạp của các thuật toán sắp xếp khác nhau Thuật toán sắp xếp Độ phức tạp của thời gian - Độ phức tạp của thời gian tốt nhất - Độ phức tạp của thời gian tồi tệ nhất - Độ phức tạp của thời gian trung bình Tính ổn định của thuật toán sắp xếpThuật toán sắp xếp được coi là ổn định nếu hai hoặc nhiều mục có cùng giá trị duy trì cùng một vị trí tương đối ngay cả sau khi sắp xếp Ví dụ như hình bên dưới có 2 mục có cùng giá trị 3. Thuật toán sắp xếp không ổn định cho phép hai khả năng trong đó hai vị trí của 3 có thể được duy trì hoặc không Tuy nhiên, sau thuật toán sắp xếp ổn định, luôn có một khả năng các vị trí được giữ nguyên như trong mảng ban đầu Đây là một bảng cho thấy sự ổn định của các thuật toán sắp xếp khác nhau Thuật toán sắp xếp bảngSắp xếp bong bóngCóLựa chọn Sắp xếpKhôngChèn Sắp xếpCóHợp nhấtSắp xếpCóSắp xếp nhanhKhôngĐếm Sắp xếpCóSắp xếp radixCóSắp xếp nhómCóSắp xếp theo đốngKhôngSắp xếp theo vỏKhông Timsort là một thuật toán sắp xếp lai, bắt nguồn từ sắp xếp hợp nhất và sắp xếp chèn, được thiết kế để hoạt động tốt trên nhiều loại dữ liệu trong thế giới thực. Nó được phát minh bởi Tim Peters vào năm 2002 để sử dụng trong ngôn ngữ lập trình Python. Thuật toán tìm các tập hợp con của dữ liệu đã được sắp xếp và sử dụng các tập hợp con đó để sắp xếp dữ liệu hiệu quả hơn. Điều này được thực hiện bằng cách hợp nhất một tập hợp con đã xác định, được gọi là một lần chạy, với các lần chạy hiện có cho đến khi đáp ứng một số tiêu chí nhất định. Timsort là thuật toán sắp xếp tiêu chuẩn của Python kể từ phiên bản 2. 3. Nó hiện cũng được sử dụng để sắp xếp các mảng trong Java SE 7 và trên nền tảng Android Tìm hiểu cách sử dụng hàm Sắp xếp trong Python để sắp xếp danh sách, mảng, từ điển, v.v. bằng các phương pháp và thuật toán sắp xếp khác nhau trong Python Sắp xếp là một kỹ thuật được sử dụng để sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần Hầu hết thời gian, dữ liệu của các dự án lớn không được sắp xếp theo đúng thứ tự và điều này tạo ra sự cố khi truy cập và tìm nạp dữ liệu cần thiết một cách hiệu quả Kỹ thuật sắp xếp được sử dụng để giải quyết vấn đề này. Python cung cấp nhiều kỹ thuật sắp xếp khác nhau ví dụ: Sắp xếp bong bóng, Sắp xếp chèn, Sắp xếp hợp nhất, Sắp xếp nhanh, v.v. Trong hướng dẫn này, chúng ta sẽ hiểu cách sắp xếp hoạt động trong Python bằng cách sử dụng các thuật toán khác nhau => Hãy xem Hướng dẫn dành cho người mới bắt đầu Python tại đây Bạn sẽ học được gì Sắp xếp PythonCú pháp sắp xếp PythonĐể thực hiện sắp xếp, Python cung cấp sẵn hàm i. e. chức năng “sắp xếp()”. Nó được sử dụng để sắp xếp các phần tử dữ liệu của một danh sách theo thứ tự tăng dần hoặc giảm dần Hãy hiểu khái niệm này với một ví dụ ví dụ 1 ``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ``` đầu ra Trong ví dụ này, danh sách không có thứ tự đã cho được sắp xếp theo thứ tự tăng dần bằng cách sử dụng hàm “sort( )” ví dụ 2 ``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ``` đầu ra Trong ví dụ trên, danh sách không có thứ tự đã cho được sắp xếp theo thứ tự ngược lại bằng cách sử dụng hàm “sort(reverse = True)” Độ phức tạp về thời gian của thuật toán sắp xếpĐộ phức tạp về thời gian là lượng thời gian mà máy tính sử dụng để chạy một thuật toán cụ thể. Nó có ba loại trường hợp phức tạp về thời gian
Ký hiệu phức tạpKý hiệu Big Oh, O. Ký hiệu big oh là cách chính thức để truyền đạt giới hạn trên của thời gian chạy của các thuật toán. Nó được sử dụng để đo độ phức tạp thời gian trong trường hợp xấu nhất hoặc chúng tôi nói lượng thời gian lớn nhất mà thuật toán cần để hoàn thành Ký hiệu omega lớn, Ký hiệu Theta, Phương pháp sắp xếp trong PythonSắp xếp bong bóngSắp xếp bong bóng là cách đơn giản nhất để sắp xếp dữ liệu sử dụng kỹ thuật brute force. Nó sẽ lặp lại từng phần tử dữ liệu và so sánh nó với các phần tử khác để cung cấp cho người dùng dữ liệu đã được sắp xếp Hãy để chúng tôi lấy một ví dụ để hiểu kỹ thuật này
Chương trình sắp xếp bong bóng ``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ``` đầu ra Độ phức tạp về thời gian của sắp xếp bong bóng
Thuận lợi
Nhược điểm
Sắp xếp chènSắp xếp chèn là một kỹ thuật sắp xếp dễ dàng và đơn giản, hoạt động tương tự như sắp xếp các quân bài. Chèn sắp xếp sắp xếp các phần tử bằng cách so sánh từng phần tử với nhau. Các phần tử được chọn và hoán đổi với phần tử khác nếu phần tử này lớn hơn hoặc nhỏ hơn phần tử kia Hãy lấy một ví dụ
Chương trình sắp xếp chèn ``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value < array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ``` đầu ra Độ phức tạp về thời gian của sắp xếp chèn
Thuận lợi
Nhược điểm
Hợp nhất sắp xếpPhương pháp sắp xếp này sử dụng phương pháp chia để trị để sắp xếp các phần tử theo một thứ tự cụ thể. Trong khi sắp xếp với sự trợ giúp của sắp xếp hợp nhất, các phần tử được chia thành hai nửa và sau đó, chúng được sắp xếp. Sau khi sắp xếp tất cả các nửa, một lần nữa các phần tử lại được nối với nhau để tạo thành một trật tự hoàn hảo Hãy lấy một ví dụ để hiểu kỹ thuật này
Chương trình sắp xếp hợp nhất ``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i], end=" ") print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ``` đầu ra Độ phức tạp về thời gian của sắp xếp hợp nhất
Thuận lợi
Nhược điểm
Sắp xếp nhanh chóngSắp xếp nhanh lại sử dụng phương thức chia để trị để sắp xếp các phần tử của Danh sách hoặc mảng. Nó nhắm mục tiêu các phần tử trục và sắp xếp các phần tử theo phần tử trục đã chọn Ví dụ
Chương trình sắp xếp nhanh ``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] <= pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest < highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ``` đầu ra Độ phức tạp về thời gian của sắp xếp nhanh
Thuận lợi
Nhược điểm
sắp xếp đốngSắp xếp đống là phiên bản nâng cao của cây tìm kiếm nhị phân. Trong heap sort, phần tử lớn nhất của mảng luôn được đặt trên gốc của cây rồi so sánh gốc với các nút lá Ví dụ
Chương trình sắp xếp Heap ``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[ larger_element ] < arr[ left ]: larger_element = left if right < n and arr[ larger_element ] < arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ``` đầu ra Độ phức tạp về thời gian của sắp xếp Heap
Thuận lợi
Nhược điểm
So sánh giữa các kỹ thuật sắp xếpPhương pháp sắp xếp Độ phức tạp về thời gian của trường hợp tốt nhấtĐộ phức tạp về thời gian của trường hợp trung bìnhĐộ phức tạp về thời gian của trường hợp xấu nhấtĐộ phức tạp về không gianTính ổn địnhTrong - vị tríSắp xếp bong bóngO(n)O(n2)O(n2)O(1)CóCóSắp xếp chènO(n)O(n2)O(n2)O(1)CóCóSắp xếp nhanhO( Trong bảng so sánh trên “O” là ký hiệu Big Oh được giải thích ở trên trong khi “n” và “N” có nghĩa là kích thước của đầu vào Các câu hỏi thường gặpQ #1) Sort() trong Python là gì? Câu trả lời. Trong Python sort() là một hàm được sử dụng để sắp xếp các danh sách hoặc mảng theo một thứ tự cụ thể. Chức năng này giúp giảm bớt quá trình sắp xếp trong khi làm việc trên các dự án lớn. Nó rất hữu ích cho các nhà phát triển Q #2) Làm thế nào để bạn sắp xếp trong Python? Trả lời. Python cung cấp các kỹ thuật sắp xếp khác nhau được sử dụng để sắp xếp phần tử. Ví dụ: Sắp xếp nhanh, Sắp xếp hợp nhất, Sắp xếp nổi bọt, Sắp xếp chèn, v.v. Tất cả các kỹ thuật sắp xếp đều hiệu quả và dễ hiểu. Q #3) Python sort() hoạt động như thế nào? Câu trả lời. Hàm sort() lấy mảng đã cho làm đầu vào từ người dùng và sắp xếp nó theo một thứ tự cụ thể bằng thuật toán sắp xếp. Việc lựa chọn thuật toán phụ thuộc vào sự lựa chọn của người dùng. Người dùng có thể sử dụng Quick sort, Merge sort, Bubble sort, Insertion sort,… tùy theo nhu cầu của người dùng Phần kết luậnTrong hướng dẫn trên, chúng ta đã thảo luận về kỹ thuật sắp xếp trong Python cùng với các kỹ thuật sắp xếp chung
Chúng tôi đã tìm hiểu về sự phức tạp về thời gian cũng như ưu điểm và nhược điểm của chúng. Chúng tôi cũng so sánh tất cả các kỹ thuật trên sort() là gì và cho ví dụ?Sắp xếp là quá trình sắp xếp các phần tử từ một bộ sưu tập theo một số loại trật tự . Ví dụ: một danh sách các từ có thể được sắp xếp theo thứ tự bảng chữ cái hoặc theo độ dài. Danh sách các thành phố có thể được sắp xếp theo dân số, theo khu vực hoặc theo mã zip.
Thuật toán nào là tốt nhất để sắp xếp?Một số thuật toán sắp xếp phổ biến nhất là. . sắp xếp bong bóng Sắp xếp chèn Hợp nhất sắp xếp Sắp xếp nhanh chóng sắp xếp đống sắp xếp đếm sắp xếp cơ số sắp xếp xô Có bao nhiêu kỹ thuật sắp xếp trong Python?6 Loại Thuật Toán Sắp Xếp Sử Dụng Trong Python. tăng tốc
Timsort có nhanh hơn Quicksort không?Timsort (có nguồn gốc từ sắp xếp hợp nhất và sắp xếp chèn) được giới thiệu vào năm 2002 và mặc dù chậm hơn quicksort đối với dữ liệu ngẫu nhiên, Timsort hoạt động tốt hơn trên dữ liệu có thứ tự. Quadsort (derived from merge sort) was introduced in 2020 and is faster than quicksort for random data, and slightly faster than Timsort on ordered data. |