1. Giới thiệuĐôi khi dữ liệu chúng ta lưu trữ hoặc truy xuất trong một ứng dụng có thể có ít hoặc không có thứ tự. Chúng ta có thể phải sắp xếp lại dữ liệu để xử lý chính xác hoặc sử dụng nó một cách hiệu quả. Trong những năm qua, các nhà khoa học máy tính đã tạo ra nhiều thuật toán sắp xếp để tổ chức dữ liệu. Show
Bài viết này chúng ta sẽ xem xét các thuật toán sắp xếp phổ biến, chúng ta chắc cũng đã quen với những thuật toán sắp xếp khi còn ngồi trên ghế nhà trường, cùng hiểu cách chúng hoạt động và mã hóa chúng trong Python. Chúng tôi cũng sẽ so sánh cách sắp xếp nào nhanh hơn các items trong một list. Để đơn giản, việc triển khai thuật toán sẽ sắp xếp danh sách các số theo thứ tự tăng dần. Chúng ta có những thuật toán sắp xếp phổ biến sau:
2. Bubble SortThuật toán sắp xếp đơn giản này lặp lại qua một danh sách, so sánh các phần tử theo cặp và hoán đổi chúng cho đến khi các phần tử lớn hơn "nổi bong bóng" đến cuối danh sách và các phần tử nhỏ hơn nằm ở "dưới cùng". giải thíchChúng ta bắt đầu bằng cách so sánh hai elements đầu tiên của danh sách. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng ta hoán đổi chúng. Nếu họ đã theo thứ tự, chúng ta giữ nguyên. Sau đó chúng tôi chuyển sang cặp phần tử tiếp theo, so sánh giá trị của chúng và trao đổi khi cần thiết. Quá trình này tiếp tục đến cặp mục cuối cùng trong danh sách. Khi đến cuối danh sách, nó lặp lại quy trình này cho mọi mục. Mặc dù, điều này là không hiệu quả cao. Điều gì nếu chỉ một hoán đổi duy nhất cần phải được thực hiện trong mảng? Tại sao chúng ta vẫn lặp đi lặp lại ^2 lần, mặc dù nó đã được sắp xếp? Rõ ràng, để tối ưu hóa thuật toán, chúng ta cần dừng nó khi sắp xếp xong. Làm thế nào chúng ta biết rằng chúng ta đã sắp xếp xong? Nếu các mục theo thứ tự thì chúng ta sẽ không phải tráo đổi các items. Vì vậy, bất cứ khi nào chúng ta hoán đổi giá trị, chúng ta đặt flag thành True để lặp lại quá trình sắp xếp. Nếu không có swapped xảy ra, flag sẽ vẫn là Sai và thuật toán sẽ dừng lại.
Thuật toán chạy trong một vòng lặp while, chỉ phá vỡ khi không có mục nào được hoán đổi. Chúng ta đã đặt swapped thành True ngay từ đầu để đảm bảo thuật toán chạy ít nhất một lần. Độ phức tạp thời gianTrong trường hợp xấu nhất (khi danh sách theo thứ tự ngược lại), thuật toán này sẽ phải hoán đổi mọi item của mảng. flag swapper của chúng ta sẽ được đặt thành True trên mỗi lần lặp. Do đó, nếu chúng ta có n phần tử trong danh sách của mình, chúng ta sẽ có n lần lặp cho mỗi mục - do đó độ phức tạp thời gian của Bubble Sort là O (n ^ 2). 3. Selection SortThuật toán này phân chia danh sách thành hai phần: được sắp xếp và chưa được sắp xếp. Chúng ta liên tục xóa phần tử nhỏ nhất của phân đoạn chưa sắp xếp của danh sách và nối nó vào phân đoạn đã sắp xếp. giải thíchChúng ta bắt đầu bằng cách so sánh hai elements đầu tiên của danh sách. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng ta hoán đổi chúng. Nếu họ đã theo thứ tự, chúng ta giữ nguyên. Sau đó chúng tôi chuyển sang cặp phần tử tiếp theo, so sánh giá trị của chúng và trao đổi khi cần thiết. Quá trình này tiếp tục đến cặp mục cuối cùng trong danh sách.
Khi đến cuối danh sách, nó lặp lại quy trình này cho mọi mục. Mặc dù, điều này là không hiệu quả cao. Điều gì nếu chỉ một hoán đổi duy nhất cần phải được thực hiện trong mảng? Tại sao chúng ta vẫn lặp đi lặp lại ^2 lần, mặc dù nó đã được sắp xếp? Rõ ràng, để tối ưu hóa thuật toán, chúng ta cần dừng nó khi sắp xếp xong. Độ phức tạp thời gianTrong trường hợp xấu nhất (khi danh sách theo thứ tự ngược lại), thuật toán này sẽ phải hoán đổi mọi item của mảng. flag swapper của chúng ta sẽ được đặt thành True trên mỗi lần lặp. Do đó, nếu chúng ta có n phần tử trong danh sách của mình, chúng ta sẽ có n lần lặp cho mỗi mục - do đó độ phức tạp thời gian của Bubble Sort là O (n ^ 2). 3. Selection Sort Thuật toán này phân chia danh sách thành hai phần: được sắp xếp và chưa được sắp xếp. Chúng ta liên tục xóa phần tử nhỏ nhất của phân đoạn chưa sắp xếp của danh sách và nối nó vào phân đoạn đã sắp xếp.Trong thực tế, chúng ta không cần tạo một danh sách mới cho các phần tử được sắp xếp, những gì chúng ta làm là coi phần ngoài cùng bên trái của danh sách là phân đoạn được sắp xếp. Sau đó chúng ta tìm kiếm phần tử nhỏ nhất trong toàn bộ danh sách đã cho và hoán đổi nó với phần tử đầu tiên. giải thíchChúng ta bắt đầu bằng cách so sánh hai elements đầu tiên của danh sách. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng ta hoán đổi chúng. Nếu họ đã theo thứ tự, chúng ta giữ nguyên. Sau đó chúng tôi chuyển sang cặp phần tử tiếp theo, so sánh giá trị của chúng và trao đổi khi cần thiết. Quá trình này tiếp tục đến cặp mục cuối cùng trong danh sách. Khi đến cuối danh sách, nó lặp lại quy trình này cho mọi mục. Mặc dù, điều này là không hiệu quả cao. Điều gì nếu chỉ một hoán đổi duy nhất cần phải được thực hiện trong mảng? Tại sao chúng ta vẫn lặp đi lặp lại ^2 lần, mặc dù nó đã được sắp xếp? Rõ ràng, để tối ưu hóa thuật toán, chúng ta cần dừng nó khi sắp xếp xong.
Độ phức tạp thời gianTrong trường hợp xấu nhất (khi danh sách theo thứ tự ngược lại), thuật toán này sẽ phải hoán đổi mọi item của mảng. flag swapper của chúng ta sẽ được đặt thành True trên mỗi lần lặp. Do đó, nếu chúng ta có n phần tử trong danh sách của mình, chúng ta sẽ có n lần lặp cho mỗi mục - do đó độ phức tạp thời gian của Bubble Sort là O (n ^ 2). Trong trường hợp xấu nhất, vòng lặp for bên trong sẽ hoán đổi một lần, sau đó hoán đổi hai lần và cứ thế. Số lượng giao dịch hoán đổi sau đó sẽ là 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1), điều này mang lại cho Sắp xếp chèn một độ phức tạp thời gian của O (n ^ 2). 5. Heap SortThuật toán sắp xếp phổ biến này, như sắp xếp Chèn và Chọn, phân đoạn danh sách thành các phần được sắp xếp và chưa sắp xếp. Nó chuyển đổi phân đoạn chưa sắp xếp của danh sách thành cấu trúc dữ liệu Heap, để chúng ta có thể xác định hiệu quả phần tử lớn nhất. giải thíchChúng ta bắt đầu bằng cách chuyển đổi danh sách thành Max Heap - Cây nhị phân trong đó phần tử lớn nhất là nút gốc. Sau đó chúng tôi đặt mục đó vào cuối danh sách. Sau đó, chúng ta xây dựng lại Heap Max của chúng ta hiện có một giá trị nhỏ hơn, đặt giá trị lớn nhất mới trước mục cuối cùng của danh sách. Chúng tôi lặp lại quá trình xây dựng heap này cho đến khi tất cả các nút được loại bỏ.
Độ phức tạp thời gianTrước tiên chúng ta hãy xem xét độ phức tạp thời gian của hàm heapify. Trong trường hợp xấu nhất, phần tử lớn nhất không bao giờ là phần tử gốc, điều này gây ra một lệnh gọi đệ quy để heapify. Trong khi các cuộc gọi đệ quy có vẻ expensive, hãy nhớ rằng chúng ta đang làm việc với cây nhị phân. Hình dung một cây nhị phân có 3 phần tử, nó có chiều cao là 2. Bây giờ hãy hình dung một cây nhị phân có 7 phần tử, nó có chiều cao là 3. Cây phát triển logarit theo n. Hàm heapify đi ngang qua cây đó trong thời gian O (log (n)). Hàm heap_sort lặp lại qua mảng n lần. Do đó, độ phức tạp thời gian tổng thể của thuật toán Heap Sort là O (nlog (n)). 6. Merge SortThuật toán phân chia và trị này chia một danh sách thành một nửa và tiếp tục chia danh sách cho 2 cho đến khi nó chỉ có các phần tử số ít. Các phần tử liền kề trở thành các cặp được sắp xếp, sau đó các cặp được sắp xếp cũng được merge và sắp xếp với các cặp khác. Quá trình này tiếp tục cho đến khi chúng ta nhận được một danh sách được sắp xếp với tất cả các yếu tố của danh sách đầu vào chưa được sắp xếp. giải thíchChúng ta bắt đầu bằng cách chuyển đổi danh sách thành Max Heap - Cây nhị phân trong đó phần tử lớn nhất là nút gốc. Sau đó chúng tôi đặt mục đó vào cuối danh sách. Sau đó, chúng ta xây dựng lại Heap Max của chúng ta hiện có một giá trị nhỏ hơn, đặt giá trị lớn nhất mới trước mục cuối cùng của danh sách. Chúng tôi lặp lại quá trình xây dựng heap này cho đến khi tất cả các nút được loại bỏ. Độ phức tạp thời gian Trước tiên chúng ta hãy xem xét độ phức tạp thời gian của hàm heapify. Trong trường hợp xấu nhất, phần tử lớn nhất không bao giờ là phần tử gốc, điều này gây ra một lệnh gọi đệ quy để heapify. Trong khi các cuộc gọi đệ quy có vẻ expensive, hãy nhớ rằng chúng ta đang làm việc với cây nhị phân.
Hình dung một cây nhị phân có 3 phần tử, nó có chiều cao là 2. Bây giờ hãy hình dung một cây nhị phân có 7 phần tử, nó có chiều cao là 3. Cây phát triển logarit theo n. Hàm heapify đi ngang qua cây đó trong thời gian O (log (n)). Độ phức tạp thời gianTrước tiên chúng ta hãy xem xét độ phức tạp thời gian của hàm heapify. Trong trường hợp xấu nhất, phần tử lớn nhất không bao giờ là phần tử gốc, điều này gây ra một lệnh gọi đệ quy để heapify. Trong khi các cuộc gọi đệ quy có vẻ expensive, hãy nhớ rằng chúng ta đang làm việc với cây nhị phân. Hình dung một cây nhị phân có 3 phần tử, nó có chiều cao là 2. Bây giờ hãy hình dung một cây nhị phân có 7 phần tử, nó có chiều cao là 3. Cây phát triển logarit theo n. Hàm heapify đi ngang qua cây đó trong thời gian O (log (n)). Hàm heap_sort lặp lại qua mảng n lần. Do đó, độ phức tạp thời gian tổng thể của thuật toán Heap Sort là O (nlog (n)).6. Merge Sort Thuật toán phân chia và trị này chia một danh sách thành một nửa và tiếp tục chia danh sách cho 2 cho đến khi nó chỉ có các phần tử số ít. Các phần tử liền kề trở thành các cặp được sắp xếp, sau đó các cặp được sắp xếp cũng được merge và sắp xếp với các cặp khác. Quá trình này tiếp tục cho đến khi chúng ta nhận được một danh sách được sắp xếp với tất cả các yếu tố của danh sách đầu vào chưa được sắp xếp.Chúng ta đệ quy chia danh sách thành một nửa cho đến khi chúng ta có danh sách với kích thước = một. Sau đó chúng ta merge từng nửa được tách ra, sắp xếp chúng trong quá trình.
Độ phức tạp thời gianTrước tiên chúng ta hãy xem xét độ phức tạp thời gian của hàm heapify. Trong trường hợp xấu nhất, phần tử lớn nhất không bao giờ là phần tử gốc, điều này gây ra một lệnh gọi đệ quy để heapify. Trong khi các cuộc gọi đệ quy có vẻ expensive, hãy nhớ rằng chúng ta đang làm việc với cây nhị phân. Hình dung một cây nhị phân có 3 phần tử, nó có chiều cao là 2. Bây giờ hãy hình dung một cây nhị phân có 7 phần tử, nó có chiều cao là 3. Cây phát triển logarit theo n. Hàm heapify đi ngang qua cây đó trong thời gian O (log (n)). Với một trục tốt, chức năng Quick Sort sẽ phân vùng mảng thành một nửa, phát triển logarit với n. Do đó, độ phức tạp thời gian trung bình của thuật toán Quick Sort là O (nlog (n)) 8 . Các hàm sắp xếp tích hợp của PythonMặc dù có ích khi hiểu các thuật toán sắp xếp này, trong hầu hết các dự án Python, bạn có thể sẽ sử dụng các hàm sắp xếp đã được cung cấp trong ngôn ngữ. Chúng ta có thể thay đổi danh sách của mình để sắp xếp nội dung bằng phương thức sort ():
Hoặc chúng ta có thể sử dụng hàm sorted () để tạo danh sách được sắp xếp mới:
Cả hai đều sắp xếp theo thứ tự tăng dần, nhưng bạn có thể dễ dàng sắp xếp theo thứ tự giảm dần bằng cách đặt flag đảo ngược thành True:
Không giống như các hàm thuật toán sắp xếp mà chúng ta đã tạo, cả hai hàm này có thể sắp xếp danh sách các bộ dữ liệu và các lớp. Hàm sort () có thể sắp xếp bất kỳ đối tượng lặp nào, bao gồm - danh sách, chuỗi, bộ dữ liệu, từ điển, bộ và trình lặp tùy chỉnh mà bạn có thể tạo. Các hàm sắp xếp này thực hiện thuật toán Tim Sort , một thuật toán được lấy cảm hứng từ Merge Sort and Insertion Sort. 9 . So sánh tốc độĐể có được ý tưởng về việc chúng thực hiện nhanh như thế nào, chúng tôi tạo ra một danh sách 5000 số từ 0 đến 1000. Sau đó chúng tôi sẽ mất bao lâu để mỗi thuật toán hoàn thành. Điều này được lặp lại 10 lần để chúng ta có thể thiết lập một mô hình hiệu suất đáng tin cậy hơn. Bạn sẽ nhận được các giá trị khác nhau nếu bạn tự thiết lập thử nghiệm, nhưng các mẫu được quan sát phải giống hoặc tương tự nhau. Bubble Sort là trình diễn chậm nhất trong tất cả các thuật toán. Mặc dù nó hữu ích như là một giới thiệu về sắp xếp và thuật toán, nó không phù hợp để sử dụng thực tế. Bạn sẽ nhận được các giá trị khác nhau nếu bạn tự thiết lập thử nghiệm, nhưng các mẫu được quan sát phải giống hoặc tương tự nhau. Bubble Sort là trình diễn chậm nhất trong tất cả các thuật toán. Mặc dù nó hữu ích như là một giới thiệu về sắp xếp và thuật toán, nó không phù hợp để sử dụng thực tế.Chúng tôi cũng nhận thấy rằng Quick Sort rất nhanh, nhanh gần gấp đôi so với merge sort và nó sẽ không cần nhiều không gian để chạy. Hãy nhớ rằng phân vùng của chúng ta dựa trên yếu tố giữa của danh sách, các phân vùng khác nhau có thể có kết quả khác nhau. Vì Insertion Sort thực hiện so sánh ít hơn nhiều so với Selection Sort, việc triển khai thường nhanh hơn nhưng trong các lần chạy này, Selection Sort nhanh hơn một chút. Insertion Sort thực hiện nhiều hoán đổi hơn so với Selection Sort. Nếu các giá trị hoán đổi chiếm nhiều thời gian hơn so với so sánh các giá trị, thì kết quả "trái ngược" này sẽ hợp lý. Hãy chú ý đến môi trường khi chọn thuật toán sắp xếp phù hợp nhất dành cho bạn, vì nó sẽ ảnh hưởng đến hiệu suất. nguồn : https://stackabuse.com/sorting-algorithms-in-python/ |