Sắp xếp lựa chọn DSA

Sắp xếp lựa chọn

Thuật toán Sắp xếp Lựa chọn tìm giá trị thấp nhất trong một mảng và di chuyển nó lên đầu mảng.

Thuật toán xem đi xem lại mảng, di chuyển các giá trị thấp nhất tiếp theo lên phía trước cho đến khi mảng được sắp xếp.

Tiếp tục đọc để hiểu đầy đủ về thuật toán Sắp xếp lựa chọn và cách tự thực hiện nó.

Chạy qua thủ công

Trước khi triển khai thuật toán Sắp xếp lựa chọn trong ngôn ngữ lập trình, chúng ta hãy chạy thủ công qua một mảng ngắn chỉ một lần để có ý tưởng.

Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp.

Bước 2: Duyệt qua mảng, mỗi lần một giá trị. Giá trị nào thấp nhất? 3 phải không?

Bước 3: Di chuyển giá trị thấp nhất 3 lên đầu mảng.

Bước 4: Xem qua các giá trị còn lại, bắt đầu từ 7. 7 là giá trị thấp nhất và đã ở đầu mảng nên chúng ta không cần di chuyển nó.

Bước 5: Xem qua phần còn lại của mảng: 12, 9 và 11. 9 là giá trị thấp nhất.

Bước 6: Di chuyển số 9 lên phía trước.

Bước 7: Nhìn 12 và 11 thì 11 là thấp nhất.

Bước 8: Di chuyển nó ra phía trước.

Cuối cùng, mảng được sắp xếp.

Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Chúng ta phải hiểu những gì đã xảy ra ở trên để hiểu đầy đủ về thuật toán, để có thể triển khai thuật toán bằng ngôn ngữ lập trình.

Bạn có thể thấy điều gì đã xảy ra với giá trị 3 thấp nhất không? Ở bước 3, nó đã được chuyển đến đầu mảng, nơi nó thuộc về, nhưng ở bước đó, phần còn lại của mảng vẫn chưa được sắp xếp.

Vì vậy, thuật toán Sắp xếp lựa chọn phải chạy đi chạy lại mảng, mỗi lần giá trị thấp nhất tiếp theo được di chuyển trước phần chưa được sắp xếp của mảng, đến đúng vị trí của nó. Việc sắp xếp tiếp tục cho đến khi giá trị cao nhất 12 còn lại ở cuối mảng. Điều này có nghĩa là chúng ta cần chạy qua mảng 4 lần để sắp xếp mảng gồm 5 giá trị.

Và mỗi khi thuật toán chạy qua mảng, phần chưa được sắp xếp còn lại của mảng sẽ trở nên ngắn hơn.

Bây giờ chúng ta sẽ sử dụng những gì đã học để triển khai thuật toán Sắp xếp lựa chọn trong ngôn ngữ lập trình.

Triển khai sắp xếp lựa chọn

Để triển khai thuật toán Sắp xếp lựa chọn trong ngôn ngữ lập trình, chúng ta cần:

1. Một mảng có các giá trị cần sắp xếp.
2. Một vòng lặp bên trong đi qua mảng, tìm giá trị thấp nhất và di chuyển nó lên đầu mảng. Vòng lặp này phải lặp qua một giá trị ít hơn mỗi lần nó chạy.
3. Vòng lặp bên ngoài kiểm soát số lần vòng lặp bên trong phải chạy. Đối với một mảng có giá trị \(n\), vòng lặp bên ngoài này phải chạy \(n-1\) lần.

Mã kết quả trông như thế này:

 my_array = [64, 34, 25, 5, 22, 11, 90, 12]

n = len(my_array)
for i in range(n-1):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j
    min_value = my_array.pop(min_index)
    my_array.insert(i, min_value)

print("Sorted array:", my_array)

Vấn đề dịch chuyển sắp xếp lựa chọn

Thuật toán Sắp xếp lựa chọn có thể được cải thiện thêm một chút.

Trong đoạn mã trên, phần tử có giá trị thấp nhất sẽ bị xóa và sau đó được chèn vào phía trước mảng.

Mỗi lần phần tử mảng có giá trị thấp nhất tiếp theo bị xóa, tất cả các phần tử sau phải được dịch chuyển xuống một vị trí để bù cho việc xóa.

Những thao tác chuyển dịch này mất rất nhiều thời gian và chúng tôi thậm chí còn chưa hoàn thành! Sau khi tìm thấy và xóa giá trị thấp nhất (5), nó sẽ được chèn vào đầu mảng, khiến tất cả các giá trị sau dịch chuyển lên một vị trí để tạo khoảng trống cho giá trị mới, như hình ảnh bên dưới hiển thị.

Giải pháp: Hoán đổi giá trị!

Thay vì chuyển đổi tất cả, hãy hoán đổi giá trị thấp nhất (5) với giá trị đầu tiên (64) như bên dưới.

Chúng ta có thể hoán đổi các giá trị như hình ảnh hiển thị ở trên vì giá trị thấp nhất kết thúc ở đúng vị trí và việc chúng ta đặt giá trị khác mà chúng ta đang hoán đổi ở đâu không quan trọng vì nó chưa được sắp xếp.

Dưới đây là mô phỏng cho thấy cách hoạt động của Sắp xếp lựa chọn cải tiến với tính năng hoán đổi:

Đây là cách triển khai Sắp xếp lựa chọn được cải tiến, sử dụng tính năng hoán đổi:

 my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j   
    my_array[i], my_array[min_index] = my_array[min_index], my_array[i]

print("Sorted array:", my_array)

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

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp Lựa chọn, hãy truy cập trang này .

Sắp xếp lựa chọn sắp xếp một mảng các giá trị \(n\).

Trung bình, khoảng \(\frac{n}{2}\) phần tử được so sánh để tìm giá trị thấp nhất trong mỗi vòng lặp.

Và Sắp xếp lựa chọn phải chạy vòng lặp để tìm giá trị thấp nhất khoảng \(n\) lần.

Chúng tôi nhận được độ phức tạp về thời gian:

\[ O( \frac{n}{2} \cdot n) = \underline{\underline{O(n^2)}} \]

Độ phức tạp về thời gian của thuật toán Sắp xếp lựa chọn có thể được hiển thị trong biểu đồ như sau:

Như bạn có thể thấy, thời gian chạy cũng giống như Bubble Sort: Thời gian chạy tăng rất nhanh khi kích thước của mảng tăng lên.

Chạy mô phỏng bên dưới cho các mảng có kích thước khác nhau.

Đường đứt nét màu đỏ biểu thị độ phức tạp về mặt thời gian theo lý thuyết \(O(n^2)\).

Các dấu thập màu xanh lam xuất hiện khi bạn chạy mô phỏng. Các dấu thập màu xanh lam cho biết cần bao nhiêu thao tác để sắp xếp một mảng có kích thước nhất định.

Sự khác biệt đáng kể nhất so với Sắp xếp nổi bọt mà chúng ta có thể nhận thấy trong mô phỏng này là trường hợp tốt nhất và xấu nhất thực sự gần giống nhau đối với Sắp xếp lựa chọn (\(O(n^2)\)), nhưng đối với Sắp xếp bong bóng thời gian chạy trường hợp tốt nhất là chỉ \(O(n)\).

Sự khác biệt trong trường hợp tốt nhất và xấu nhất đối với Sắp xếp lựa chọn chủ yếu là số lần hoán đổi. Trong trường hợp tốt nhất, Sắp xếp lựa chọn không phải hoán đổi bất kỳ giá trị nào vì mảng đã được sắp xếp. Và trong trường hợp xấu nhất, khi mảng đã được sắp xếp nhưng sai thứ tự, vì vậy Sắp xếp lựa chọn phải thực hiện nhiều lần hoán đổi bằng số giá trị trong mảng.