So messen Sie die Sortiertheit

34

Ich frage mich, ob es eine Standardmethode zum Messen der "Sortierbarkeit" eines Arrays gibt. Würde ein Array mit der mittleren Anzahl möglicher Inversionen als maximal unsortiert betrachtet werden? Damit meine ich, dass es so weit wie möglich von einer Sortierung oder umgekehrten Sortierung entfernt ist.

Robert S. Barnes
quelle

Antworten:

31

Nein, das hängt von Ihrer Anwendung ab. Die Sortierbarkeitsmaße werden oft als Unordnungsmaße bezeichnet , die Funktionen von bis , wobei die Sammlung aller endlichen Folgen verschiedener nichtnegativer Ganzzahlen ist. Die Umfrage von Estivill-Castro und Wood [1] listet und diskutiert 11 verschiedene Störungsmaße im Kontext adaptiver Sortieralgorithmen.N<NRN<N

Die Anzahl der Inversionen kann in einigen Fällen funktionieren, ist jedoch manchmal unzureichend. Ein Beispiel in [1] ist die Sequenz

n/2+1,n/2+2,,n,1,,n/2

das hat eine quadratische Anzahl von Inversionen, besteht aber nur aus zwei aufsteigenden Läufen. Es ist fast sortiert, aber dies wird nicht durch Inversionen erfasst.


[1] Estivill-Castro, Vladmir und Derick Wood. "Eine Übersicht über adaptive Sortieralgorithmen." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

Juho
quelle
2
Der Kontext versucht zu verstehen, warum Quicksort bei zufälligen Permutationen von n Elementen relativ schlecht abschneidet, wenn die Anzahl der Inversionen nahe am Median liegt.
Robert S. Barnes
1
Tolles Beispiel, das ist genau die Information, nach der ich gesucht habe.
Robert S. Barnes
1
Estivill-Castro and Wood ist mit Sicherheit DIE Referenz dafür.
Pedro Dusso
10

Mannila [1] axiomatisiert die Vorsortierung (mit Schwerpunkt auf vergleichenden Algorithmen) wie folgt (Paraphrasierung).

Sei ein total geordneter Satz. Dann ist eine Abbildung m von Σ Σ (die Folgen verschiedener Elemente von Σ ) auf die Naturtöne ein Maß für die Vorsortierung, wenn sie die folgenden Bedingungen erfüllt.ΣmΣΣ

  1. Wenn ist, ist m ( X ) = 0 .XΣm(X)=0

  2. Wenn mit X = x 1x n , Y = y 1y n und x i < x iX,YΣX=x1xnY=y1yn für alle i , j [ 1 .. n ] , dann ist m ( X ) = m ( Y ) .xi<xiyi<yjich,j[1 ..n]m(X)=m(Y.)

  3. Wenn eine Subsequenz ist Y & Sigma; , dann m ( X ) m ( Y ) .XY.Σm(X)m(Y.)

  4. Wenn für alle i [ 1 .. | X | ] und j [ 1 .. | Y | ] Für einige X , Y & Sigma; , dann m ( X Y ) m ( X ) + m ( Y ) .xich<yjich[1 ..|X|]j[1 ..|Y.|]X,Y.Σm(XY.)m(X)+m(Y.)

  5. für alle X & Sigma; und a E X .m(einX)|X|+m(X)XΣeinEX

Beispiele für solche Maßnahmen sind die

  • Anzahl der Inversionen,
  • Anzahl der Swaps,
  • die Anzahl der Elemente, die keine von links nach rechts verlaufenden Maxima sind, und
  • die Länge einer am längsten ansteigenden Subsequenz (subtrahiert von der Eingabelänge).

Beachten Sie, dass Zufallsverteilungen mit diesen Maßen definiert wurden, dh so, dass Sequenzen, die mehr oder weniger sortiert sind, mehr oder weniger wahrscheinlich sind. Diese werden Ewens-ähnliche Verteilungen genannt [2, Kap. 4-5; 3, Beispiel 12; 4], ein Sonderfall davon ist die sogenannte Mallows- Verteilung. Die Gewichte sind parametrisch in einer Konstanten und erfüllenθ>0

.Pr(X)=θm(X)Y.ΣΣ|X|θm(Y.)

Man beachte, wie die gleichmäßige Verteilung definiert (für alle m ).θ=1m

Da es möglich ist, Permutationen für diese Kennzahlen effizient abzutasten, kann diese Arbeit in der Praxis beim Benchmarking von Sortieralgorithmen hilfreich sein.


  1. Messungen der Vorsortierung und optimale Sortieralgorithmen von H. Mannila (1985)
  2. Logarithmische kombinatorische Strukturen: ein probabilistischer Ansatz von R. Arratia, AD Barbour und S. Tavaré (2003)
  3. Über das Hinzufügen einer Liste von Zahlen (und anderer einseitiger determinanter Prozesse) von A. Borodin, P. Diaconis und J. Fulman (2010)
  4. Ewens-ähnliche Verteilungen und Analyse von Algorithmen von N. Auger et al. (2016)
Raphael
quelle
3

Ich habe meine eigene Definition von "Sortierbarkeit" einer Sequenz.

Bei gegebener Folge [a, b, c,…] vergleichen wir sie mit der sortierten Folge, die dieselben Elemente enthält, zählen die Anzahl der Übereinstimmungen und dividieren sie durch die Anzahl der Elemente in der Folge.

Zum Beispiel [5,1,2,3,4]gehen wir bei gegebener Reihenfolge wie folgt vor:

1) sortiere die Reihenfolge: [1,2,3,4,5]

2) Vergleichen Sie die sortierte Sequenz mit dem Original, indem Sie sie jeweils um eine Position verschieben und die maximale Anzahl der Übereinstimmungen zählen:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) Die maximale Anzahl von Übereinstimmungen ist 4, wir können die "Sortierbarkeit" als 4/5 = 0,8 berechnen.

Die Sortierbarkeit einer sortierten Sequenz wäre 1, und die Sortierbarkeit einer Sequenz mit in umgekehrter Reihenfolge angeordneten Elementen wäre 1 / n.

Die Idee hinter dieser Definition ist es, den minimalen Arbeitsaufwand abzuschätzen, der erforderlich ist, um eine Sequenz in die sortierte Sequenz umzuwandeln. Im obigen Beispiel müssen wir nur ein Element, die 5, verschieben (es gibt viele Möglichkeiten, aber das Verschieben von 5 ist am effizientesten). Wenn die Elemente in umgekehrter Reihenfolge platziert würden, müssten wir 4 Elemente verschieben. Und wenn die Reihenfolge sortiert wurde, ist keine Arbeit erforderlich.

Ich hoffe meine Definition macht Sinn.

Andrushenko Alexander
quelle
Gute Idee. Eine ähnliche Definition ist Exc, die dritte Definition von Störung in dem in Juhos Antwort erwähnten Aufsatz . Exc ist die Anzahl der Operationen, die erforderlich sind, um eine Sequenz in eine sortierte Reihenfolge zu bringen.
Apass.Jack
Nun, vielleicht habe ich gerade mein Verständnis von Entropie und Unordnung auf die Abfolge der Elemente
angewendet
-2

Wenn Sie etwas schnelles und schmutziges brauchen (Summationszeichen machen mir Angst), habe ich in C ++ eine super einfache Unordnungsfunktion für eine Klasse namens Array geschrieben, die int-Arrays erzeugt, die mit zufällig generierten Zahlen gefüllt sind:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

Function vergleicht einfach den Wert in jedem Element mit dem Index des Elements + 1, sodass ein Array in umgekehrter Reihenfolge einen Unordnungswert von 1 und ein sortiertes Array einen Unordnungswert von 0 hat.

Michael

Michael Sneberger
quelle
Dies ist keine Programmierseite. Es hätte gereicht, den Störungsbegriff zu definieren und zu erwähnen, dass er in linearer Zeit berechnet werden kann.
Yuval Filmus