Sắp xếp chọn

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm
Sắp xếp chọn
Mô phỏng sắp xếp chọn
Phân loạiThuật toán sắp xếp
Cấu trúc dữ liệuNgẫu nhiên
Hiệu suất trường hợp tệ nhấtTrung bình
Độ phức tạp không gian trường hợp tệ nhấtKhông tốn thêm vùng nhớ
Tối ưuThỉnh thoảng

Sắp xếp chọn là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh tại chỗ.

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn một phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước thực hiện[sửa | sửa mã nguồn]

  • Bước 1: i=1.
  • Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n].
  • Bước 3: Hoán vị a[min] và a[i]
  • Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2.
  • Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.

Đánh giá[sửa | sửa mã nguồn]

  • Thuật toán ít phải đổi chỗ các phần tử nhất trong số các thuật toán sắp xếp(n lần hoán vị) nhưng có độ phức tạp so sánh là O(n2) (n2/2 phép so sánh).
  • Thuật toán tốn thời gian gần như bằng nhau đối với mảng đã được sắp xếp cũng như mảng chưa được sắp xếp.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]