Về bong bóng sắp xếp vs merge sort

Question

Đây là một câu hỏi phỏng vấn mà tôi vừa tìm thấy trên Internet:

Nếu bạn đang đi để thực hiện một chức năng mà phải mất một mảng số nguyên như là đầu vào và trả về tối đa, bạn sẽ sử dụng bong bóng sắp xếp hoặc hợp nhất sắp xếp để thực hiện chức năng này? Điều gì sẽ xảy ra nếu kích thước mảng nhỏ hơn 1000? Nếu nó lớn hơn 1000 thì sao?

Đây là cách tôi suy nghĩ về điều này:

Đầu tiên, việc sử dụng phân loại để thực hiện chức năng trên thực sự rất lạ. Bạn chỉ có thể đi qua các mảng một lần và tìm thấy một trong những tối đa. Thứ hai, nếu phải lựa chọn giữa hai loại, thì việc sắp xếp bong bóng tốt hơn - bạn không phải thực hiện toàn bộ quy trình sắp xếp bong bóng mà chỉ cần thực hiện lần đầu tiên. Nó tốt hơn so với sắp xếp hợp nhất cả về thời gian lẫn không gian.

Có bất kỳ sai lầm nào trong câu trả lời của tôi không? Tôi đã bỏ lỡ bất cứ điều gì?

Answer 1

Đó là một câu hỏi mẹo. Nếu bạn chỉ muốn tối đa, (hoặc thực sự, k ^thứ giá trị cho bất kỳ k, bao gồm việc tìm kiếm trung vị), có một thuật toán hoàn hảo tốt O(n). Phân loại là một sự lãng phí thời gian. Đó là những gì họ muốn nghe.

Như bạn nói, thuật toán cho tối đa thực sự tầm thường. Để đưa ra một câu hỏi như thế này, bạn nên có sẵn thuật toán chọn nhanh và cũng có thể đề xuất một cơ sở hạ tầng heap trong trường hợp bạn cần có khả năng thay đổi danh sách các giá trị và luôn có thể tạo ra nhanh nhất.

Answer 2

Thứ nhất, tôi đồng ý với mọi thứ bạn đã nói, nhưng có lẽ nó đang hỏi về sự hiểu biết về độ phức tạp của thời gian và cách kích thước đầu vào là yếu tố lớn nhất sẽ nhanh nhất.

Sắp xếp bong bóng là O(n2) và Hợp nhất sắp xếp là O(nlogn). Vì vậy, trên một bộ nhỏ nó sẽ không khác nhau nhưng trên rất nhiều dữ liệu Bubble sắp xếp sẽ chậm hơn nhiều.

Answer 3

Tôi vừa googled các thuật toán. Loại bong bóng chiến thắng trong cả hai tình huống vì lợi ích lớn nhất chỉ phải chạy qua nó một lần. Sắp xếp hợp nhất không thể cắt bất kỳ vết cắt ngắn nào cho chỉ phải tính số lớn nhất. Hợp nhất có độ dài của danh sách, tìm phần giữa, và sau đó tất cả các số bên dưới so sánh giữa phía bên trái và tất cả ở trên so sánh với bên phải; đối lập với việc tạo ra các cặp độc nhất để so sánh. Có nghĩa là cho mỗi số còn lại trong mảng một số lượng tương đương so sánh cần phải được thực hiện. Ngoài ra, mỗi số được so sánh hai lần để số lượng thấp nhất của mảng sẽ bị loại bỏ nhất trong cả hai so sánh của chúng. Có nghĩa là chỉ có một số ít hơn trong mảng sau khi thực hiện hai so sánh trong nhiều tình huống. Bong bóng sẽ thống trị

Answer 4

Chặn phần tối đa, phân loại bong bóng chậm hơn tiệm cận, nhưng nó có lợi thế lớn cho nhỏ n ở chỗ nó không yêu cầu sáp nhập/tạo mảng mới. Trong một số triển khai, điều này có thể làm cho nó nhanh hơn trong thời gian thực.

Answer 5

chỉ có một đường chuyền là cần thiết, đối với trường hợp tồi tệ nhất, để tìm tối đa u chỉ phải đi qua toàn bộ mảng, do đó bong bóng sẽ tốt hơn ..

Answer 6

Merge sort là dễ dàng cho một máy tính để sắp xếp các yếu tố và nó mất ít thời gian hơn để sắp xếp loại bong bóng. Trường hợp tốt nhất với loại hợp nhất là n*log2n và trường hợp xấu nhất là n*log2n. Với trường hợp loại bong bóng tốt nhất là O(n) và trường hợp xấu nhất là O(n2).