Sắp xếp chọn¶
Sắp xếp chọn hoạt động rất đơn giản: trong mỗi vòng, nó chọn phần tử nhỏ nhất từ khoảng chưa được sắp xếp và đặt nó vào cuối khoảng đã được sắp xếp.
Giả sử mảng có độ dài \(n\). Quy trình của sắp xếp chọn được minh họa trong hình dưới đây.
- Ban đầu, tất cả các phần tử đều chưa được sắp xếp, nghĩa là khoảng (chỉ số) chưa được sắp xếp là \([0, n-1]\).
- Chọn phần tử nhỏ nhất trong khoảng \([0, n-1]\) và hoán đổi nó với phần tử tại chỉ số \(0\). Sau khi hoàn thành, phần tử đầu tiên của mảng đã được sắp xếp.
- Chọn phần tử nhỏ nhất trong khoảng \([1, n-1]\) và hoán đổi nó với phần tử tại chỉ số \(1\). Sau khi hoàn thành, 2 phần tử đầu tiên của mảng đã được sắp xếp.
- Và cứ tiếp tục như vậy. Sau \(n - 1\) vòng chọn và hoán đổi, \(n - 1\) phần tử đầu tiên của mảng đã được sắp xếp.
- Phần tử duy nhất còn lại chắc chắn là phần tử lớn nhất, do đó không cần sắp xếp thêm và mảng đã được sắp xếp.
Trong mã nguồn, chúng ta sử dụng \(k\) để theo dõi phần tử nhỏ nhất trong khoảng chưa được sắp xếp:
Đặc điểm của thuật toán¶
- Độ phức tạp thời gian là \(O(n^2)\), sắp xếp không thích ứng: Vòng lặp ngoài có tổng cộng \(n - 1\) vòng. Độ dài của khoảng chưa được sắp xếp trong vòng đầu tiên là \(n\), và độ dài của khoảng chưa được sắp xếp trong vòng cuối cùng là \(2\). Nghĩa là, các vòng của vòng lặp ngoài chứa các vòng lặp trong với lần lượt \(n\), \(n - 1\), \(\dots\), \(3\), và \(2\) lượt lặp, tổng số lượt lặp là \(\frac{(n - 1)(n + 2)}{2}\).
- Độ phức tạp không gian là \(O(1)\), sắp xếp tại chỗ: Các con trỏ \(i\) và \(j\) sử dụng một lượng không gian bổ sung không đổi.
- Sắp xếp không ổn định: Như minh họa trong hình dưới đây, phần tử
nums[i]có thể bị hoán đổi sang bên phải của một phần tử bằng nó, làm thay đổi thứ tự tương đối của chúng.
