So sánh
Hoán đổi
Lượt

  • Đang so sánh
  • Nhỏ nhất hiện tại
  • Vừa hoán đổi
  • Đã đúng chỗ

Tìm hiểu thêm về sắp xếp chọn

Sắp xếp chọn

Sắp xếp chọn xây dựng danh sách đã sắp xếp từ đầu. Mỗi lượt quét các giá trị chưa được sắp xếp, ghi nhớ giá trị nhỏ nhất, rồi hoán đổi nó vào vị trí chưa sắp xếp đầu tiên. Phát với tốc độ bất kỳ, hoặc đi từng phép so sánh, và theo dõi bộ đếm phép so sánh, hoán đổi và lượt. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các ô đếm số phép so sánh, hoán đổi và lượt. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Chọn số cột và thứ tự ban đầu: ngẫu nhiên, gần như đã sắp xếp, đảo ngược, hoặc ít giá trị khác nhau. Hoặc tự nhập các số.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
  3. Theo dõi giá trị nhỏ nhất hiện tại thay đổi trong lúc quét, và lần hoán đổi đưa nó vào đúng chỗ ở cuối mỗi lượt.

Sắp xếp chọn hoạt động thế nào

Xem mọi giá trị trong danh sách và ghi nhớ giá trị nhỏ nhất. Hoán đổi nó với giá trị đầu tiên: vị trí đầu tiên giờ đã cố định. Sau đó làm tương tự với phần còn lại của danh sách, bắt đầu từ vị trí kế tiếp. Sau n − 1 lượt, mọi giá trị đều đã đúng chỗ, và giá trị cuối cùng tự nhiên đúng chỗ.

Nhiều phép so sánh, ít hoán đổi

Lượt quét không bao giờ dừng sớm, vì chỉ sau khi xem hết mọi giá trị còn lại mới chắc chắn được giá trị nào nhỏ nhất. Vì vậy sắp xếp chọn luôn thực hiện đúng n(n − 1)/2 phép so sánh với n giá trị, dù danh sách đã sắp xếp, đảo ngược hay ngẫu nhiên. Đổi lại, nó chỉ hoán đổi tối đa n − 1 lần, mỗi lượt một lần. Nhờ đó nó là lựa chọn hợp lý khi di chuyển một giá trị tốn kém hơn nhiều so với so sánh hai giá trị.

Câu hỏi thường gặp

Sắp xếp chọn hoạt động thế nào?

Nó lặp lại việc chọn giá trị nhỏ nhất chưa được sắp xếp và hoán đổi nó vào vị trí chưa sắp xếp đầu tiên. Sau lượt k, k vị trí đầu chứa k giá trị nhỏ nhất theo thứ tự.

Sắp xếp chọn thực hiện bao nhiêu phép so sánh và hoán đổi?

Luôn là n(n − 1)/2 phép so sánh với n giá trị: 45 với 10 giá trị, 780 với 40. Số lần hoán đổi tối đa là n − 1, mỗi lượt một lần, và ít hơn khi giá trị nhỏ nhất đã đúng chỗ.

Vì sao danh sách đã sắp xếp lại mất thời gian như danh sách đảo ngược?

Vì mỗi lượt phải xem hết mọi giá trị còn lại mới chắc chắn đã tìm được giá trị nhỏ nhất. Khác với sắp xếp nổi bọt và sắp xếp chèn, sắp xếp chọn không thể biết từ các phép so sánh rằng danh sách đã được sắp xếp.

Sắp xếp chọn có ổn định không?

Không, ở dạng thông thường. Một lần hoán đổi có thể đưa một giá trị vượt qua giá trị bằng nó: với 2, 2, 1, số 2 đầu tiên hoán đổi với 1 và nằm sau số 2 thứ hai. Phiên bản dịch chuyển các giá trị thay vì hoán đổi thì ổn định, nhưng phải di chuyển nhiều hơn.

Các số của tôi có bị gửi đi đâu không?

Không. Việc sắp xếp chạy trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa