Sắp xếp lựa chọn: Thuật toán được giải thích bằng Python Ví dụ về mã

Sắp xếp lựa chọn là gì?

SẮP XẾP LỰA 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êm. Nó chỉ yêu cầu thêm một vùng nhớ cho biến thời gian.

Điều này được gọi là tại chỗ sắp xếp. Sắp xếp lựa chọn có độ phức tạp thời gian là O(n²) trong đó n là tổng số mục trong danh sách. Độ phức tạp 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 đã sắp xếp, trong khi danh sách thứ hai chứa các mục chưa 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ử. Danh sách chưa sắp xếp sau đó được quét tìm giá trị tối thiểu, sau đó được đặt 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.

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 sắp xếp được so sánh với tất cả các giá trị ở phía bên phải để kiểm tra xem đó có phải là giá trị tối thiểu hay không. Nếu nó không phải là giá trị tối thiểu thì vị trí của nó sẽ được hoán đổi với giá trị tối thiểu.

Ví dụ

Ví dụ: nếu chỉ mục của giá trị tối thiểu là 3 thì giá trị của phần tử có chỉ mục 3 được đặt ở chỉ mục 0 trong khi giá trị ở chỉ mục 0 được đặt ở chỉ mục 3. Nếu phần tử đầu tiên trong phân vùng chưa được sắp xếp là giá trị tối thiểu thì nó sẽ trả về vị trí của nó.
Phần tử đã được xác định là giá trị nhỏ nhất sau đó sẽ được chuyển sang phân vùng ở phía bên trái, đây là danh sách được sắp xếp.
Bên được phân vùng hiện 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 đề

Danh sách các phần tử được sắp xếp ngẫu nhiên cần được sắp xếp theo thứ tự tăng dần. Hãy xem xét danh sách sau đây làm ví dụ.

[21,6,9,33,3]

Danh sách trên phải đượ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à chưa 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ị tối thiểu từ phần chưa được phân vùng và đặt nó vào phần được sắp xếp.

Bước 4) Lặp lại quá 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

Với danh sách năm phần tử, các hình ảnh sau đây 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 hiển thị 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 đó có phải là giá trị tối thiểu hay không.

3 là giá trị nhỏ nhất nên vị trí của 21 và 3 được hoán đổi cho nhau. Các giá trị có nền màu xanh lá cây biểu thị 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 sắp xếp được so sánh với các giá trị còn lại để tìm hiểu xem có tồn tại giá trị thấp hơn không

Giá trị 6 là giá trị tối thiểu nên nó duy trì vị trí của mình.

Bước 3)

Phần tử đầu tiên của danh sách chưa sắp xếp có giá trị 9 được so sánh với các giá trị còn lại để kiểm tra xem đó có phải là giá trị tối thiểu hay không.

Giá trị 9 là giá trị nhỏ nhất nên nó duy trì vị trí của nó trong phân vùng được 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 nên 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. Vì vậy, nó đã được sắp xếp.

Danh sách cuối cùng giống như danh sách hiển thị 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 đây cho thấy việc triển khai sắp xếp lựa chọn sử dụng Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Chạy đoạn mã trên sẽ cho ra 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 về Mã:

Xác định một hàm có tên SelectionSort
Lấy tổng số phần tử trong danh sách. Chúng ta cần điều này để xác định số lần thực hiện khi so sánh các giá trị.
Vòng lặp bên 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 nên (5 – 1) cho ta kết quả 4. Điều này có nghĩa là các lần 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ậ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 ở phía bên phải 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ởi giá trị tối thiểu
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 el có số ngẫu nhiên
In danh sách đã sắp xếp sau khi gọi hàm Sắp xếp lựa chọn truyền vào el làm tham số.

Độ phức tạp thời gian của sắp xếp lựa chọn

Độ phức tạp sắp xếp được sử dụng để thể hiện 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 thi n lần trong đó 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 trong đó n là tổng số phần tử trong danh sách.

Do đó, số lần thực thi là (n * n), cũng có thể được biểu thị dưới dạng O(n²).

Thuật toán sắp xếp lựa chọn có ba loại độ phức tạp, cụ thể là;

Trường hợp xấu 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²)
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ượng thực thi tối thiểu được biểu thị là [Big-Omega] ?(n²)
Trường hợp trung bình – điều này xảy ra khi danh sách được sắp xếp ngẫu nhiên. Độ phức tạp trung bình được biểu thị là [Big-theta] ?(n²)

Thuật toán sắp xếp lựa chọn có độ phức tạp về 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 giá trị.

Khi nào nên sử dụng sắp xếp lựa chọn?

Sắp xếp 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ị là 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 việc sắp xếp lựa chọn

Nó hoạt động rất tốt trên danh sách nhỏ
Nó là một thuật toán tại chỗ. Nó không đòi hỏi nhiều không gian để sắp xếp. 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ương pháp sắp xếp lựa chọn.

Nó hoạt động kém khi làm việc trên 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ư sắp xếp nhanh, có hiệu suất tốt hơn so với sắp xếp chọn lọc.

Tổng kết

Selection sort là 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 thời gian là O(n²)
Danh sách được chia thành hai phần, được sắp xếp và chưa sắp xếp. Giá trị tối thiểu được chọn từ phần chưa 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.
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 có cần hoán đổi 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 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 thời gian là [Big-O] O(n²)
Độ phức tạp thời gian trường hợp tốt nhất xảy ra khi danh sách đã theo thứ tự tăng dần. Nó có độ phức tạp thời gian là [Big-Omega] ?(n²)
Độ phức tạp thời gian trường hợp trung bình xảy ra khi danh sách được sắp xếp ngẫu nhiên. Nó có độ phức tạp thời gian là [Big-theta] ?(n²)
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 giá trị không thành vấn đề và việc kiểm tra tất cả các giá trị là bắt buộc.
Sắp xếp lựa chọn không hoạt động tốt trên 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 so với sắp xếp chọn lọc.

Bạn có thể thích: