Über Blasensortierung vs Mergesort

Question

Dieses eine Interview-Frage, die ich vor kurzem im Internet gefunden:

Wenn Sie eine Funktion implementieren werden, die ein Integer-Array als Eingabe verwendet und die maximale zurückkommt, würden Sie Blase Art verwenden oder merge sort, um diese Funktion zu implementieren? Was ist, wenn die Array-Größe weniger als 1000 ist? Was ist, wenn es größer als 1000 ist? Diese

ist, wie ich denke darüber nach:

Erstens, es ist wirklich seltsam Sortierung zu verwenden, um die obige Funktion zu implementieren. Sie können nur einmal durch das Array gehen und das Maximum finden. Zweitens, wenn Sie eine Wahl zwischen den beiden treffen müssen, dann ist Bubble-Sort besser - Sie müssen nicht die gesamte Bubble-Sortierprozedur implementieren, sondern müssen nur den ersten Durchlauf durchführen. Es ist besser als merge Sortieren in Zeit und Raum.

Gibt es Fehler in meiner Antwort? Habe ich etwas vergessen?

Answer 1

Es ist eine Trickfrage. Wenn Sie nur den Maximalwert (oder tatsächlich den Wert für alle k, einschließlich des Findens des Medianwertes) wünschen, gibt es einen vollkommen guten O(n) Algorithmus. Sortieren ist Zeitverschwendung. Das wollen sie hören.

Wie Sie sagen, der Algorithmus für Maximum ist wirklich trivial. Um eine solche Frage zu stellen, sollten Sie den Quick-Select-Algorithmus bereithalten und auch eine Heap-Datenstruktur vorschlagen können, falls Sie in der Lage sein müssen, die Werteliste zu mutieren und immer schnell das Maximum erzeugen zu können.

Answer 2

Erstens stimme ich mit allem überein, was Sie gesagt haben, aber vielleicht ist es die Frage der Zeitkomplexität der Algorithmen und wie die Eingabegröße ein großer Faktor ist, der am schnellsten ist.

Bubble Sortierung ist O(n2) und Merge Sort ist O(nlogn). Also, auf einem kleinen Set wird es nicht so anders sein, aber auf vielen Daten wird Bubble Sort viel langsamer sein.

Answer 3

Ich habe nur die Algorithmen gegoogelt. Die Bubble-Sortierung gewinnt in beiden Situationen, weil sie nur einmal durchlaufen werden muss. Merge sort kann keine Abkürzungen abschneiden, um nur die größte Zahl berechnen zu müssen. Mischen nimmt die Länge der Liste, findet die Mitte, und dann vergleichen alle Zahlen unter der Mitte mit der linken Seite und alle oben vergleichen mit der rechten; im Gegensatz zu erstellen einzigartige Paare zu vergleichen. Für jede im Array verbliebene Zahl muss eine gleiche Anzahl von Vergleichen durchgeführt werden. Zusätzlich dazu wird jede Zahl zweimal verglichen, so dass die niedrigsten Zahlen des Arrays in beiden ihrer Vergleiche wahrscheinlich eliminiert werden. Bedeutet nur eine Nummer weniger im Array nach zwei Vergleichen in vielen Situationen. Blase würde dominieren

Answer 4

Abgesehen vom maximalen Teil ist Bubble Sort langsamer asymptotisch, aber es hat einen großen Vorteil für kleine n, da es das Zusammenführen/Erstellen neuer Arrays nicht erfordert. In einigen Implementierungen könnte dies in Echtzeit schneller sein.

Answer 5

nur ein Durchlauf benötigt wird, für die ungünstigsten Fall, maximal zu finden u müssen nur das gesamte Array durchlaufen, so würde Blase besser sein ..

Answer 6

Merge Art ist einfach für einen Computer, um die Elemente zu sortieren und es braucht weniger Zeit zum Sortieren als Blasensortieren. Der beste Fall mit merge sort ist n*log2n und der schlechteste Fall ist n*log2n. Mit Blasensortierung ist der beste Fall O(n) und der schlimmste Fall ist O(n2).