Sắp xếp Lựa chọn là gì?
SẮP XẾP CHỌN là một thuật toán sắp xếp so sánh được sử dụng để sắp xếp một danh sách ngẫu nhiên các mục theo thứ tự tăng dần. Việc so sánh không đòi hỏi nhiều không gian thừa. Nó chỉ yêu cầu một không gian bộ nhớ bổ sung cho biến thời gian.
Đây được gọi là sắp xếp tại chỗ . Sắp xếp lựa chọn có độ phức tạp thời gian là O (n 2 ) trong đó n là tổng số mục trong danh sách. Độ phức tạp về thời gian đo số lần lặp cần thiết để sắp xếp danh sách. Danh sách được chia thành hai phân vùng: Danh sách đầu tiên chứa các mục được sắp xếp, trong khi danh sách thứ hai chứa các mục chưa được sắp xếp.
Theo mặc định, danh sách được sắp xếp trống và danh sách chưa được sắp xếp chứa tất cả các phần tử. Sau đó, danh sách chưa được sắp xếp sẽ được quét để tìm giá trị nhỏ nhất, giá trị này sau đó được đưa vào danh sách đã sắp xếp. Quá trình này được lặp lại cho đến khi tất cả các giá trị đã được so sánh và sắp xếp.
Trong hướng dẫn về Thuật toán này, bạn sẽ học:
- Sắp xếp Lựa chọn là gì?
- Sắp xếp lựa chọn hoạt động như thế nào?
- Định nghĩa vấn đề
- Giải pháp (Thuật toán)
- Đại diện trực quan
- Chương trình sắp xếp lựa chọn sử dụng Python 3
- Giải thích mã
- Sự phức tạp về thời gian của việc sắp xếp lựa chọn
- Khi nào sử dụng sắp xếp lựa chọn?
- Ưu điểm của Sắp xếp Lựa chọn
- Nhược điểm của Sắp xếp Lựa chọn
Sắp xếp lựa chọn hoạt động như thế nào?
Mục đầu tiên trong phân vùng chưa được sắp xếp được so sánh với tất cả các giá trị ở phía bên tay phải để kiểm tra xem nó có phải là giá trị nhỏ nhất hay không. Nếu nó không phải là giá trị nhỏ nhất, thì vị trí của nó sẽ được hoán đổi với giá trị nhỏ nhất.
Thí dụ:
- Ví dụ: nếu chỉ mục của giá trị nhỏ nhất là 3, thì giá trị của phần tử có chỉ số 3 được đặt ở chỉ mục 0 trong khi giá trị ở chỉ mục 0 được đặt ở chỉ số 3. Nếu phần tử đầu tiên trong phân vùng chưa được sắp xếp là giá trị nhỏ nhất, sau đó nó trả về vị trí của nó.
- Phần tử đã được xác định là giá trị nhỏ nhất sau đó được chuyển đến phân vùng ở phía bên trái, là danh sách đã được sắp xếp.
- Bên được phân vùng bây giờ có một phần tử, trong khi bên không được phân vùng có (n - 1) phần tử trong đó n là tổng số phần tử trong danh sách. Quá trình này được lặp đi lặp lại cho đến khi tất cả các mục đã được so sánh và sắp xếp dựa trên giá trị của chúng.
Định nghĩa vấn đề
Một danh sách các phần tử theo thứ tự ngẫu nhiên cần được sắp xếp theo thứ tự tăng dần. Hãy xem danh sách sau đây làm ví dụ.
[21,6,9,33,3]
Danh sách trên nên được sắp xếp để tạo ra các kết quả sau
[3,6,9,21,33]
Giải pháp (Thuật toán)
Bước 1) Lấy giá trị của n là tổng kích thước của mảng
Bước 2) Phân chia danh sách thành các phần được sắp xếp và không được sắp xếp. Phần được sắp xếp ban đầu trống trong khi phần chưa được sắp xếp chứa toàn bộ danh sách
Bước 3) Chọn giá trị nhỏ nhất từ phần chưa được phân vùng và đặt nó vào phần đã sắp xếp.
Bước 4) Lặp lại quy trình (n - 1) lần cho đến khi tất cả các phần tử trong danh sách đã được sắp xếp.
Đại diện trực quan
Đưa ra danh sách năm phần tử, các hình ảnh sau minh họa cách thuật toán sắp xếp lựa chọn lặp lại các giá trị khi sắp xếp chúng.
Hình ảnh sau đây cho thấy danh sách chưa được sắp xếp
Bước 1)
Giá trị đầu tiên 21 được so sánh với các giá trị còn lại để kiểm tra xem nó có phải là giá trị nhỏ nhất hay không.
3 là giá trị nhỏ nhất, vì vậy vị trí của 21 và 3 được đổi chỗ cho nhau. Các giá trị có nền màu xanh lá cây đại diện cho phân vùng được sắp xếp của danh sách.
Bước 2)
Giá trị 6 là phần tử đầu tiên trong phân vùng chưa được sắp xếp được so sánh với phần còn lại của các giá trị để tìm xem có tồn tại giá trị thấp hơn hay không
Giá trị 6 là giá trị nhỏ nhất nên nó giữ nguyên vị trí của nó.
Bước 3)
Phần tử đầu tiên của danh sách chưa được sắp xếp có giá trị là 9 được so sánh với các giá trị còn lại để kiểm tra xem nó có phải là giá trị nhỏ nhất hay không.
Giá trị 9 là giá trị nhỏ nhất, vì vậy nó duy trì vị trí của nó trong phân vùng đã sắp xếp.
Bước 4)
Giá trị 33 được so sánh với các giá trị còn lại.
Giá trị 21 thấp hơn 33, vì vậy các vị trí được hoán đổi để tạo ra danh sách mới ở trên.
Bước 5)
Chúng tôi chỉ còn lại một giá trị trong danh sách chưa được phân vùng. Do đó, nó đã được sắp xếp.
Danh sách cuối cùng giống như trong hình trên.
Chương trình sắp xếp lựa chọn sử dụng Python 3
Đoạn mã sau cho thấy việc triển khai sắp xếp lựa chọn bằng Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Chạy đoạn mã trên cho kết quả sau
[3, 6, 9, 21, 33]
Giải thích mã
Giải thích cho mã như sau
Đây là giải thích mã:
- Định nghĩa một hàm có tên là selectionSort
- Nhận tổng số phần tử trong danh sách. Chúng tôi cần điều này để xác định số lượng đường chuyền được thực hiện khi so sánh các giá trị.
- Vòng ngoài. Sử dụng vòng lặp để lặp qua các giá trị của danh sách. Số lần lặp là (n - 1). Giá trị của n là 5, do đó (5 - 1) cho chúng ta 4. Điều này có nghĩa là các bước lặp bên ngoài sẽ được thực hiện 4 lần. Trong mỗi lần lặp, giá trị của biến i được gán cho biến minValueIndex
- Vòng trong. Sử dụng vòng lặp để so sánh giá trị ngoài cùng bên trái với các giá trị khác ở phía bên phải. Tuy nhiên, giá trị của j không bắt đầu ở chỉ số 0. Nó bắt đầu ở (i + 1). Điều này loại trừ các giá trị đã được sắp xếp để chúng tôi tập trung vào các mục chưa được sắp xếp.
- Tìm giá trị nhỏ nhất trong danh sách chưa được sắp xếp và đặt nó vào vị trí thích hợp của nó
- Cập nhật giá trị của minValueIndex khi điều kiện hoán đổi là đúng
- So sánh các giá trị của số chỉ mục minValueIndex và i để xem chúng có bằng nhau không
- Giá trị ngoài cùng bên trái được lưu trữ trong một biến thời gian
- Giá trị thấp hơn từ phía bên phải sẽ chiếm vị trí đầu tiên
- Giá trị đã được lưu trữ trong giá trị tạm thời được lưu trữ ở vị trí đã được giữ trước đó bằng giá trị nhỏ nhất
- Trả về danh sách đã sắp xếp dưới dạng kết quả của hàm
- Tạo một danh sách có các số ngẫu nhiên
- In danh sách đã sắp xếp sau khi gọi hàm Sort lựa chọn chuyển vào el làm tham số.
Sự phức tạp về thời gian của việc sắp xếp lựa chọn
Độ phức tạp sắp xếp được sử dụng để biểu thị số lần thực hiện cần thiết để sắp xếp danh sách. Việc triển khai có hai vòng lặp.
Vòng lặp bên ngoài chọn từng giá trị một từ danh sách được thực hiện n lần với n là tổng số giá trị trong danh sách.
Vòng lặp bên trong, so sánh giá trị từ vòng lặp bên ngoài với các giá trị còn lại, cũng được thực hiện n lần với n là tổng số phần tử trong danh sách.
Do đó, số lần thực hiện là (n * n), cũng có thể được biểu thị bằng O (n 2 ).
Việc sắp xếp lựa chọn có ba loại phức tạp cụ thể là;
- Trường hợp tệ nhất - đây là nơi danh sách được cung cấp theo thứ tự giảm dần. Thuật toán thực hiện số lần thực thi tối đa được biểu thị bằng [Big-O] O (n 2 )
- Trường hợp tốt nhất - điều này xảy ra khi danh sách được cung cấp đã được sắp xếp. Thuật toán thực hiện số lần thực thi tối thiểu được biểu thị bằng [Big-Omega] Ω (n 2 )
- Trường hợp trung bình - điều này xảy ra khi danh sách theo thứ tự ngẫu nhiên. Độ phức tạp trung bình được biểu thị bằng [Big-theta] ⊝ (n 2 )
Sắp xếp lựa chọn có độ phức tạp không gian là O (1) vì nó yêu cầu một biến thời gian được sử dụng để hoán đổi các giá trị.
Khi nào sử dụng sắp xếp lựa chọn?
Loại lựa chọn được sử dụng tốt nhất khi bạn muốn:
- Bạn phải sắp xếp một danh sách nhỏ các mục theo thứ tự tăng dần
- Khi chi phí hoán đổi giá trị không đáng kể
- Nó cũng được sử dụng khi bạn cần đảm bảo rằng tất cả các giá trị trong danh sách đã được kiểm tra.
Ưu điểm của Sắp xếp Lựa chọn
Sau đây là những ưu điểm của phân loại lựa chọn
- Nó hoạt động rất tốt trên các danh sách nhỏ
- Nó là một thuật toán tại chỗ. Nó không yêu cầu nhiều không gian để phân loại. Chỉ cần thêm một khoảng trống để giữ biến thời gian.
- Nó hoạt động tốt trên các mục đã được sắp xếp.
Nhược điểm của Sắp xếp Lựa chọn
Sau đây là những nhược điểm của phân loại lựa chọn.
- Nó hoạt động kém khi làm việc trên các danh sách lớn.
- Số lần lặp được thực hiện trong quá trình sắp xếp là n bình phương, trong đó n là tổng số phần tử trong danh sách.
- Các thuật toán khác, chẳng hạn như quicksort, có hiệu suất tốt hơn so với sắp xếp lựa chọn.
Tóm lược:
- Sắp xếp lựa chọn là một thuật toán so sánh tại chỗ được sử dụng để sắp xếp một danh sách ngẫu nhiên thành một danh sách có thứ tự. Nó có độ phức tạp về thời gian là O (n 2 )
- Danh sách được chia thành hai phần, được sắp xếp và không được sắp xếp. Giá trị tối thiểu được chọn từ phần chưa được sắp xếp và đặt vào phần đã sắp xếp.
- Điều này được lặp lại cho đến khi tất cả các mục đã được sắp xếp.
- Việc triển khai mã giả trong Python 3 liên quan đến việc sử dụng hai vòng lặp for và câu lệnh if để kiểm tra xem việc hoán đổi có cần thiết hay không
- Độ phức tạp về thời gian đo lường số bước cần thiết để sắp xếp danh sách.
- Độ phức tạp thời gian trong trường hợp xấu nhất xảy ra khi danh sách theo thứ tự giảm dần. Nó có độ phức tạp về thời gian là [Big-O] O (n 2 )
- Độ phức tạp về thời gian trong trường hợp tốt nhất xảy ra khi danh sách đã có thứ tự tăng dần. Nó có độ phức tạp về thời gian là [Big-Omega] Ω (n 2 )
- Độ phức tạp thời gian theo trường hợp trung bình xảy ra khi danh sách theo thứ tự ngẫu nhiên. Nó có độ phức tạp về thời gian là [Big-theta] ⊝ (n 2 )
- Sắp xếp lựa chọn được sử dụng tốt nhất khi bạn có một danh sách nhỏ các mục cần sắp xếp, chi phí hoán đổi các giá trị không quan trọng và việc kiểm tra tất cả các giá trị là bắt buộc.
- Việc sắp xếp lựa chọn không hoạt động tốt trên các danh sách lớn
- Các thuật toán sắp xếp khác, chẳng hạn như quicksort, có hiệu suất tốt hơn khi so sánh với sắp xếp lựa chọn.