Besten

Ik hou me wat bezig met C# en heb deze sorteer algoritmes gevonden in verband met array's (tabellen) voor C#. Het probleem is nu dat ik wel het globale idee er achter versta maar ik zou graag weten wat elke regel code doet voor sommige dingen versta ik wel de basis. Maar ik graag niet echt wijs uit die variabelen.

Als iemand zo lief zou willen zijn om bij deze code comentaar te schrijven wat het effectief doet zou ik het echt appreciëren :good:



namespace ConsApp_Internal_Sorting_Basic
{
class ClsArrayOperations
{
public void FillArray(int[]T, int Max)
{
Random RndInt = new Random(12345);
for (byte I = 0; I < T.Length; I++)
{
T[I] = RndInt.Next(1, Max + 1);
}
} /* FillArray */

public void InsertionSort(int[]T)
{
int J, X; // local variables
for (int I = 1; I < T.Length; I++)
{
X = T[I];
J = I;
while ((J - 1 >= 0) && (X < T[J - 1]))
{
T[J] = T[J - 1];
J--;
}
T[J] = X;
}
} /* InsertionSort */

public void SelectionSort(int[]T)
{
int K, X;
for (int I = 0; I < T.Length - 1; I++)
{
K = I;
X = T[K];
for (int J = I + 1; J < T.Length; J++)
{
if (T[J] < X)
{
K = J;
X = T[K];
}
}
T[K] = T[I];
T[I] = X;
}
} /* SelectionSort */

public void ExchangeSort(int[]T)
{
int X;
for (int I = T.Length - 1; I >= 1; I--)
{
for(int J = 0; J < I; J ++)
{
if(T[J] > T[J+1])
{
X = T[J];
T[J] = T[J+1];
T[J+1] = X;
}
}
}
} /* Exchange Sort */

InsertionSort, SelectionSort en ExchangeSort zijn allemaal verschillende sorteeralgoritme. Maar deze worden eigenlijk nooit gebruikt in het dagelijkse leven. Dat zijn de "makkelijke" algoritmes voor een array te sorteren. ;)
Die algoritmes zijn meestal goed voor arrays met een korte lengte. Maar als de array vrij lang begint te worden, dan gaan die algoritmes te traag zijn.

InsertionSort gaat eigenlijk de hele array doorlopen (for lus). En bij elk element dat hij tegenkomt, gaat hij kijken waar hij moet plaatsen om de array van klein -> groot te sorteren. En dan zal hij die daar plaatsen. (while lus)

En als hij op het einde van de for lus komt, is de array gesorteerd.

Qua tijdscomplexiteit:
Worst case performance: О(n2)
Best case performance: O(n )
Average case performance: О(n2)


******

Selection Sort gaat de array element per element af, op zoek naar het minimum. Als hij het minimum heeft gevonden. Dan vervangt hij dat met 'eerste' element van de array.

Dan doorloopt hij de array nog een keer, maar zegt dan dat de array begint van plaats "2". Omdat element 1 al juist staat. Het minimum dat hij dan vindt is dus eigenlijk het tweedde grootste getal. En komt dus op de tweedde plaats in de array.

De derde keer dat hij de array doorzoekt naar het minimum, begint hij het minimum te zoeken vanaf plaats 3, deze keer. En op die manier, wordt de array dus volledig gesorteerd uiteindelijk.

Het zoeken van het minimum is die tweedde for lus. Na het uitvoeren van de lus, bevat X het minimum. Dan wordt deze code uitgevoerd, alvorens een nieuwe lus te beginnen:

T[K] = T[I];
T[I] = X;

Dat is dat "switchen" waarover ik het had. Het getal op plaats 1 gaat naar plaats "K", waar dus het minimum staat. En het minimum komt op plaats "I". Dat is dus de eerste plaats.

"Eerste plaats" is relatief. Aangezien die "I" altijd verhoogd wordt met 1. "Eerste plaats in het niet gesorteerde deel van de array" is eigenlijk de beste benaming.

Worst case performance: O(n²)
Best case performance: O(n²)
Average case performance: O(n²)

Dit is hopelijk wat duidelijker:
http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif

******

Exchange Sort of Bubble Sort is al een iets beter algoritme, maar nog steeds niet echt goed.

Dit algoritme gaat element op positie "n" vergelijken met element op positie "n+1". Als het element op positie "n" groter is dan die op "n+1" dan worden ze omgewisseld. En wordt "n" met 1 verhoogd.

Zo wordt dus bij elke "pass" van deze for lus:
for (int I = T.Length - 1; I >= 1; I--)

Het grootste element achteraan gezet.

De andere for lus, heeft gewoon als doel, om de hele array te doorlopen, om element "n" met "n+1" te vergelijken en om te wisselen indien nodig.

Worst case performance O(n2)
Best case performance O(n )
Average case performance O(n2)

*********

Exchange Sort uitleg:
http://nl.wikipedia.org/wiki/Bubblesort
Insertion Sort uitleg:
http://nl.wikipedia.org/wiki/Insertion_sort
Selection Sort uitleg:
http://nl.wikipedia.org/wiki/Selection_sort

Mvg,
Dave

Beste

Bedankt voor deze aanvulling. Meestal kan ik ongeveer wel afleiden uit de code wat het doet. Maar kan ik niet verantwoorden wat elke regel nu eigenlijk doet met andere woorden ik kijk een beetje scheel op al die variabelen.

Bij mijn opinie is Bubble sort het zwakste algoritme van allemaal omdat je eerst gaat vergelijken en dan maar gaat switchen. Alhoewel zijn verbeterde broer Quicksort de snelste is in zijn soort.

Een eventuele verdere analyse van de code is natuurlijk altijd welkom :p

Hier heb je al de insertion sort, de rest kan ik nog niet doen wegens tijdgebrek. Maar de code is echt wel eenvoudig te interpreteren ;) Als je het niet ziet maak dan eens op papier een eenvoudige array waarvoor je stap per stap het algoritme doorloopt.

public void InsertionSort(int[]T)
{
int J, X; // local variables
for (int I = 1; I < T.Length; I++) //de te sorteren array T wordt overlopen
{
X = T[I]; //Voor elke lus komt het volgende element in X te staan
J = I; //J is de positie in de array
while ((J - 1 >= 0) && (X < T[J - 1]))
//zolang het huidige element NIET op de eerste plaats staat EN
//het huidige element is kleiner dan het voorgaande element
{
T[J] = T[J - 1]; //schuif het huidige element 1 plaats naar voor
J--;//geef aan dat het huidige element verplaatst is
}
T[J] = X; // het J-de element in de array wordt X
}
} /* InsertionSort */

Zeer bedankt voor deze aanvulling.

IK zou het apprecieren als de andere twee ook op deze manier kunnen worden voorzien van commentaar.

Ik zal het zelf eens proberen het te doen anders moet ik jullie blijven lastigvallen :P. Zal dan wel later me hersinskronkels posten.

Het is zo dat ik meestel wel het algoritme kan analyseren wat het doet en wat de efficiente er van is. Maar raar maar waar ik graak niet wijs uit de variabelen :P

Graak nog steeds niet uit die leuke variabelekes woop woop