Quicksort mit einem rekursiven Aufruf

Al von uns kann Quicksort mit zwei oder mehr rekursiven Aufrufe schreiben.Quicksort mit einem rekursiven Aufruf

Vor ein paar Tagen sagte Lehrer, dass es möglich ist, es mit einem rekursiven Aufruf zu machen. Eigentlich habe ich keine Ahnung, wie man O (n log n) mit nur einem rekursiven Aufruf speichern kann.

Irgendwelche Ideen?

Quelle

2016-10-25 openspace

kann eine der zwei rekursive Aufrufe machen eine tailcall sein, die (beseitigt werden kann:

void QuickSort(int a[], size_t lo, size_t hi) { while(lo < hi){ size_t i = lo, j = (lo+hi)/2, k = hi; int p; if (a[k] < a[i]) // median of 3 std::swap(a[k], a[i]); if (a[j] < a[i]) std::swap(a[j], a[i]); if (a[k] < a[j]) std::swap(a[k], a[j]); p = a[j]; i--; // Hoare partition k++; while (1) { while (a[++i] < p); while (a[--k] > p); if (i >= k) break; std::swap(a[i], a[k]); } i = k++; while(i > lo && a[i] == p) // exclude middle values == pivot i--; while(k < hi && a[k] == p) k++; // recurse on smaller part, loop on larger part if((i - lo) <= (hi - k)){ QuickSort(a, lo, i); lo = k; } else { QuickSort(a, k, hi); hi = i; } } }

Um nur einen einzigen rekursiven Aufruf im Code haben, kann der letzte Teil ersetzt werden in Iteration statt Rekursion). – EOF

Das ist fast so, als würde man mit einer Schleife die beiden rekursiven Aufrufe machen. Nicht sicher, was gut ist. –

versuchen http://stackoverflow.com/questions/19094283/quicksort-and-tail-recursive-optimization? – nephi12

Beispiel C++ - Quicksort mit einem rekursiven Aufruf pro Iteration, um den Stack-Overhead auf O zu reduzieren (log (n)). Verwendet auch den Medianwert 3 für Pivot und schließt den mittleren Wert von Partition == Pivot aus.

Sie

 // recurse on smaller part, loop on larger part 
     size_t ll, rr; 
     if((i - lo) <= (hi - k)){ 
      ll = lo; 
      rr = i; 
      i = hi; 
     } else { 
      ll = k; 
      rr = hi; 
      k = lo; 
     } 
     QuickSort(a, ll, rr); 
     lo = k; 
     hi = i; 
    } 
}

Quelle

2016-10-26 04:54:53 rcgldr

Technisch gesehen haben Sie immer noch zwei rekursive Aufrufe –

@BasileStarynkevitch - ein rekursiver Aufruf pro Iteration, um einen Stack-Überlauf zu vermeiden, ansonsten zeigt der Link von Nephi12 ein rekursives Aufrufbeispiel. – rcgldr

@BasileStarynkevitch, wenn anstelle des rekursiven Aufrufs zum kleineren Stück es auf den ersten Teil (unabhängig von der Größe) vorgegangen wird, erhalten Sie nur einen rekursiven Aufruf ... Technisch ist die Schleife eine andere Form der Rekursion, die übrigens ist man nimmt einen der rekursiven Aufrufe ab. Recht? Sie erhalten zwei Anrufe in der Liste, aber Sie erhalten nie beide im selben Anruf angerufen. –

Quicksort mit einem rekursiven Aufruf

Antwort

Verwandte Themen