Wie finde ich die größte Elementnummer (Array-Größe), lassen Sie Insertion sort Beat Merge sort? - Algorithmus, Sortieren, Mergesort, Einfügen-Sortieren

von der Wiki-Seite der Einfügung Sortierung:

Einige Divide-and-Conquer-Algorithmen wie zquicksort und mergesort sort durch rekursives Unterteilen der Liste in kleinere Unterlisten, die dann sortiert. Eine nützliche Optimierung in der Praxis für diese Algorithmen ist Sortierung zum Sortieren von kleinen Unterlisten verwenden, wo Sortierung übertrifft diese komplexeren Algorithmen. Die Größe der Liste für welche Einfügesortierung hat den Vorteil, je nach Umgebung und variiert Implementierung, aber ist in der Regel zwischen acht und zwanzig Elemente.

das Zitat aus wiki hat einen Grund, dass die kleinen Listen aus merge sort nicht schlimmer sind für einsortieren.

Ich möchte diesen Grund einfach ignorieren.

Ich wusste, dass, wenn die Array-Größe klein ist, Insertion sort O (n ^ 2) die Chance hat, Merge Sort O (n log n) zu schlagen.

Ich denke (nicht sicher) das hängt mit den Konstanten in T (n) zusammen

Einfügesortierung: T (n) = c1n ^ 2 + c2n + c3

Zusammenführen Sortieren: T (n) = n log n + cn

Jetzt ist meine Frage, auf der gleichen Maschine, der gleiche Fall (schlimmer Fall), wie man die größte Elementnummer herausfindet, ließ Einfügung sortieren Schlag mergen sortieren?

Antworten:

1 für die Antwort № 1

Es ist einfach:

Nehmen Sie eine Reihe von Beispiel-Arrays zum Sortieren und Iterieren über einen Wert k, wobei k der Schwellenwert für den Übergang von Zusammenführen zu Einfügen ist.

dann geh

for(int k = 1; k < MAX_TEST_VALUE; k++) {
System.out.println("Results for k = " + k);
for(int[] array : arraysToTest) {
long then = System.currentTimeMillis();
mergeSort(array,k); // pass in k to your merge sort so it uses that
long now = System.currentTimeMillis();
System.out.println(now - then);
}
}

Für was es wert ist, die java.util.Arrays Klasse hat dazu in ihrer internen Dokumentation zu sagen:

/**
* Tuning parameter: list size at or below which insertion sort will be
* used in preference to mergesort or quicksort.
*/
private static final int INSERTIONSORT_THRESHOLD = 7;

/**
* Src is the source array that starts at index 0
* Dest is the (possibly larger) array destination with a possible offset
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
*/
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;

// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}

In seinen primitiven Sequenzen verwendet es auch 7, obwohl es nicht den konstanten Wert verwendet.

---

0 für die Antwort № 2

In der Regel erfolgt dies durch Testen mit Arrays unterschiedlicher Größe n == 10Die Einfügesortierung ist fast sicher schneller. Wann n == 100, wahrscheinlich nicht. Testen, testen, testen, bis Ihre Ergebnisse konvergieren.

Ich nehme an es ist möglich um die Zahl streng zu bestimmenAnalyse, aber um dies zu tun, müssen Sie genau wissen, welcher Code vom Compiler erzeugt wird, Timings für die Instruktionen einschließen und Dinge wie die Kosten von Cache-Misses usw. berücksichtigen. Alles in allem ist es am einfachsten, sie abzuleiten empirisch.

---

0 für die Antwort № 3

Die Einfügesortierung schlägt normalerweise die Merge-Sortierung für sortierte (oder fast sortierte) Listen beliebiger Größe vor.

Also die Frage "Wie finde ich die größte Elementnummer (Array-Größe), lassen Insertion Sortierung Beat Merge sort?" Ist nicht wirklich richtig.

bearbeiten: Nur um die Downvoters von meinem Rücken zu bekommen: Die Frage könnte umformuliert werden als:

1. "Wie ermittelt man die größte Array-Größe fürIm Durchschnitt, Insertion sort schlägt Merge sort ". Dies wird in der Regel empirisch durch die Generierung von Probe von Arrays von kleiner Größe und laufenden Implementierungen beider Algorithmen auf ihnen gemessen. Glowcoder macht das in seiner Antwort.
2. "Was ist die größte Array-Größe für dieSortierung Sortierung im schlechtesten Fall besser als Sortierung Sortierung "Dies ist etwas, das annähernd durch eine einfache Rechnung beantwortet werden kann, da IS im schlimmsten Fall n Insertionen und n * (n-1) Elementbewegungen (die Insertionen sind), während Mergesort kopiert immer Zellen von einem Array in ein anderes, da es eine relativ kleine Zahl ist, macht es keinen Sinn, es zu betrachten.

---