Có bao giờ có lý do chính đáng để sử dụng Sắp xếp Chèn không?

Question

Để phân loại mục đích chung, câu trả lời dường như là không, như sắp xếp nhanh, sắp xếp hợp nhất và sắp xếp đống có xu hướng hoạt động tốt hơn trong trường hợp trung bình và xấu nhất. Tuy nhiên, sắp xếp chèn xuất hiện để trội hơn khi sắp xếp gia tăng, tức là thêm các phần tử vào danh sách một lần trong một khoảng thời gian dài trong khi vẫn sắp xếp danh sách, đặc biệt nếu sắp xếp chèn được thực hiện dưới dạng danh sách được liên kết (O (log) n) trường hợp trung bình so với O (n)). Tuy nhiên, một heap dường như có thể thực hiện chỉ (hoặc gần) cũng như để sắp xếp gia tăng (thêm hoặc loại bỏ một phần tử duy nhất từ ​​một đống có trường hợp xấu nhất là O (log n)). Vì vậy, chính xác những gì sắp xếp chèn phải cung cấp trên các thuật toán phân loại dựa trên so sánh khác hoặc đống?

Answer 1

Từ http://www.sorting-algorithms.com/insertion-sort:

Mặc dù nó là một trong những thuật toán phân loại tiểu với O (n) thời gian hợp xấu nhất, sắp xếp chèn là thuật toán lựa chọn một trong hai khi dữ liệu là gần như sắp xếp (vì nó là thích ứng) hoặc khi kích thước vấn đề là nhỏ (vì nó có chi phí thấp ).

Đối với những lý do này, và bởi vì nó cũng là ổn định, sắp xếp chèn là thường được sử dụng như trường hợp cơ sở đệ quy (khi kích thước vấn đề là nhỏ) cho overhead chia-và-chinh phục thuật toán sắp xếp cao hơn, chẳng hạn như hợp nhất sắp xếp hoặc sắp xếp nhanh.

Answer 2

Hầu hết các quy trình sắp xếp sẽ sử dụng quicksort và sau đó sắp xếp chèn cho các tập dữ liệu rất nhỏ.

Answer 3

Một khái niệm quan trọng trong phân tích thuật toán là phân tích tiệm cận. Trong trường hợp của hai thuật toán với thời gian chạy tiệm cận khác nhau, chẳng hạn như một O (n^2) và một O (nlogn) như trường hợp với sắp xếp chèn và quicksort tương ứng, nó không xác định rằng một là nhanh hơn .

Sự khác biệt quan trọng với loại phân tích này là đối với đủ lớn N, một thuật toán sẽ nhanh hơn một thuật toán khác. Khi phân tích một thuật toán xuống đến một thuật ngữ như O (nlogn), bạn thả các hằng số. Khi thực tế phân tích hoạt động của thuật toán, các hằng số này sẽ chỉ quan trọng đối với các tình huống của n nhỏ.

Vậy điều này có nghĩa là gì? Điều đó có nghĩa là đối với một số n nhỏ, một số thuật toán nhanh hơn. Điều này article từ EmbeddedGurus.net bao gồm một quan điểm thú vị về việc lựa chọn các thuật toán phân loại khác nhau trong trường hợp của một không gian hạn chế (16k) và hệ thống bộ nhớ hạn chế. Tất nhiên, các tài liệu tham khảo bài viết chỉ phân loại một danh sách 20 số nguyên, vì vậy các đơn đặt hàng lớn hơn của n là không liên quan. Mã ngắn hơn và tiêu thụ bộ nhớ ít hơn (cũng như tránh đệ quy) cuối cùng là quyết định quan trọng hơn.

Loại chèn có chi phí thấp, có thể viết khá ngắn gọn và có hai lợi ích chính: ổn định và có trường hợp chạy nhanh khi đầu vào gần như sắp xếp.

Answer 4

Nếu bạn đang nói về việc duy trì danh sách được sắp xếp, không có lợi thế so với một số loại cây, nó chỉ chậm hơn.

Vâng, có thể nó tiêu thụ ít bộ nhớ hơn hoặc thực hiện đơn giản hơn.

Chèn vào một danh sách được sắp xếp sẽ liên quan đến quá trình quét, có nghĩa là mỗi chèn là O (n), do đó sắp xếp các mặt hàng n trở thành O (n^2)

Chèn vào một container như một cây cân bằng, thường là log (n), do đó sắp xếp là O (n log (n)), tất nhiên là tốt hơn.

Nhưng đối với các danh sách nhỏ, nó hầu như không tạo ra bất kỳ sự khác biệt nào. Bạn có thể sử dụng một loại chèn nếu bạn phải tự viết nó mà không có bất kỳ thư viện nào, danh sách nhỏ và/hoặc bạn không quan tâm đến hiệu suất.

Answer 5

CÓ,

Loại sắp xếp tốt hơn Sắp xếp nhanh trên danh sách ngắn.

Trong thực tế, một Sắp xếp nhanh tối ưu có ngưỡng kích thước mà nó dừng lại, và sau đó toàn bộ mảng được sắp xếp bằng cách sắp xếp sắp xếp qua giới hạn ngưỡng.

Ngoài ra ...

Để duy trì bảng điểm, Phân loại chèn nhị phân có thể tốt như vậy.

Xem this page.

Answer 6

Có, có lý do để sử dụng loại sắp xếp hoặc một trong các biến thể của nó.

Lựa chọn thay thế sắp xếp (sắp xếp nhanh, v.v.) của các câu trả lời khác ở đây làm cho giả định rằng dữ liệu đã có trong bộ nhớ và sẵn sàng hoạt động. Nhưng nếu bạn đang cố gắng đọc một lượng lớn dữ liệu từ một nguồn bên ngoài chậm hơn (nói một ổ đĩa cứng), có một lượng lớn thời gian lãng phí vì nút cổ chai rõ ràng là kênh dữ liệu hoặc chính ổ đĩa đó. Nó chỉ không thể theo kịp với CPU. Một loạt chờ đợi tự nhiên xảy ra trong bất kỳ lần đọc nào. Những lần chờ này là các chu kỳ CPU bị lãng phí trừ khi bạn sử dụng chúng để sắp xếp khi bạn đi.

Ví dụ, nếu bạn đã làm cho giải pháp của bạn này là như sau:

1. Đọc một tấn dữ liệu trong một vòng lặp chuyên dụng vào bộ nhớ
2. Sắp xếp dữ liệu

Bạn rất có thể sẽ mất nhiều thời gian hơn nếu bạn đã làm như sau trong hai chủ đề.

Chủ đề A:

1. đọc một dữ kiện
2. Nơi mốc tính toán vào FIFO hàng đợi
3. (Lặp lại cho đến khi dữ liệu cạn kiệt từ ổ đĩa)

Thread B:

1. Lấy datum từ hàng đợi FIFO
2. Chèn nó vào vị trí thích hợp trong danh sách được sắp xếp của bạn
3. (lặp lại cho đến khi hàng đợi rỗng VÀ chủ đề Một nói "done").

... ở trên sẽ cho phép bạn sử dụng thời gian lãng phí khác. Lưu ý: Chủ đề B không cản trở tiến độ của luồng A.

Khi dữ liệu được đọc đầy đủ, dữ liệu sẽ được sắp xếp và sẵn sàng để sử dụng.

Answer 7

Một khái niệm quan trọng trong phân tích các thuật toán là phân tích tiệm cận. Trong trường hợp của hai thuật toán với thời gian chạy tiệm cận khác nhau, chẳng hạn như một O (n^2) và một O (nlogn) là trường hợp với sắp xếp chèn và quicksort tương ứng, nó không phải là xác định rằng một là nhanh hơn khác.

Sự khác biệt quan trọng với loại phân tích này là đối với N đủ lớn, một thuật toán sẽ nhanh hơn một thuật toán khác. Khi phân tích một thuật toán xuống đến một thuật ngữ như O (nlogn), bạn thả các hằng số. Khi thực tế phân tích hoạt động của thuật toán, các hằng số này sẽ chỉ quan trọng đối với các tình huống của n nhỏ.

Vậy điều này có nghĩa là gì? Điều đó có nghĩa là đối với một số n nhỏ, một số thuật toán nhanh hơn. Bài viết này từ EmbeddedGurus.net bao gồm một quan điểm thú vị về việc lựa chọn các thuật toán phân loại khác nhau trong trường hợp của một không gian hạn chế (16k) và hệ thống bộ nhớ hạn chế. Tất nhiên, các tài liệu tham khảo bài viết chỉ phân loại một danh sách 20 số nguyên, vì vậy các đơn đặt hàng lớn hơn của n là không liên quan. Mã ngắn hơn và tiêu thụ bộ nhớ ít hơn (cũng như tránh đệ quy) cuối cùng là quyết định quan trọng hơn.

Loại chèn có chi phí thấp, có thể viết khá ngắn gọn và có hai lợi ích chính: ổn định và có trường hợp chạy nhanh khi đầu vào gần như sắp xếp.

Answer 8

Để sắp xếp chèn mảng nhỏ hoạt động nhanh hơn quicksort. Java 7 và Java 8 sử dụng tính năng tăng tốc trục kép để sắp xếp các loại dữ liệu nguyên thủy. Tua nhanh trục kép thực hiện các thao tác rút gọn trục đơn đơn giản điển hình. Theo thuật toán của quick port kép pivot:

1. Đối với mảng nhỏ (chiều dài < 27), hãy sử dụng thuật toán sắp xếp chèn.
2. Chọn hai trục ...........

definetely sắp xếp chèn ra thực hiện quicksort cho mảng nhỏ và đó là lý do tại sao bạn là chuyển sang sắp xếp chèn cho mảng có độ dài ít hơn 27. Lý do có thể là không có sự thu thập trong sắp xếp chèn.

Nguồn: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf