Hoofdstuk 3: Sorteeralgoritmen

Sorteren is het proces van het herschikken van een reeks objecten om ze in een logische volgorde te plaatsen. Bijvoorbeeld, uw creditcardafschrift presenteert transacties in chronologische volgorde, en u plaatst uw boeken in alfabetische volgorde op uw boekenplank op basis van auteur en titel. Sorteren is een fundamentele bewerking in de informatica en speelt een cruciale rol in veel toepassingen. Er zijn verschillende klassieke sorteeralgoritmen die verschillende benaderingen van dit probleem belichamen.

In dit hoofdstuk bespreken we verschillende klassieke sorteermetoden en een belangrijke datastructuur die bekend staat als de prioriteitswachtrij. We beginnen met een bespreking van enkele elementaire sorteermetoden, waaronder selectiesorteer, invoersorteer en shellsorteer. Deze methoden worden op de juiste wijze gebruikt in veel toepassingen, maar voor grote problemen wenden we ons tot mergesorteer en quicksorteer, twee recursieve sorteeralgoritmen die kunnen worden gebruikt om enorme aantallen items te sorteren. We sluiten af met een bespreking van prioriteitswachtrijen en hun gebruik bij het sorteren en andere toepassingen.

Elementaire Sorteermethoden

De eenvoudigste sorteeralgoritmen voeren de volgende bewerkingen uit:

Selectiesorteer: Zoek het kleinste item en ruil het uit met de eerste vermelding, zoek dan het tweede kleinste item en ruil het uit met de tweede vermelding, enzovoort.
Invoersorteer: Neem elk item op zijn beurt en plaats het in de juiste positie tussen de reeds beschouwde items (waarbij ze gesorteerd blijven).

Deze bewerkingen weerspiegelen hoe mensen normaal gesproken sorteerklussen uitvoeren en zijn effectief voor kleine probleemgroottes. Ze schalen echter niet goed en worden onpraktisch voor het sorteren van grote arrays.

Selectiesorteer

Selectiesorteer is een eenvoudig sorteeralgoritme dat als volgt werkt: Zoek eerst het kleinste item in de array en ruil het uit met de eerste vermelding (zichzelf als de eerste vermelding al het kleinste is). Zoek dan het volgende kleinste item en ruil het uit met de tweede vermelding. Ga op deze manier door tot de hele array is gesorteerd.

De binnenste lus van de selectiesorteer...Hier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

De on sort wordt gebruikt om het minimale element in het ongesorteerde subarray a[i..N-1] te vinden. De index van het minimale element wordt opgeslagen in min. Vervolgens wordt a[i] uitgewisseld met a[min], waardoor het minimale element in zijn definitieve positie komt. Naarmate de index i van links naar rechts beweegt, zijn de elementen links van i in gesorteerde volgorde in het array en worden ze niet meer aangeraakt.

Hier is een implementatie van selectiesort in Java:

public static void selectionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        // Zoek het minimale element in het ongesorteerde subarray a[i..N-1]
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // Wissel a[i] en a[min] uit om het minimale element op zijn plaats te zetten
        exch(a, i, min);
    }
}

Selectiesort gebruikt ongeveer ~N^2/2 vergelijkingen en N uitwisselingen om een array van lengte N te sorteren. De uitvoeringstijd is ongevoelig voor de invoer - het duurt ongeveer even lang om selectiesort uit te voeren voor een array die al in volgorde is of voor een array met alle sleutels gelijk als voor een willekeurig geordende array.

Insertiesort

Insertiesort is een ander eenvoudig sorteeralgoritme dat werkt door het uiteindelijke gesorteerde array stap voor stap op te bouwen. Het is veel minder efficiënt voor grote arrays dan geavanceerdere algoritmen zoals quicksort, heapsort of mergesort, maar het heeft enkele voordelen:

Het is efficiënt voor kleine datasets.
Het is in de praktijk efficiënter dan selectiesort.
Het is stabiel; d.w.z. het verandert de relatieve volgorde van elementen met gelijke sleutels niet.
Het is in-place; d.w.z. het vereist slechts een constante hoeveelheid O(1) extra geheugenruimte.
Het is online; d.w.z. het kan een lijst sorteren terwijl het deze ontvangt.

Hier is een implementatie van insertiesort in Java:

public static void insertionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        // Plaats het element a[i] op de juiste plaats in het gesorteerde subarray a[0..i-1]
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

De binnenste lus van insertiesort verplaatst grotere elementen één positie naar rechts, waardoor er ruimte komt om het huidige element in te voegen.Here is the Dutch translation of the provided markdown file, with the code comments translated:

De uitvoeringstijd van insertionsort hangt af van de oorspronkelijke volgorde van de items in de invoer. Als bijvoorbeeld het array groot is en de items al in volgorde (of bijna in volgorde) staan, is insertionsort veel, veel sneller dan wanneer de items willekeurig of in omgekeerde volgorde zijn geordend.

Shellsort

Shellsort is een eenvoudige uitbreiding van insertionsort die snelheid wint door het toestaan van uitwisselingen van arrayitems die ver uit elkaar liggen, om gedeeltelijk gesorteerde arrays te produceren die efficiënt kunnen worden gesorteerd, uiteindelijk door middel van insertionsort.

Het idee is om het array zodanig te herschikken dat het de eigenschap heeft dat het nemen van elke he entry (vanaf een willekeurige startpositie) een gesorteerde deelreeks oplevert. Een dergelijk array wordt een h-gesorteerd array genoemd. Met andere woorden, een h-gesorteerd array bestaat uit h onafhankelijke gesorteerde deelreeksen, die door elkaar zijn geweven. Door voor bepaalde grote waarden van h h-sorteren, kunnen we items in het array over grote afstanden verplaatsen en zo het h-sorteren voor kleinere waarden van h vergemakkelijken. Het gebruik van een dergelijke procedure voor een willekeurige reeks waarden van h die eindigt in 1, zal een gesorteerd array opleveren: dat is shellsort.

Hier is een implementatie van shellsort in Java:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq; // Prioriteitswachtrij
    private int N; // Aantal elementen in de wachtrij
    
    public MaxPQ(int capacity) { // Maak een nieuwe prioriteitswachtrij aan met de gegeven capaciteit
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() { // Controleer of de wachtrij leeg is
        return N == 0;
    }
   
    public void insert(Key key) { // Voeg een nieuw element toe aan de wachtrij
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() { // Verwijder en retourneer het maximale element uit de wachtrij
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) { // Laat een element omhoog zwemmen in de wachtrij
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) { // Laat een element omlaag zinken in de wachtrij
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private booleaHier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:
 
```java
private boolean less(int i, int j) {
    // Vergelijk de elementen op index i en j in de pq-array
    // en retourneer true als het element op index i kleiner is dan het element op index j
    return pq[i].compareTo(pq[j]) < 0;
}
 
private void exch(int i, int j) {
    // Wissel de elementen op index i en j in de pq-array
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}
}

Deze code implementeert een max-georiënteerde binaire heap met behulp van een array pq om de heap-geordende volledige binaire boom op te slaan. De insert() en delMax() bewerkingen behouden de heap-invariant door gebruik te maken van de swim() en sink() hulpmethoden om de heap-volgorde te herstellen door sleutels uit te wisselen met een ouder die groter is dan een kind of een kind dat groter is dan zijn ouder.

Stopwatch

Een nuttiger abstracte gegevensstructuur is een eenvoudige en effectieve abstractie voor een stopwatch, zoals weergegeven op de tegenoverliggende pagina. Om deze te gebruiken, maakt u een Stopwatch-object aan wanneer u de timer wilt starten, en gebruikt u vervolgens de elapsedTime()-methode om de verstreken tijd in seconden sinds het object is gemaakt op te halen. De implementatie gebruikt System.currentTimeMillis() van Java om de huidige tijd in milliseconden sinds middernacht 1 januari 1970 op te halen.

De instantievariabele start registreert de tijd waarop de stopwatch is gemaakt, en elapsedTime() gebruikt start om de verstreken tijd te berekenen. De weergegeven client is typisch: deze voert een berekening uit en gebruikt een Stopwatch om te meten hoe lang de berekening duurt. De Stopwatch-gegevensstructuur is een effectieve abstractie omdat deze het concept van een stopwatch (de interface) scheidt van de implementatie (met behulp van System.currentTimeMillis() van Java). Deze scheiding van interface en implementatie is een fundamenteel kenmerk van abstracte gegevensstructuren dat we in elk ADT in het hele boek zullen zien.

Samenvatting

Abstracte gegevensstructuren zijn een essentieel element van objectgeoriënteerd programmeren dat veel wordt gebruikt in moderne programmering. In dit gedeelte hebben we het volgende gezien:

Het definiëren van een abstracte gegevensstructuur als een Java-klasse, met instantievariabelen om de gegevensstructuurwaarden te definiëren en instantiemethoden om de bewerkingen op die waarden te implementeren.
Het ontwikkelen van meerdere implementaties van dezelfde API, met behulp van verschillende representaties van dezelfde abstracte gegevensstructuur.Hier is de Nederlandse vertaling van het Markdown-bestand, waarbij de code-opmerkingen zijn vertaald:

Abstracte gegevenstypen

Onderscheid maken tussen API's, clients en implementaties van een abstract gegevenstype.
API's ontwerpen voor abstracte gegevenstypen.
Clients en testclients ontwikkelen voor gebruik bij testen en debuggen.
Redeneren over de correctheid van een implementatie van een abstract gegevenstype, met behulp van assertions.
De prestaties van verschillende implementaties van dezelfde API vergelijken.

Deze activiteiten zijn een essentieel onderdeel van de ontwikkeling van elke Java-programma. Elk Java-programma dat we schrijven, zal het gebruik van abstracte gegevenstypen uit bibliotheken omvatten; veel zullen de ontwikkeling van nieuwe abstracte gegevenstypen omvatten. In het volgende gedeelte behandelen we drie fundamentele abstracte gegevenstypen die essentiële componenten zijn in een groot aantal programma's, en in Sectie 1.4 gaan we gedetailleerd in op het proces van het analyseren van de prestatie-eigenschappen van implementaties.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms