Recursion and Sorting Flashcards
How do you calculate a pivot?
Median of three
How does selection sort work
Swapping numbers and putting the swapped numbers in a sorted spot
How does insertion sort work
The first item doesnt have anything left of it so its gets added to the sorted part. The next number you hcekc if it is smaller than the number on the left of it and if so swap them and do the same with thenext number etc.
How does merge sort work
You break the array up into 2 arrays. and then you break them up till you have each number in it is own array. than you compare them on size and place them in one array on each side and then you have a new array in wich you place both of the sorted arrays comparing the values.
How does quick sort work
You choose a pivot. The pivot is already in the correct spot. Then you split it up into greater than and smaller than. and you repeat the proces. Choosing a new pivot each time until you have siungle numbers left and then you should have everything in the correct place so you can add them toghether from left to right.
Is quick sort Recursive
Ja
Complexity of quick sort
o (N LOG N)
What is the name of the technique in the merge sort
Devide and Conquer
Is merge sort recursive
Ja
Complexity Merge Sort
O (n log n)
Complexity Insertion Sort
o (n2)
Waarvoor is de selection sort goed
Snel voor kleine arrays
Wanneer is de insertion sort goed
Snel voor kleine arrays
Waarom heeft de merge sort meer geheugen nodig
Hij maakt veel arrays aan.
Hoe werkt Fibonacci
0,1,1,2,3,5 you add the numbers before it up
How does recursion work
Recursie is een programmeertechniek waarbij een functie zichzelf aanroept om kleinere versies van hetzelfde probleem op te lossen, totdat een basisgeval wordt bereikt dat de recursie stopt. Het wordt vaak gebruikt voor taken zoals het doorlopen van hiërarchische structuren of het oplossen van problemen die kunnen worden opgesplitst in vergelijkbare deelproblemen, zoals factorialen of Fibonacci-reeksen.
De 3 regels voor recursion
Weiss: Regels voor recursie
1. Base case: zorg dat er altijd een geval
is waarbij de recursie stopt
2. Make Progress: werk naar de base
case toe
3. You gotta believe! Geloof dat het
werkt!
De drie stappen van divide-and-conquer
- Divide: opdelen probleem in delen van een
datastructuur. - Conquer: verder opdelen, óf als deelprobleem inderdaad
klein genoeg is, oplossen. - Combine: combineren van de oplossingen voor de
deelproblemen.
Wat is dynamic programming
Dynamic programming is een programmeertechniek die wordt gebruikt om complexe problemen op te lossen door ze op te splitsen in kleinere, overlappende deelproblemen. Het werkt door oplossingen van deze deelproblemen op te slaan (in een tabel of cache), zodat ze niet herhaaldelijk opnieuw worden berekend.
Het bestaat uit twee hoofdprincipes: recursie met memoization en tabulation
Wat is Memoization
Memoization is een techniek binnen dynamic programming waarbij de resultaten van eerder opgeloste subproblemen worden opgeslagen, meestal in een tabel of een dictionary, zodat ze later opnieuw kunnen worden gebruikt zonder opnieuw te hoeven worden berekend. Dit wordt vaak toegepast in een recursieve aanpak: elke keer dat een functie wordt aangeroepen, wordt eerst gecontroleerd of het resultaat al is opgeslagen (in de “cache”). Als dat zo is, wordt het direct teruggegeven; anders wordt het berekend en toegevoegd aan de cache. Dit vermindert onnodige herhalingen en verbetert de prestaties aanzienlijk, vooral bij problemen met overlappende deelproblemen, zoals het berekenen van Fibonacci-getallen
Wat is greedy algoritme(Shortest path Algorithm)
Een greedy algoritme is een oplossingsstrategie die bij elke stap de meest optimale (of “greedy”) keuze maakt in de hoop dat deze keuze uiteindelijk leidt tot de globale optimale oplossing. Voor kortste-pad-algoritmen betekent dit dat het algoritme bij elke stap het pad met de laagste kosten selecteert.
Hoewel greedy algoritmen snel en efficiënt zijn, garanderen ze niet altijd een globale optimale oplossing
