Asymptotische Laufzeit von Sortieralgorithmen

Question

Aufgabe:

Bestimme für Insertion Sort, Bubble Sort und Selection Sort asymptotisch exakt in der Form Θ(·) jeweils die Anzahl der Vergleiche und die Anzahl der Vertauschungen auf den folgenden Eingaben:

a)1, N,2, N−1,3, N−2, . . .

b)N, N−1,2,1,4,3,6,5, . . . , N−4, N−5, N−2, N−3

Hinweis:Es kann angenommen werden, dass N= 2k für ein k∈N

Problem/Ansatz:

Mir ist nicht klar, wie man hier vorgehen soll. Ich weiß, dass die Sortieralgorithmen eine erwartete Laufzeit von Θ (n²) haben und in n-1 Phasen  n- i Vergleiche durchgeführt werden.

Jetzt wollte ich bei a) für Insertion-Sort durchgehen. Angenommen N sei 6. Dann wäre die zu sortierende Folge

1,6,2,5,3,4

Insertion-Sort ergäbe folgende Umsortierung

1,6,2,5,3,4

1,6,2,5,3,4

1,2,6,5,3,4

1,2,5,6,3,4

1,2,3,5,6,4

1,2,3,4,5,6

Insgesamt wären es 6 Vertauschungen, also n Vertauschungen. Die Vergleiche wären, wenn ich richtig gezählt habe 4. Vorausgesetzt, man muss eine bereits richtig einsortierte Zahl nicht erneut mit Vor- und Nachfolger vergleichen (Hier bin ich nicht sicher).

Aber wähle ich jetzt N = 8, dann hätte die zu sortierende Folge 1,8,2,7,3,6,4,5 und laut meiner Zählung 12 Vertauschungen, also n + 4. Ich erkenne hier kein Muster.

Evtl. wäre noch ein möglicher Ansatz, da ja in der Folge 1,N,2,N-1,3,N-2 immer eine extrem große auf eine extrem kleine Zahl folgt, dass die extrem große Zahl immer fast den kompletten Weg durchlaufen muss, also n-1 Wege, d.h. Θ (n²). Das ist aber auch schon aus der Definiton bekannt.

b) Hier habe ich es auch ausprobiert, in dem ich die Folge 12,11,2,1,4,3,6,5,8,7,10,9 genommen habe, da sie die Bedingung N, N−1,2,1,4,3,6,5, . . . , N−4, N−5, N−2, N−3 genau erfüllt. Durch Zählen komme ich auf 26 Vertauschungen (2n + 2) und 34 Vergleiche. Aber das ist leider auch nicht der wahre Hugo. Ein Ansatz wäre noch, dass hier ja das größte Element N ganz am Anfang steht, also bei Insertion-Sort jedes Mal nach hinten geschoben wird. Das würde dann wieder für n Wege, also aufsummiert Θ (n²) sprechen.

Egal wie ich es drehe, ich komme durch Testen immer auf völlig unterschiedliche Wege und durch Nachdenken immer nur auf Θ (n²). Bei Bubble- und Selection Sort analog.

Hat jemand einen Ansatz, wie man hier vorgeht.

LG

Marcy

Comments

Hallo Marcy, diese Frage gehört eigentlich nach www.stacklounge.de, die Informatik Platform.  

Answer 1

Meiner Ansicht nach ist es nicht möglich, die Anzahl der Vergleiche und Vertauschungen rein kombinatorisch zu ermitteln. Es ist einfacher, die Sortierungen per Programm zu implementieren und die Vergleiche und Vertauschungen mitzuzählen. Dabei kommt folgendes heraus:

Bubble-Sort a) Anzahl Vergleiche N*(N-1)/2, Anzahl Vertauschungen ~ N*(N-1)/4

Selection-Sort a) Anzahl Vergleiche N*(N-1)/2, Anzahl Vertauschungen N-1
Insertion-Sort a) Anzahl Vergleiche N*(N-1)/4, Anzahl Vertauschungen ~ N*(N-1)/4

Die Reihenfolge der Array-Elemente im Fall b) ist unklar. Dazu einfach die Routine Array_Fill_a() anpassen.

Hier das Programm:

#include <iostream>

#define Array_Size 1024

int Array[Array_Size];
int Array_Len;
int Vergleiche;
int Vertauschungen;

void bubbleSort();
void selectionSort();
void insertionSort();

int minimum ( int anfang );
void Array_Fill_a( );
void Array_Vertausche ( int indexA, int indexB );

int main ()
{
  std::cout << "Bubble-Sort" << std::endl;

  for (Array_Len=16; Array_Len < Array_Size; Array_Len+=16)
  {
    Array_Fill_a( );
    bubbleSort();

    std::cout << "N: " << Array_Len << " Vergleiche: " << Vergleiche << " Vertauschungen: " << Vertauschungen << std::endl;
  }

  std::cout << "Selection-Sort" << std::endl;

  for (Array_Len=16; Array_Len < Array_Size; Array_Len+=16)
  {
    Array_Fill_a(  );
    selectionSort();

    std::cout << "N: " << Array_Len << " Vergleiche: " << Vergleiche << " Vertauschungen: " << Vertauschungen << std::endl;
  }

  std::cout << "Insertion-Sort" << std::endl;

  for (Array_Len=16; Array_Len < Array_Size; Array_Len+=16)
  {
    Array_Fill_a(  );
    insertionSort();

    std::cout << "N: " << Array_Len << " Vergleiche: " << Vergleiche << " Vertauschungen: " << Vertauschungen << std::endl;
  }

  return 0;
}

void bubbleSort ()
{
  bool sortiert;

  Vergleiche = 0;
  Vertauschungen = 0;

  do 
  {
    sortiert = true;
    for (int i=1; i<Array_Len; i++) 
    {
      Vergleiche++;

      if (Array[i-1]>Array[i]) 
      {
        Array_Vertausche( i-1, i);
        Vertauschungen++;

        sortiert=false;
      }
    }
  } while (!sortiert);
}

void selectionSort () 
{
Vergleiche = 0;
Vertauschungen = 0;

 for (int index=0; index < Array_Len-1; index++) 
 {
  int minIdx = minimum( index );
  Array_Vertausche(index,minIdx);
  Vertauschungen++;
 }
}

void insertionSort () 
{
  Vergleiche = 0;
  Vertauschungen = 0;

  for (int j=1; j < Array_Len-1; j++) 
  {
    int key = Array[j];
    int i = j-1;
    while (i>=0 && Array[i]>key) 
    {
      Vergleiche++;

      Array[i+1] = Array[i];
      i = i-1;
      Vertauschungen++;
    }

    Array[i+1] = key;
    Vertauschungen++;
  }
}

int minimum ( int anfang ) 
{
  int minIdx = anfang;
  for (int index=anfang+1; index < Array_Len; index++) 
  {
  Vergleiche++;

    if (Array[index] < Array[minIdx]) 
    minIdx = index;
  }
  return minIdx;
}

void Array_Fill_a()
{
 int start = 1;

 for (int i = 0; i < Array_Len; i+=2)
 {
  Array[i] = start;
  Array[i+1] = Array_Len+1-start;

  start++;
 }
}

void Array_Vertausche ( int indexA, int indexB )
{
  int tmp;

  tmp=Array[indexA];
  Array[indexA]=Array[indexB];
  Array[indexB]=tmp;
}

Comments

Danke für die ausführliche Antwort, inklusive den Code.

Wir müssen so etwas leider in Klausuren "händisch" lösen, also ohne Programme laufen zu lassen. Ich versteh' nicht so recht, wie man z.B. bei Insertion-Sort auf eine Anzahl der erwarten Vergleiche von (N/(N-1))/4 kommen soll. Sind das die Summe aller Zahlen, geteilt durch 2?  Weil die Summe aller Zahlen wäre ja (N/(N-1))/2.  Und weil hier durch 4 geteilt wird, daher die Hälfte. Weil man läuft ja 1, N, 2, N-1, 3, N-2. Und da man an 2. Stelle schon das N entdeckt, was das größte Element ist, muss man, wenn man die nachfolgenden Elemente einordnet, im Schnitt immer nur die Hälfte der Listnelemente vertauschen. Also die erwartete Anzahl der Vertauschungen wäre die Hälfte der Durchläufe?

Wir hatten das in der Vorlesung immer mit (N/(N-1)/2 => Θ (n²)

Wennn ich jetzt (N/(N-1)/4) habe, dann könnte man ja die Faktoren wie "/4" vernachlässigen und man käme asymptotisch wieder bei Θ (n²) raus?

---

Hallo Marceline, die Info aus eurer Vorlesung:
N*(N-1)/2 = Θ (n²)
ist korrekt.
Und
N*(N-1)/4 = Θ (n²)
ist auch korrekt.
Bitte beachte, dass du bei deinem Aufschrieb * und / verwechselt hast, und eine Klammer fehlt. 

---

Die Anzahl der Vergleiche bei Insertion-Sort im Fall a) ist N*(N-1)/4, weil die innere while-Schleife nur dann durchlaufen wird, wenn Array[i] > key gilt. Weil die Zahlenmenge bereits zur Hälfte vorsortiert ist, wird die while-Schleife nur bei jedem 2. Array-Element durchlaufen.

Völlig richtig, n^2 € O(n^2), N*(N-1)/2 € O(n^2),  N*(N-1)/4 € O(n^2), aber in der Aufgabe wird die exakte Laufzeit verlangt. Dass man diese theoretisch erarbeiten muss, ist kompletter Nonsense, denn was studiert Ihr eigentlich, und wozu gibt es Computer? Ist nicht persönlich gemeint, sondern wendet sich an den Lehrstuhl.

---

Ok, jetzt hab ich's verstanden. Vielen Dank :)