Sortering
Der findes mange sortering. Vi vil undersøge flere af disse, både simple og komplekse. Det er vigtigt at man forstår taktiken som de forskellige sorteringer bruger, før man begynder at kode. Lad os bare komme igang med det samme.
| Bubble Sort | |
|
Selv om Bubble Sort er den simpleste i følge litteraturen, så er den ret svær helt at forstå hvis man ikke har tænkt over sorterninger før. |
|
|
(1) Her til højre ser du et Array (arr) med længden 8 (0-7)og med følgende tal (6, 1, 4, 7, 9, 10, 2, 8). De er ikke sorterede. Det skal algoritmen gøre. Taktikken med bubble sort er at undersøge de to tal som er side om side. Og hvis den første er større en den anden, skal disse bytte plads. Her på billede ser du at jeg bruger to pile ( i og j) for at vise fremgangsmåden. I et program vil disse pile være int variabler. Nedenfor pilene ser du lidt kode, som laver arbejdet. I tilfælde her er i > j (6 > 1), og de skal så bytte plads, og i og j skal tælles ét op. Når dette arbejde er lavet kommer vi til næste billede. |
 |
| (2) Nu er vi kommet til 2. gennemløb, og vi ser at 6 og 1 har byttet plads, og i og j er flyttet ét op. Her sammenlignes nu 6 og 4, og vi har endnu en bytning, fordi 6 er større end 4. Og vi flytter igen i og j ét op. |
 |
| (3) Nu er vi kommet til 3. gennemløb, og vi ser at 6 og 4 har byttet plads, og i og j er flyttet ét op. Her sammenlignes nu 6 og 7, og nu skal der ikke byttes rundt, fordi 6 er ikke større end 7. Og vi flytter igen i og j ét op. |
 |
| (4) Nu er vi kommet til 4. gennemløb. Her skal der heller ikke byttes. Vi går videre. |
 |
| (5) Nu er vi kommet til 5. gennemløb. Her skal der heller ikke byttes. Vi går videre. |
 |
| (6) Nu er vi kommet til 6. gennemløb.Her skal der byttes igen fordi 10 er større end 2. |
 |
| (7) Nu er vi kommet til 7. gennemløb.Vi ser at 10 og 2 har byttet plads, og nu skal 10 og 8 også til at bytte plads. |
 |
| (8) Nu er vi kommet til 8. gennemløb. 10 og 8 har nu byttet plads, og vi er færdige med itteration 1 og i og j er sat tilbage til start position. Jeg har tegnet en linje lige foran 10 tallet (pos 7). Denne linje indikerer noget specielt, nemlig at bag denne er alt i orden. Vi bøhver ikke mere komme hele vejen der hen, fordi 10 er nemlig det største tal i hele samlingen og har nu fundet sin endelige plads. Du bør her studere lidt hvordan det kan være at vi er sikre på at dette forholder sig sådan. Næste iteration vil nu køre én sammenligning mindre. Og når så den er færdi, vil næste iteration igen også lave en mindre sammenligning end denne lige før. Du hehøves ikke have denne linje, du kan sagtens bare gå hele vejen til slut for hver iteration, den vil ikke ødelægge noget, men den vil heller ikke lave noget konstruktiv. Men når du skal implimentere denne, kan du starte med ikke at have denne begrænsning, det er simplere at implimentere, og så kan du finpusse din løsning senere (lave den hurtigere). |
 |
| Kode | |
|
Læg mærke til at koden her ikke er helt som illustreret ovenover. Jeg syns at koden er endnu simplere end taktikken ovenover, fordi vi ikke behøves at tænke på slut linjen (det som er færdig sorteret). Taktikken i koden er simplere og er sådan: Når vi finder noget som skal byttes, bytter vi dette og så sætter vi i og j tilbage til start positionen. Skal der ikke byttes tælles i og j op med en lige som normalt. Eftersom man ligesom nullstiller i og j hvergang der bliver byttet, ved vi, at når vi kommer til sidste tal i arrayet, så må arrayet være sorteret. Vi kan således bare lave et tjekke om j er lig med sidste plads i arrayet, og er det det, så stopper algoritmen. Denne tjek laves i for loopen. Jeg har heller ikke en j variabel, kun en i. Så siger jeg bare i + 1, når jeg tænker j. Og koden har et nivo extra, nemlig objekter i stedet for int variabler. Det kan måske gøre koden en lidt mere kompleks, men taktikken er uændret. |
|
|
using System;
using System.Collections.Generic;
using System.Text;
namespace bubbleSort
{
class Program
{
static void Main(string[] args)
{
Sorter s = new Sorter();
}
}
class Sorter
{
Bil[] biler = new Bil[6];
public Sorter()
{
biler[0] = new Bil(6, "Karl");
biler[1] = new Bil(5, "Peter");
biler[2] = new Bil(4, "Jens");
biler[3] = new Bil(3, "Allan");
biler[4] = new Bil(2, "Hans");
biler[5] = new Bil(1, "Ole");
udskriv(biler);
viSorterer(biler);
udskriv(biler);
}
public void viSorterer(Bil[] arr)
{
Console.WriteLine();
Console.WriteLine("--------Bobbel Sort start--------------");
int operations = 0;
for (int i = 0; i < arr.Length - 1; i++)
{
operations++;
if (arr[i].tal > arr[i + 1].tal)
{
//Her bytter vi rundt.
Bil tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
//Helt tilbage til start.
i = -1;
}
}
Console.WriteLine(" Antal iterationer: " + operations);
Console.WriteLine("--------Bobbel Sort slut--------------");
Console.WriteLine();
}
public void udskriv(Bil[] biler)
{
Console.WriteLine("------Udskriv start------");
for (int i = 0; i < biler.Length; i++)
{
Console.WriteLine(biler[i].tal + " " + biler[i].navn);
}
Console.WriteLine("------Udskriv slut------");
}
}
class Bil
{
public int tal;
public string navn;
public Bil(int t, String n)
{
tal = t;
navn = n;
}
}
} |
|
| Output | |
 |
|
| Selection Sort | |
| (1) Alt det som er på venstre side af pilen i, er sorteret. Vi starter her hvor der intet er på venstre side, selvfølgelig. Pilen j, sættes til at holde samme position som i (pos=0 med værdien=9). Nu flytter pilen j sig hele vejen til slutningen og gemmer den position som holder den mindste værdi. |
 |
| (2) Nu er pilen j kommet helt til slut, og den indeholder pos=2, som er værdien=1, som passer med at være den mindste værdi. Nu skal værdien som i pil peger på og værdien som j pilen holder (pos=2), bytte plads. |
 |
| (3) Nu har de byttet plads. Så flyttes i pilen én til højre og j pilen får samme position. Se hvordan alt som er til venstre (kun værdien 1) er det mindste og sorteret. Pilen j kører nu igen helt til slutningen og finder den position som indeholder mindste værdi. |
 |
| (4) Her har j pilen ikke fundet nogen bedre kandidat en den som den startede med, så der behøves ikke at byttes. Pilen i flyter så igen én til højre og pilen j sættes til samme position |
 |
| (5) Pilen i peger på position 2 og det gør j pilen også. vi kan nu kører igen. Læg igen mærke til at alt på venstre side er sorteret og indeholder de mindste værdier fra arrayet. Hele taktikken med selection sort er denne, at man selecter fra højre og det til venstre er sorteret og i orden. Man skal altså ikke til at rode i de positioner som er lavere en i. Pilen j er klar til endnu engang at finde den mindste position i det resterende på højre side. |
 |
| (6) Pilen j er kommet til sidste plads og har fundet en kandidat i position 6. Værdierne i Pil j position og pil i position bytter nu plads. |
 |
| (7) Pil i er flyttet én til højre og peger nu på position 3. Læg mærke til at værdierne 9 og 3 har flyttet plads. Alt som er til venstre for pil i er stadigvæk sorteret og i orden. Pil j er klar til endnu en tur igennem resten af arrayet. Vi stopper her, fordi jeg tror at du har forstået taktikken med selection sort nu. Algoritmen stopper når i kommer til sidste position i arrayet. |
 |
| Kode | |
|
using System;
namespace SelectionSort
{
class Program
{
static void Main(string[] args)
{
Sortering sort = new Sortering();
int[] ar = { 9, 2, 1,4, 6, 5,3, 8 };
sort.printArray(ar);
ar = sort.selectionSort(ar);
sort.printArray(ar);
}
}
class Sortering
{
public void printArray(int[] ar)
{
Console.WriteLine("-----------------------");
foreach (int i in ar)
{
Console.WriteLine(i);
}
}
public int[] selectionSort(int[] ar)
{
for (int i = 0; i < ar.Length-1; i++)
{
int mindste = ar[i];
int swapPos = i;
//Finde den mindste. Læg mærke til: j = i.
for (int j = i; j < ar.Length ; j++)
{
if (mindste > ar[j])
{
mindste = ar[j];
swapPos = j;
}
}
//Swap
ar[swapPos] = ar[i];
ar[i] = mindste;
}
return ar;
}
}
} |
|
| Output | |
 |
|
| Merge Sort | |
| (1) Fra wikipedia kan følgende læses "Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945". Merge sort er lidt speciel i forhold til de andre som bubble sort, selection sort. Lad os kikke på hvordan den fungerer. Her til højre har vi et array med 4 elementer (tal) som er u-sorterede. Det første algoritmen gør er at splitte arrayet i 2 dele, som vises på næste billede. |
 |
| (2) Her har vi nu 2 array, begge er stadigvæk u-sorterede, og vi kan splitte dem endnu mere. Læg mærke til at vi hele tiden fokuserer på venstre side først. Det er den måde vi kommer til at implimentere merge sort, som en rekursiv algoritme. |
 |
| (3) Nu har vi splittet venstre side til 2 nye array. Men disse 2 array indeholder KUN ét element (tal), og er derfor sorterede. Man kan ikke splitte disse mere. Nu køres der en ny metode som vi kalder merge. Denne metode modtager 2 array og svarer med et sorteret array. Den kunne se sådan ud: public int[] merge(int[] a, int[]b) |
 |
| (4) Efter at merge har kørt, har vi nu et nyt array som indeholder 2 elementer og er nu sorteret. Så er tiden kommet til højre side, som stadigvæk er u-sorteret. |
 |
| (5) Der er nu lavet 2 nye array ud af det enkelte array med 2 elementer fra højre side. Vi kan ikke splitte disse 2 mere, og derfor kører merge metoden på disse og returnerer et samlet sorteret array, som vi ser på næste billede. |
 |
| (6) Sådan, nu har vi 2 array som hver i ser indeholder 2 elementer som er sorterede. Men vi er ikke helt færdige endnu. |
 |
| (7) Vi kører nu merge metoden på disse 2 sorterede arrays, som vil returnere et samlet sorteret array indholdende alle elementer fra de 2 arrays. |
 |
| (8) Algoritmen er nu færdig og er kommet tilbage til toppen, og vi har nu et sorteret array. |
 |
| Kode | |
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MergeSort
{
class Program
{
static void Main(string[] args)
{
MergeSort ms = new MergeSort();
int[] a = {9,2,1,4,6,5,3,8 };
ms.mergeSortRecursive(a);
}
}
class MergeSort
{
public void print(int[] ar)
{
// Console.WriteLine("----------");
int i = 0;
while (i < ar.Length)
{
Console.Write("[ "+ ar[i] + " ]");
i = i + 1;
}
Console.WriteLine();
}
public int[] mergeSortRecursive(int[] ar)
{
if (ar.Length == 1)
{
Console.WriteLine(" < STOP > kan ikke splitte mere. "); return ar;
}
Console.WriteLine("-----Skal til at splitte følgende array:"); print(ar);
int midt = ar.Length / 2;
int[] left = fyldArray(ar, 0, midt);
Console.WriteLine("-----split Result: Left"); print(left);
int[] right = fyldArray(ar, midt, ar.Length - midt);
Console.WriteLine("-----split Result: Right"); print(right);
Console.WriteLine("mergeSortRecursive(Left)");
left = mergeSortRecursive(left);
Console.WriteLine("mergeSortRecursive(Right)");
right = mergeSortRecursive(right);
Console.WriteLine("merge(Left, right) START");
Console.WriteLine("LEFT"); print(left);
Console.WriteLine("RIGHT"); print(right);
ar = merge(left, right);
Console.WriteLine("merge(Left, right) RESULT"); print(ar);
return ar;
}
public int[] fyldArray(int[] ar, int posStart, int length)
{
int[] svar = new int[length];
int i = 0;
while (i < length)
{
svar[i] = ar[posStart];
posStart++;
i++;
}
return svar;
}
public int[] merge(int[] a, int[] b)
{
int i, j, k;
i = j = k = 0;
int[] svar = new int[a.Length + b.Length];
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])
{
svar[k] = a[i];
i++;
k++;
}
else
{
svar[k] = b[j];
j++;
k++;
}
}
while (i < a.Length)
{
svar[k] = a[i];
i++;
k++;
}
while (j < b.Length)
{
svar[k] = b[j];
j++;
k++;
}
return svar;
}
}
} |
|
| Output | |
 |
|