Tôi đang sửa đổi cho kỳ thi.Sắp xếp chèn tốt hơn so với Sắp xếp bong bóng?
Muốn biết trong điều kiện nào, sắp xếp chèn sẽ hoạt động tốt hơn so với sắp xếp bong bóng cho cùng độ phức tạp trung bình của O (N^2).
Tôi đã tìm thấy một số bài viết có liên quan nhưng tôi không thể hiểu chúng.
Mọi người có thể giải thích nó theo một cách đơn giản không?
Tôi đoán câu trả lời bạn đang tìm kiếm là here:
Bubble sort cũng có thể được sử dụng một cách hiệu quả trên danh sách đó đã là sắp xếp ngoại trừ một số rất nhỏ các nguyên tố. Ví dụ: nếu chỉ một phần tử không theo thứ tự, việc sắp xếp bong bóng sẽ chỉ mất 2n thời gian. Nếu hai yếu tố này là không theo thứ tự, bong bóng sắp xếp sẽ chỉ mất tối đa là thời gian 3n ...
và
Sắp xếp chèn là một thuật toán sắp xếp đơn giản đó là tương đối hiệu quả cho các danh sách nhỏ và chủ yếu là sắp xếp danh sách, và thường được sử dụng như một phần của thuật toán phức tạp hơn
Ưu điểm của việc sắp xếp nổi bọt là ở tốc độ phát hiện một đã sorte d danh sách:
sắp xếp nổi bọt nhất Trường hợp Kịch bản: O (n)
Tuy nhiên, ngay cả trong trường hợp này chèn loại trở nên tốt hơn/cùng hiệu suất.
sắp xếp nổi bọt là, nhiều hơn hoặc ít hơn, chỉ tốt cho sự hiểu biết và/hoặc giảng dạy cơ chế sortalgorithm, nhưng sẽ không tìm thấy một cách sử dụng thích hợp trong lập trình những ngày này, vì sự phức tạp của nó
O (n ²)
có nghĩa là hiệu quả của nó giảm đáng kể trên danh sách nhiều hơn một số lượng nhỏ các thành phần.
"bubbleort chỉ tốt cho sự hiểu biết và/hoặc dạy cơ chế thuật toán sắp xếp" - thậm chí không, tôi muốn nói. Sắp xếp chèn không khó hiểu và không khó mã hơn. Sắp xếp bong bóng có một lợi thế rất cụ thể, đó là khả năng phân loại hiệu quả nhất cho một loại lưu trữ cụ thể không có quyền truy cập ngẫu nhiên. Lưu trữ trống, tôi nghĩ, nơi trống quay ở tốc độ không đổi theo một hướng. Sau đó, nó đập loại sắp xếp bởi vì sắp xếp chèn cần phải "nhìn về phía sau", rất chậm. Ưu điểm này hiếm khi được sử dụng thực tế trong những ngày này! –
điều sau lóe lên trong óc tôi:
Bubble sort luôn mất thêm một đường chuyền qua mảng để xác định nếu nó được sắp xếp. Mặt khác, việc sắp xếp chèn không cần điều này - một khi phần tử cuối cùng được chèn vào, thuật toán đảm bảo rằng mảng được sắp xếp.
Sắp xếp bong bóng thực hiện n so sánh trên mọi thẻ. Sắp xếp chèn không nhỏ hơn n so sánh: khi thuật toán tìm vị trí chèn phần tử hiện tại, nó dừng so sánh và lấy phần tử tiếp theo.
Cuối cùng, trích dẫn từ wikipedia bài viết:
Bubble sort cũng tương tác kém với phần cứng CPU hiện đại. Nó yêu cầu ít nhất gấp đôi số lần viết khi sắp xếp chèn, hai lần là nhiều lần xóa bộ nhớ cache và các thông báo sai lệch về chi nhánh càng tiệm cận. Experiments bởi Astrachan sắp xếp chuỗi trong Java hiển thị bong bóng sắp xếp để thể chậm hơn khoảng 5 lần so với sắp xếp chèn và chậm hơn so với lựa chọn 40% loại
Bạn có thể tìm liên kết đến bài nghiên cứu ban đầu ở đó.
cảm ơn Victor. Tôi đã tìm thấy 2 điểm đầu tiên thực sự hữu ích. Bây giờ tôi hiểu một sự khác biệt cơ bản giữa 2 thuật toán là số lượng so sánh được yêu cầu. Chúc mừng – Jonathan
Điểm thứ hai có vẻ không chính xác. Có một số thuật toán làm điều đó. Nhưng tôi nghĩ trong thuật toán sắp xếp bong bóng chính xác, vòng lặp bên trong chạy n-1, n-2, n-3 .... lần trên mỗi lần lặp của vòng lặp ngoài. –
Bạn có thể cung cấp liên kết đến các bài viết liên quan mà bạn không hiểu không? Tôi không chắc họ có thể giải quyết những khía cạnh nào. Ngoài ra, có một sự khác biệt về lý thuyết có thể là phân loại bong bóng phù hợp hơn cho các bộ sưu tập được biểu diễn dưới dạng mảng (hơn là đối với các bộ được biểu diễn dưới dạng danh sách liên kết), trong khi sắp xếp chèn phù hợp với danh sách được liên kết. Lý do sẽ là loại bong bóng luôn hoán đổi hai mục tại một thời điểm không quan trọng trên cả mảng, mảng và danh sách liên kết (hiệu quả hơn trên mảng), trong khi sắp xếp chèn chèn tại một vị trí trong danh sách đã cho danh sách được liên kết nhưng liên quan đến việc di chuyển tất cả các phần tử tiếp theo trong một mảng sang bên phải.
Điều đó đang được nói, mang nó bằng một hạt muối. Trước hết, sắp xếp mảng là, trong thực tế, hầu như luôn luôn nhanh hơn so với phân loại danh sách liên kết. Đơn giản là do việc quét danh sách một lần có sự khác biệt rất lớn. Ngoài ra, di chuyển n phần tử của mảng sang bên phải, nhanh hơn nhiều so với thực hiện các giao dịch ho (hoặc thậm chí n/2). Đây là lý do tại sao các câu trả lời khác xác nhận chính xác việc chèn sắp xếp để được cấp trên nói chung và tại sao tôi thực sự băn khoăn về các bài viết bạn đọc, bởi vì tôi không nghĩ một cách đơn giản để nói điều này tốt hơn trong trường hợp A và tốt hơn trong trường hợp B.
Sắp xếp bong bóng có thể phù hợp hơn với mảng so với sắp xếp bong bóng là danh sách được liên kết, nhưng sắp xếp bong bóng không phù hợp hơn với mảng so với sắp xếp chèn là mảng. –
Có, có thể tôi không đủ rõ ràng trong đoạn cuối. Vấn đề là, sắp xếp bong bóng là tầm thường về mặt khái niệm trên mảng trong khi sắp xếp chèn không phải là "di chuyển mọi thứ từ x sang phải"). Tuy nhiên nó là sự thật, rằng điều này không làm cho bong bóng sắp xếp nhanh hơn. –
vì vậy ví dụ: danh sách được sắp xếp chủ yếu: ví dụ: [2,3,4,5,1] loại bong bóng cần 4 hoán đổi và 4 so sánh Loại sắp xếp cần 4 lần hoán đổi và 4 so sánh. vì vậy sự khác biệt là gì? – Jonathan
trong ví dụ cụ thể đó không có sự khác biệt :) – MarcoS