Hvad er Array sortering?
Array sortering er processen med at tage de individuelle elementer i en matrix og arrangere dem i en eller anden form for logisk rækkefølge i henhold til en række regler defineret af brugeren. Processen involverer at gå gennem arrayet, et element ad gangen og teste det element mod de omgivende elementer for at bestemme, om det skal flyttes til et andet indeks i arrayet. Når du udfører array-sortering, er der flere algoritmer, der kan bruges, især når sorteringsbetingelserne er numeriske i modsætning til noget mere vilkårligt. De fleste array-sorteringsalgoritmer måles ud fra deres hastighed og effektivitet, idet de langsomste algoritmer er den nemmeste at programmere, og den hurtigste er meget mere kompleks.
Den enkleste array-sorteringsalgoritme kaldes en boble sortering, og den er også den langsomste. Processen begynder med en løkke, der træder gennem hvert element i matrixen. Det aktuelle element sammenlignes med det næste element i matrixen, og hvis det næste element har lavere værdi end det aktuelle element, skiftes dataene ved indekserne. Ulempen ved en boble-sortering er, at den er nødt til at løbe gennem matrixen flere gange for at foretage alle de nødvendige swaps for at sortere matrixen. I de mest basale implementeringer løber sorteringen gennem hele matrixen en komplet tid for hvert element, den indeholder.
En udvælgelsessort bruger en algoritme, der udfører array-sortering på en lidt mere effektiv måde end en boble-sortering, men stadig kræver flere iterationer gennem matrixen. Denne sortering starter med at sløjfe gennem matrixen for at finde det lavest værdsatte element. Dette element placeres derefter i det første indeks i matrixen, og nogle sporingsvariabler øges. Cyklussen gentages derefter og leder nu efter den næste laveste værdi, der derefter placeres i det andet indeks i arrayet. Processen fortsætter, indtil elementet med den højeste værdi er placeret i det sidste indeks i matrixen.
En metode til matrixsortering, der kan være effektiv, men sommetider kompleks at implementere, er kendt som en quicksort. Quicksorting indebærer, at man tager en værdi, der er midt i alle de mulige værdier, der findes i matrixen. Algoritmen går gennem alle elementerne i matrixen og sætter alle værdier større end mediantalet i slutningen af matrixen og lavere værdier i begyndelsen. Denne proces udføres rekursivt på blokke af arrayet, indtil i slutningen hele arrayet er sorteret. Hvis man antager, at den midterste værdi, der bruges til matrixen, er ret nøjagtig, kan dette være en meget hurtig måde at sortere.
En faktor, der kan påvirke en matrixsorteringsalgoritme, er det middel, hvorpå dataene testes for ækvivalens. Det er nemt at sammenligne enkle tal, som værdien er større, men dette er muligvis ikke tilfældet for komplekse dataklasser, hvor flere forhold skal sammenlignes. Jo længere tid det tager at sammenligne, om et element er større end eller mindre end et andet, desto længere tid tager det for algoritmen at sortere arrayet.