Grade 10 · 8 algorithmsCitește în română

Divide and conquerDivide et impera

Every divide and conquer algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

8algorithms
6chapters
1grade

Divide and conquer

Divide et impera · 8 algorithms

Recursive binary searchCăutare binară recursivăThe array is sorted in increasing order. We compare x with the middle element: if they are equal we are done; if x is smaller, we search only the…O(log n)
GCD of an array's elements with divide and conquerCmmdc-ul elementelor unui vector prin divide et imperaThe GCD of a portion is the GCD of the left half's GCD and the right half's GCD, because gcd(a, b, c, d) = gcd(gcd(a, b), gcd(c, d)). The base case:…O(n log n)
Maximum of an array with divide and conquerMaximul unui vector prin divide et imperaThe three stages of the method: we split the portion [st, dr] into two halves at the middle m = (st + dr) / 2 (divide); we find the maximum of each…O(n)
Counting the even elements with divide and conquerNumărul elementelor pare prin divide et imperaThe same pattern as for the sum: the result for the portion [st, dr] is the sum of the results of the two halves. Only the base case differs: a…O(n)
Merge sortSortarea prin interclasare (Merge Sort)We split the array into two halves, sort each half recursively, then merge them: we always compare the first remaining elements of the two halves…O(n log n)
Quick sortSortarea rapidă (Quick Sort)We pick a pivot (here the middle element) and rearrange the portion so that values <= pivot end up on the left and values >= pivot on the right:…O(n log n)
Sum of the elements with divide and conquerSuma elementelor prin divide et imperaThe sum of the portion [st, dr] is the sum of the left half [st, m] plus the sum of the right half [m + 1, dr]. A portion with a single element has…O(n)
Towers of HanoiTurnurile din HanoiThere are n disks on rod A, in decreasing order of size, and we want to move them to rod C, using rod B, without ever placing a large disk on a…Exponential