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

  • Đang chèn
  • Đang so sánh
  • Vừa hoán đổi
  • Phần đã sắp xếp

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 hoạt động giống cách nhiều người xếp bài trên tay. Thuật toán giữ một phần đã sắp xếp ở đầu danh sách, lấy giá trị kế tiếp và đẩy lùi nó qua mọi giá trị lớn hơn cho đến khi vừa chỗ. 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 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. Thử một danh sách gần như đã sắp xếp và một danh sách đảo ngược, rồi so sánh số phép so sánh của mỗi danh sách.

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

Riêng giá trị đầu tiên đã là một phần đã sắp xếp. Lấy giá trị thứ hai và so sánh với giá trị đứng trước; nếu giá trị đó lớn hơn thì hoán đổi, rồi tiếp tục so sánh và hoán đổi cho đến khi giá trị đứng trước không lớn hơn hoặc giá trị đã lên đến đầu. Lúc này hai giá trị đầu đã đúng thứ tự. Làm tương tự với giá trị thứ ba, thứ tư, cho đến cuối danh sách.

Nhanh với danh sách gần như đã sắp xếp

Mỗi lượt dừng ở giá trị đầu tiên không lớn hơn, nên một giá trị vốn đã gần đúng chỗ chỉ tốn một hai phép so sánh. Danh sách đã sắp xếp cần n − 1 phép so sánh và không có hoán đổi; danh sách đảo ngược, trường hợp xấu nhất, cần n(n − 1)/2 phép so sánh và chừng ấy lần hoán đổi. Số lần hoán đổi luôn bằng số nghịch thế của danh sách ban đầu, tức số cặp sai thứ tự. Vì vậy sắp xếp chèn thường được dùng cho danh sách ngắn hoặc gần như đã sắp xếp, và bên trong các thuật toán nhanh hơn để xử lý nốt các đoạn nhỏ.

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

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

Thuật toán dựng một phần đã sắp xếp ở đầu danh sách. Mỗi lượt lấy giá trị kế tiếp và lùi nó qua mọi giá trị lớn hơn đứng trước cho đến khi vừa chỗ. Sau lượt k, k + 1 giá trị đầu đã đúng thứ tự, dù một giá trị đến sau vẫn có thể được chèn vào giữa.

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

Số lần hoán đổi luôn bằng số nghịch thế của danh sách ban đầu: 0 với danh sách đã sắp xếp, n(n − 1)/2 với danh sách đảo ngược. Số phép so sánh bằng số lần hoán đổi cộng tối đa một phép mỗi lượt, nên nằm trong khoảng từ n − 1 đến n(n − 1)/2.

Vì sao sắp xếp chèn nhanh với danh sách gần như đã sắp xếp?

Vì một lượt dừng ngay khi gặp giá trị không lớn hơn. Khi mọi giá trị đều gần vị trí cuối cùng, mỗi lượt đều ngắn, và cả quá trình sắp xếp mất thời gian gần bằng n.

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

Có. Một giá trị chỉ vượt qua các giá trị lớn hơn hẳn, nên các giá trị bằng nhau không bao giờ vượt qua nhau và giữ nguyên thứ tự ban đầu.

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

Không. Quá trình 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