Algorytmy

Fast searching in a SORTED array: we look at the middle and throw out half of the elements every time. In an array of a million numbers about 20 steps are enough.

The simplest way to search: we check the elements one by one, from the first, until we hit the target or run out of array. Works on any array — sorted or not.

Compares neighbouring elements and swaps them when they are in the wrong order. After every pass the largest element "floats" to the end — like a bubble.

In every pass it selects the smallest element of the unsorted part and puts it in the next position. It makes at most n - 1 swaps.

Takes the numbers one by one and inserts each into its place in the already sorted part, shifting bigger numbers to the right. Very fast for almost sorted data.

Instead of comparing numbers, it counts how many times each value appears and then writes them out in order. Lightning fast when the values come from a small range (e.g. grades 1-6).

The fastest way to get the GCD — the greatest common divisor of two numbers. Instead of checking every divisor, we replace the pair (a, b) with (b, a % b) until b is zero.

A preprocessing technique that allows for fast calculation of range sums in an array.

An algorithmic technique using two pointers moving through an array to solve a problem.

A graph traversal algorithm that visits all neighbors at the current depth before moving to nodes at the next depth level.

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

Algorithm for detecting cycles in a directed graph using DFS with two sets: visited and in_path.

Algorithm for detecting cycles in an undirected graph using DFS with a parent parameter.

Topological sort arranges vertices of a directed acyclic graph (DAG) in an order such that every edge goes from an earlier vertex to a later one.

The pre-order list algorithm records vertices in the order they are first discovered by DFS — each vertex is added to the list upon entry, BEFORE checking neighbors.

The in-order list algorithm records binary tree vertices in the order: left subtree → vertex → right subtree. On a BST it produces a sorted list!

The post-order list algorithm records vertices in the order they are completed by DFS — each vertex is added to the list AFTER processing ALL its neighbors (at function exit).

Algorithm for finding connected components in an undirected graph. Uses DFS with an outer loop over all vertices — each unvisited vertex starts a new component, and DFS visits all vertices in that component.

The algorithm checks whether an undirected graph is bipartite — meaning vertices can be split into two groups so that every edge connects vertices from different groups. Uses DFS with vertex coloring.

Naive algorithm for finding the Strongly Connected Component (SCC) from a single vertex. Performs forward DFS to find reachable vertices, then a separate backward DFS for each candidate. Introduction to more efficient algorithms (Kosaraju, Tarjan).

Finding the Strongly Connected Component (SCC) of a given vertex using the edge flip trick. Instead of checking each candidate separately (naive), we reverse all edges and run just 2 DFS searches! Complexity: O(V+E) instead of O(V×(V+E)).

Kosaraju's algorithm finds ALL strongly connected components (SCC) in a directed graph using two DFS passes. The first pass records the finish order of vertices. The second pass processes vertices in reverse finish order on the reversed graph — each DFS in the second pass finds exactly one SCC!