Quicksort ohne Rekursion?

Hi,

gibt es eine Möglichkeit QuickSort ohne Rekursion hinzukriegen? Theoretisch müsste es doch gehen, aber wie geht es Praktisch?

void Quicksort(DWORD dwLow, DWORD dwHigh) {
  //Die Indizes in das zu sortierende Array initialisieren
  int iTop = dwLow;
  int iBottom = dwHigh - 1;
  int iPartitionIndex = 0;
  int iPartitionValue = 0;

  //Wenn Low >= High, muss nichts getan werden (wie auch...)
  if (dwLow < dwHigh) {
  //Wenn die Elemente direkt hintereinander liegen, ist die unterste Sortierebene erreicht
    if (dwHigh == (dwLow + 1)) {
      if(Compare(List[dwLow], List[dwHigh])) {
        SwapElements(List, dwHigh, dwLow);
      }
    }else {
      //Ein Partition Element auswählen und an die letzte Position im Array schieben
      //(damit man es in Ruhe lassen kann)
      iPartitionIndex = static_cast<int>((dwLow + dwHigh) / 2);
      iPartitionValue = List[iPartitionIndex];
      SwapElements(List, dwHigh, iPartitionIndex);
      do {
        //Den Top Index hochzählen, bis man ein Element gefunden hat, das größer ist,
        //als das Partition Element
        while (!Compare(List[iTop], iPartitionValue) && (iTop <= iBottom)) {
          iTop++;
        }
        //Den Bottom Index herunterzählen, bis man ein Element gefunden hat, das kleiner 
        //ist als das Partition Element
        while (Compare(List[iBottom], iPartitionValue) && (iTop <= iBottom)) {
          iBottom--;
        }
        //Wenn die Indizes sich nicht getroffen haben, werden die Elemente vertauscht
        if (iTop < iBottom) {
  SwapElements(List, iTop, iBottom);
        }
      } while (iTop < iBottom);

      //Das Partition Element wird auf seine finale Position gesetzt
      SwapElements(List, iTop, dwHigh);

      //Und die Funktion für die Teile rechts und links des Partition Elements aufgerufen
      QuickSort(dwLow, iTop - 1, Compare);
      QuickSort(iTop + 1, dwHigh, Compare);
    }
  }
}

Hat da jemand ahnung von oder ggf. sowas schonmal gemacht?

volkard

'#' schrieb:

gibt es eine Möglichkeit QuickSort ohne Rekursion hinzukriegen?

ja. indem man die rekursion durch einen künstlichen stack simuliert. brint aber nix, ist ja lahmer als der eingebaute stack.

Theoretisch müsste es doch gehen, aber wie geht es Praktisch?

praktisch tut man es nicht.

warum willst du es tun?

@volkard
Ignorier diesen Deppen da der direkt unter dir gepostet hat.

Warum? Ich hab gehört das es eine Rekursionstiefe gibt welche bei zu hoher Rekursionsausführung abbricht. Auch das die daten direkt im cach landen und wenn dieser zu klein ist das es dann rummms macht.

volkard

'#' - the real schrieb:

@volkard
Ignorier diesen Deppen da der direkt unter dir gepostet hat.

hab ihn gelöscht.

Warum? Ich hab gehört das es eine Rekursionstiefe gibt welche bei zu hoher Rekursionsausführung abbricht.

das ist der fall. dein stack hat vermutlich nur 1M. wenn quicksort pech hat und in den worst case geht, würde das rumms machen, wenn das feld ein wenig größer ist. aber wenn quicksort glück hat und die feldgröße bei jedem weiteren rekursionslevel halbiert wird, kannste mit 30 levels gleich 2^30 datensätze sortieren.

Auch das die daten direkt im cach landen und wenn dieser zu klein ist das es dann rummms macht.

wenn der chache zu klein ist, wirds langsamer. aber das ist eher nicht so relevant.

alles, was wir brauchen, ist glück, daß wir mit jedem teiferen level die arraygröße halbieren. da gibts sogar einen trick, daß die arraygröße sich mindestens halbiert.

dein code:

void Quicksort(DWORD dwLow, DWORD dwHigh) {
:anfang
//ganz viel weggelassen
      //Und die Funktion für die Teile rechts und links des Partition Elements aufgerufen
      QuickSort(dwLow, iTop - 1, Compare);
      QuickSort(iTop + 1, dwHigh, Compare);
    }
  }
}

mein code:

void Quicksort(DWORD dwLow, DWORD dwHigh) {
:anfang
//ganz viel weggelassen
      //Und die Funktion für die Teile rechts und links des Partition Elements aufgerufen
      QuickSort(dwLow, iTop - 1, Compare);
      dwLow=iTop+1;
      dwHigh=dwHigh;
      goto anfang;
    }
  }
}

also ein unteraufruf wird rekursiv gemacht und einer wird zu nem schleifensprung umgemodelt.
schleifen kann der computer ja ohne schmerzen viele ausführen.

außerdem hat keiner gesagt, welchen der beiden unteraufrufe du zuerst abarbeiten mußt. mach es so: arbeite zuerst rekursiv das kleinere unterfeld ab und dann per schleife das größere. das garantiert, daß du bei jeder neuen rekursionstiefe die feldgröße mindestens halbiert hat. hast also bei 1 milliarde datensätzen eine rekursionstiefe von höchstens 30. bist auf der sicheren seite damit.