APP-Notes

• Sorteeralgoritmes
  • Insertion sort
    • Voordelen
  • Bubble sort
  • Selection sort
  • Merge sort
  • Quicksort
• Kiezen
• Opdrachten
  • Opdracht 1
  • Opdracht 2 - Mergesort
  • Opdracht 3 - Quicksort

Sorteeralgoritmes

Zijn belangrijk om dingen (met name zoeken) snel te kunnen doen

Insertion sort

• Steeds een entiteit uit een ongesorteerd lijstje in het gesorteerde lijstje inserten
• Bij inserten van rechts naar links steeds kijken of het te-inserten getal groter of kleiner is
• O(n^2) omdat er 2 loops in elkaar zitten

Voordelen

• Snel voor kleine arrays

Bubble sort

• O(n^2)
• Begint voorin
• Schuift 1 plek op
• Vergelijkt 2 getallen die naast elkaar staan
• Wisselt om zodat links groter is dan rechts
• Aan het begin + 1 beginnen

Selection sort

• O(n^2)
• Steeds lijstje af, kleinste zoeken en vooraan zetten

Merge sort

Zie afbeelding

• O(n log n)
• Recusief algoritme
• Steeds splitsen
• Steeds mergen
• Veel geheugenruimte door extra array
• Veel kopieeracties is duur
• Minste aantal vergelijkingen nodig (bij object vergelijkingen is dit een voordeel)
• Voor primitieve types is Quicksort in het voordeel

Quicksort

Zie slide afbeelding

• O(n log n)
• Gebruikt in java voor primitieve types
• Erg snel, zeker bij grote arrays, populair algoritme
• Etc. Zie slides

1. Pak eik-getal
   • Niet begin/eind. Als het lijstje al gesorteerd hebt, heb je het worst-kaas scenario
   • Mediaan pakken. Het precieze midden van het linker, middelste en rechter getal
2. Stop alle nummers kleiner dan het eik-getal links
3. Stop alle nummers groter dan het eik-getal rechts
4. Voer op links en rechts hetzelfde verhaal uit tot er 1 getal overblijft
5. Voeg recursief samen (links , eik-punt, rechts)

Kiezen

• Kleine arrays: insertionsort
• Objectreferenties (grotere arrays): mergesort
• Primitieve arrays (grotere arrays): quicksort

Opdrachten

Opdracht 1

[] - [8,6,0,7,5,3,1]
[8] - [6,0,7,5,3,1]
[6,8] - [0,7,5,3,1]
[0,6,8] - [7,5,3,1]
[0,6,7,8] - [5,3,1]
[0,5,6,7,8] - [3,1]
[0,3,5,6,7,8] - [1]
[0,1,3,5,6,7,8] - []

Opdracht 2 - Mergesort

[8,6,0,7,5,3,1]
[8,6,0,7] - [5,3,1]
[8,6] - [0,7] - [5,3,1]
[8] - [6] - [0,7] - [5,3,1]
[6,8] - [0,7] - [5,3,1]
[6,8] - [0] - [7] - [5,3,1]
[6,8] - [0,7] - [5,3,1]
[0,6,7,8] - [5,3,1]
[0,6,7,8] - [5,3] - [1]
[0,6,7,8] - [5] - [3] - [1]
[0,6,7,8] - [3,5] - [1]
[0,6,7,8] - [1,3,5]
[0,1,3,5,6,7,8]

Opdracht 3 - Quicksort

Zie afbeelding