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
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ếp
Hiệ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ếp
Thuậ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 Python
Cú 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
- Trường hợp xấu nhất. Thời gian tối đa mà máy tính thực hiện để chạy chương trình
- trường hợp trung bình. Thời gian giữa mức tối thiểu và tối đa của máy tính để chạy chương trình
- Trường hợp tốt nhất. Thời gian tối thiểu để máy tính chạy chương trình. Đó là trường hợp tốt nhất về độ phức tạp của thời gian
Ký hiệu phức tạp
Ký 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 Python
Sắp xếp bong bóng
Sắ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 tôi được cung cấp một mảng có các phần tử “ 10, 40, 7, 3, 15 ”. Bây giờ, chúng ta cần sắp xếp mảng này theo thứ tự tăng dần bằng cách sử dụng kỹ thuật Bubble sort trong Python
- Bước đầu tiên là sắp xếp mảng theo thứ tự nhất định
- Trong “ Lặp lại 1 ”, chúng ta đang so sánh từng phần tử đầu tiên của một mảng với các phần tử khác
- Các mũi tên màu đỏ đang mô tả việc so sánh các phần tử đầu tiên với các phần tử khác của một mảng
- Nếu bạn nhận thấy “10” nhỏ hơn “40” thì nó giữ nguyên vị trí nhưng phần tử tiếp theo “7” nhỏ hơn “10”. Do đó nó được thay thế và đứng ở vị trí đầu tiên
- Quá trình trên sẽ được thực hiện lặp đi lặp lại để sắp xếp các phần tử
- Trong “Lặp lại 2”, phần tử thứ hai được so sánh với các phần tử khác của một mảng
- Nếu phần tử được so sánh nhỏ thì nó sẽ bị thay thế, nếu không nó sẽ ở nguyên vị trí cũ
- Trong “ Lặp lại 3 “, phần tử thứ ba được so sánh với các phần tử khác của một mảng
- Trong " Lặp lại 4 ", phần tử cuối cùng thứ hai được so sánh với các phần tử khác của một mảng
- Ở bước này mảng được sắp xếp theo thứ tự tăng dần
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
- Trường hợp xấu nhất. Độ phức tạp thời gian tồi tệ nhất cho sắp xếp bong bóng là O[n2]
- trường hợp trung bình. Độ phức tạp thời gian trung bình cho sắp xếp bong bóng là O[n2]
- Trường hợp tốt nhất. Độ phức tạp thời gian tốt nhất để sắp xếp bong bóng là O[n]
Thuận lợi
- Nó chủ yếu được sử dụng và dễ thực hiện
- Chúng tôi có thể trao đổi các phần tử dữ liệu mà không cần sử dụng dung lượng lưu trữ ngắn hạn
- Nó đòi hỏi ít không gian hơn
Nhược điểm
- Nó không hoạt động tốt khi xử lý một số lượng lớn các phần tử dữ liệu lớn
- Nó cần n2 bước cho mỗi “n” số phần tử dữ liệu để được sắp xếp
- Nó không thực sự tốt cho các ứng dụng trong thế giới thực
Sắp xếp chèn
Sắ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 tôi được cung cấp một mảng có các phần tử “ 100, 50, 30, 40, 10 ”
- Đầu tiên, chúng tôi sắp xếp các mảng và bắt đầu so sánh nó
- Trong bước đầu tiên “100” được so sánh với phần tử thứ hai “50”. “50” được hoán đổi với “100” vì nó lớn hơn
- Trong bước thứ hai, một lần nữa phần tử thứ hai “ 100 ” được so sánh với phần tử thứ ba “ 30 ” và được đổi chỗ
- Bây giờ, nếu bạn nhận thấy “30” đứng đầu vì nó lại nhỏ hơn “50”
- Việc so sánh sẽ xảy ra cho đến phần tử cuối cùng của một mảng và khi kết thúc, chúng ta sẽ nhận được dữ liệu đã được sắp xếp
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
- Trường hợp xấu nhất. Độ phức tạp thời gian tồi tệ nhất đối với sắp xếp Chèn là O[n2]
- trường hợp trung bình. Độ phức tạp thời gian trung bình cho sắp xếp Chèn là O[n2]
- Trường hợp tốt nhất. Độ phức tạp thời gian tốt nhất cho sắp xếp Chèn là O[n]
Thuận lợi
- Nó đơn giản và dễ thực hiện
- Nó hoạt động tốt trong khi xử lý một số lượng nhỏ các phần tử dữ liệu
- Nó không cần thêm không gian để thực hiện
Nhược điểm
- Sẽ không hữu ích khi sắp xếp một số lượng lớn các phần tử dữ liệu
- Khi so sánh với các kỹ thuật sắp xếp khác, nó không hoạt động tốt
Hợp nhất sắp xếp
Phươ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 tôi được cung cấp một mảng “ 7, 3, 40, 10, 20, 15, 6, 5”. Mảng có 7 phần tử. Nếu chúng ta chia nó thành một nửa [ 0 + 7 / 2 = 3 ]
- Trong bước thứ hai, bạn sẽ thấy rằng các yếu tố được chia thành hai phần. Mỗi cái có 4 yếu tố trong đó
- Hơn nữa, các phần tử lại được chia và có 2 phần tử mỗi phần
- Quá trình này sẽ tiếp tục cho đến khi chỉ còn một phần tử trong một mảng. Tham khảo bước không. 4 trong hình
- Bây giờ, chúng ta sẽ sắp xếp các phần tử và bắt đầu nối chúng lại như đã chia
- Ở bước không. 5 nếu bạn để ý 7 lớn hơn 3 thì ta sẽ đổi và ghép ở bước sau và ngược lại
- Cuối cùng, bạn sẽ nhận thấy rằng mảng của chúng ta đang được sắp xếp theo thứ tự tăng dần
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
- Trường hợp xấu nhất. Độ phức tạp thời gian tồi tệ nhất đối với sắp xếp hợp nhất là O[n log[n]]
- trường hợp trung bình. Độ phức tạp thời gian trung bình để sắp xếp hợp nhất là O[n log[n]]
- Trường hợp tốt nhất. Độ phức tạp thời gian tốt nhất để sắp xếp hợp nhất là O[n log[n]]
Thuận lợi
- Kích thước tệp không quan trọng đối với kỹ thuật sắp xếp này
- Kỹ thuật này phù hợp với dữ liệu thường được truy cập theo trình tự. Ví dụ: danh sách được liên kết, ổ băng từ, v.v.
Nhược điểm
- Nó đòi hỏi nhiều không gian hơn khi so sánh với các kỹ thuật sắp xếp khác
- Nó tương đối kém hiệu quả hơn những cái khác
Sắp xếp nhanh chóng
Sắ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 tôi được cung cấp một mảng có các phần tử “ 1,8,3,9,4,5,7 ”
- Giả sử “7” là phần tử thí điểm
- Bây giờ chúng ta sẽ chia mảng theo cách mà phía bên trái chứa các phần tử nhỏ hơn phần tử trục “ 7 ” và phía bên phải chứa các phần tử lớn hơn phần tử trục “ 7 ”
- Bây giờ chúng ta có hai mảng “1,3,4,5” và “8, 9”
- Một lần nữa, chúng ta phải chia cả hai mảng giống như chúng ta đã làm ở trên. Sự khác biệt duy nhất là các yếu tố trục được thay đổi
- Chúng ta cần chia mảng cho đến khi lấy được phần tử duy nhất trong mảng
- Cuối cùng, thu thập tất cả các phần tử trục theo thứ tự từ trái sang phải và bạn sẽ nhận được mảng đã sắp xếp
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 ]