 Korrektheitsbeweis Selection-Sort |
JaJaSoIstDasMitDerUni
unregistriert
 |
|
| Korrektheitsbeweis Selection-Sort |
     |
Ja also im Fach Experimentelle Algorithmik haben wir unter Anderem die Aufgabe die Korrektheit des Algorithmus Selection-Sort zu beweisen. Glücklicherweise dürfen wir diese Aufgabenstellung oberflächlich beantworten, weswegen ich nochmal den Prof gefragt habe was das bedeutet und die folgenede Antwort bekam:
'Meine Empfehlung wäre, sich einfach folgende Frage zu stellen: "Wie könnte ich einen Kommilitonen, der sich zwar vielleicht fürs Programmieren interessiert, aber nicht besonders für Mathematik oder für Korrektheitsbeweise, ÜBERZEUGEN, dass der Algorithmus funktioniert?" Stellen Sie sich diese Situation einfach vor bzw. versuchen Sie sich einfach im Team gegenseitig von der Korrektheit zu überzeugen. Man könnte auch nur mit Beispielen arbeiten. Oder man könnte ordentlich beweisen, dass nach dem 1. Schritt ein bestimmtes Teilproblem gelöst wurde, und dann einfach nur noch sagen "Und der Rest geht dann analog". So was in die Richtung.'
Ich wäre euch im folgenden total dankbar wenn ihr mir schamlos einfach eine Lösung präsentiert, denn ich bin zwar im Stande diese im Nachhinein zu verstehen, aber Sie selber zu erzeugen vermag ich sie momentan leider nicht. Glücklicherweise ist uns um Hilfe zu fragen explizit erlaubt.
"Und übrigens: Es wurde auch nie verlangt, dass Sie sich alles selbst ausdenken müssen. Es ist erlaubt, Teilaspekte in einschlägiger Literatur nachzuschlagen und zu verwenden -- solange Sie es selbst verstanden haben und gut erklären können und die Quelle nennen."
Hier sind die Varianten von Selection-sort die wir verwenden (C):
void sort(Elements& e, const unsigned int left,
const unsigned int right) const
{
int min;
for (int i = left; i < right; i++)
{
min = i;
for (int j = i + 1; j <= right; j++)
{
if (e[j] < e[min]) min = j;
}
e.swap(min, i);
}
}
Danke im Vorraus und liebe Grüße!
|
|
18.11.2016 13:46 |
|
|
JaJaSoIstDasMitDerUni
unregistriert
|
|
Das hier ist die zweite Variante:
void sort(Elements& e, const unsigned int left,
const unsigned int right) const
{
for (unsigned minIndex = 0, maxIndex = right; minIndex < maxIndex
{
Element min = e[minIndex];
Element max = e[maxIndex];
unsigned newMinIndex = minIndex + 1;
unsigned newMaxIndex = maxIndex;
for (unsigned index = newMinIndex; index <= newMaxIndex
{
Element value = e[index];
if (value <= min)
{
if (value < min)
{
min = value;
newMinIndex = minIndex;
e[index] = e[newMinIndex];
}
else
{
e[index] = e[newMinIndex];
++index;
}
e[newMinIndex] = value;
++newMinIndex;
}
else if (value >= max)
{
if (value > max)
{
max = value;
newMaxIndex = maxIndex;
}
e[index] = e[newMaxIndex];
e[newMaxIndex] = value;
--newMaxIndex;
}
else ++index;
}
minIndex = newMinIndex;
maxIndex = newMaxIndex;
}
}
Wenn ihr mir nur mit dem ersten helfen könnt wäre das auch schon total super.
lG
|
|
|
18.11.2016 13:55 |
|
|
JaJaSoIstDasMitDerUni
unregistriert
|
|
| Oh man die einrückungen verschwinden ja! |
|
Verdammt :x
|
|
|
18.11.2016 13:56 |
|
|
|
