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

Sorting and searchingSortare și căutare

Every sorting and searching 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

10algorithms
8chapters
1grade

Sorting and searching

Sortare și căutare · 10 algorithms

Binary searchCăutarea binarăIt only works on an array sorted in increasing order. We compare x with the middle element of the range [st, dr]: if they are equal, we are done; if…O(log n)
Linear searchCăutarea secvențialăWe check the elements one by one, starting from the first, until we find the value x or reach the end of the array. It works on any array, sorted or…O(n)
Merging two sorted arraysInterclasarea a doi vectori sortațiFrom two arrays sorted in increasing order we build a third, also sorted. We compare the current elements a[i] and b[j], copy the smaller one and…O(n)
First position with a value greater than or equal to xPrima poziție cu valoare mai mare sau egală cu xThe binary search variant that does not stop at the first match: in an array sorted in increasing order, we look for the smallest position p with…O(log n)
Sorting with std::sortSortarea cu std::sortThe <algorithm> library has the sort function, which orders in O(n log n). It takes the start and the end of the range: for positions 1..n we write…O(n log n)
Sorting by two criteriaSortarea după două criteriiWe order the numbers increasingly by their last digit, and numbers with the same last digit decreasingly by value. The sorting algorithm stays the…O(n²)
Insertion sortSortarea prin inserțieLike arranging playing cards in your hand: the first i - 1 elements are already sorted, and v[i] is inserted in its place among them. We save v[i]…O(n²)
Bubble sortSortarea prin metoda bulelorWe go through the array and swap any two neighbouring elements that are in the wrong order (v[i] > v[i + 1]). After every pass, the largest…O(n²)
Counting sortSortarea prin numărareWhen the values are small natural numbers (here 0..10000), we do not compare elements: we count how many times each value appears in a frequency…O(n)
Selection sortSortarea prin selecțieFor every position i, from 1 to n - 1, we look for the minimum of v[i..n] and bring it to position i with a single swap. After step i, the first i…O(n²)