Tri d'une collection

Bubble sort / sinking sort

Fait remonter les éléments les plus grands à la fin du tableau jusqu'à ce que le tableau soit trié.
Complexité en temps de O(n²)

// à chaque passage le plus grand élément du tableau sera remonté à droite
// on ne traite donc plus les éléments de droite déjà triés
for (int i = A.Length - 1; i >= 1; i--)
{
    bool sorted = true;
    // pour chaque élément restant à trier du tableau
    for (int j = 0; j < i; j++)
    {
        // si l'élément courant est plus grand que l'élément de droite, on inverse les 2 éléments
        if (A[j] > A[j + 1])
        {
            int temp = A[j + 1];
            A[j + 1] = A[j];
            A[j] = temp;
            sorted = false;
        }
    }
    // si on a procédé à aucune inversion c'est que ce qui reste à analyser du tableau est déjà trié, on s'arrête donc là
    if (sorted)
    {
        break;
    }
}

Insertion sort

Complexité en temps O(n²), pour les tableaux triés ou presque triés la complexité en temps passe à O(n)

// pour chaque élément du tableau
for (int i = 1; i < A.Length; i++)
{
    int j = i - 1;
    // on compare avec l'élément précédent
    // au besoin on déplace le plus petit élément vers la gauche de sorte que les éléments à gauche soit triés
    while (j >= 0 && A[j] > A[j + 1])
    {
        int temp = A[j + 1];
        A[j + 1] = A[j];
        A[j] = temp;
        j--;
    }
}

Recherche dans une collection triée

L'idée est de découper récursivement le tableau en deux jusqu'à trouver la valeur.

// integers in array are arranged in ascending order
private static int SearchIndexOf(int[] array, int x, int leftIndex, int rightIndex)
{
    if (leftIndex > rightIndex)
        return -1;

    var middleIndex = (leftIndex + rightIndex) / 2;

    if (array[middleIndex] == x)
        return middleIndex;
    else if (array[middleIndex] >= x)
        return SearchIndexOf(array, x, leftIndex, middleIndex - 1);
    else
        return SearchIndexOf(array, x, middleIndex + 1, rightIndex);
}

Rechercher la plus petite différence entre 2 entiers dans un tableau

int[] numbers = { 1, 6, 4, 8, 2 };
int res = FindSmallestInterval(numbers);
Console.WriteLine(res);

static int FindSmallestInterval(int[] numbers)
{
    var minDiff = int.MaxValue;
    var sortedNumbers = numbers.Order().ToArray();
    for (var i = 0; i < numbers.Length - 1; i++)
    {
        var diff = sortedNumbers[i + 1] - sortedNumbers[i];
        if (diff < minDiff)
            minDiff = diff;
    }

    return minDiff;
}

Nombres premiers

Compter le nombre de diviseurs d'un nombre entier N

L'approche la plus basique consiste à parcourir les nombres de 1 à N pour tester s'ils sont bien des diviseurs de N. Cette solution a une complexité en temps de O(N).
Sachant que si A est un diviseur de N, alors N/A est aussi un diviseur de N.

N=30, A=5 → N/A = 6 qui est un diviseur de 30  (30/6 = 5)
6 est le diviseur symétrique de 5 pour le nombre 30

Un de ces 2 diviseurs symétriques est inférieur à √N, on peut donc réduire la complexité en temps à O(√N).

int i;
int numberOfDivisors = 0;
for (i = 1; Math.BigMul(i, i) < N; i++)
{
    if (N % i == 0)
    {
        // le diviseur et son symétrique
        numberOfDivisors += 2;
    }
}

// si (i == √N) il y a un diviseur qui n'a pas de symétrique.
// Ex: N=4, on a 1 et son symétrique 4, mais 2 n'a pas de symétrique
if (Math.BigMul(i, i) == N)
{
    numberOfDivisors++;
}

return numberOfDivisors;

Tester si un entier N est premier

Un entier est premier s'il est divisible seulement par lui-même et par 1.
Ici aussi on réduit la complexité en temps à O(√N).

// on commence à 2, car tous les entiers sont divisible par 1
for (int i = 2; Math.BigMul(i, i) <= N; i++)
{
    if (N % i == 0)
    {
        return false;
    }
}

return true;

Lister les N premiers nombres premiers

L'approche basique consiste à tester si les entiers de 2 à N sont premier. La complexité en temps est de O(N*√N).
En utilisant le crible d'Ératosthène on réduit la complexité O(log(log(N)))

bool[] sieve = new bool[N + 1];
// tout le tableau à true sauf les éléments 0 et 1, car ils ne sont jamais premiers
for (int i = 2; i < N + 1; i++)
{
    sieve[i] = true;
}

// met à false les multiples de j
// par exemple: pour 2 met à false les multiles de 2 (4,6,8,...)
// puis pour 3 met à false les multiles de 3 restants (9,12,...)
// puis pour 4, il a déjà été mis à false par 2
int j = 2;
while (Math.BigMul(j, j) <= N)
{
    if (sieve[j])
    {
        long k = Math.BigMul(j, j);
        while (k <= N)
        {
            sieve[k] = false;
            k += j;
        }
    }
    j++;
}

// on extrait les nombres entiers
var primeNumbers = new List<int>();
for (int i = 0; i < sieve.Length; i++)
{
    if (sieve[i])
    {
        primeNumbers.Add(i);
    }
}

return primeNumbers;

Plus grande somme d'éléments contiguës dans un tableau

On cherche la plus grande somme qu’on puisse avoir en additionnant des éléments consécutifs d'un tableau.
Résolution à l'aide de l'algorithme de Kadane.

// tableau A
// [1, 2, 3, 4]   → somme des éléments 0 à 3 → 10
// [5, -9, 2, -1] → somme des éléments 2 à 3 → 1

int maxEndingHere = 0;
int maxSoFar = 0;
int maxElement = int.MinValue;

for (int i = 0; i < A.Length; i++)
{
    maxEndingHere = Math.Max(0, maxEndingHere + A[i]);
    maxSoFar = Math.Max(maxSoFar, maxEndingHere);
    maxElement = Math.Max(maxElement, A[i]);
}

// si tous les éléments du tableau sont négatif
// la somme max est égale à 0: somme d'un tableau vide
if (maxSoFar == 0)
{
    // ici on souhaite plutôt avoir le plus grand nombre négatif comme solution
    maxSoFar = maxElement;
}

return maxSoFar;

L'algorithme de Kadane suppose que si le tableau ne contient que des éléments négatifs, alors la plus grande somme correspond à 0: somme d'un sous-tableau vide.

Plus grande sous-matrice carrée

On parcourt la matrice, on change la valeur chaque item par Min(top, left, top-left) + 1

{ 1 1 }  { 1 1 1 }
{ 1 2 }  { 1 2 2 }
         { 1 2 3 }

La plus grande valeur de la nouvelle matrice donne la taille de la plus grande sous-matrice carrée.

var matrix = new int[5, 5]
{
    { 1, 1, 0, 1, 0 },
    { 1, 1, 1, 1, 1 },
    { 0, 0, 1, 1, 1 },
    { 0, 0, 1, 1, 1 },
    { 1, 1, 0, 1, 0 },
};

int size = FindLargestSquare(matrix);
Console.WriteLine(size);

static void PrintMatrix (int[,] matrix)
{
    int rowLength = matrix.GetLength(0);
    int colLength = matrix.GetLength(1);

    for (int row = 0; row < rowLength; row++)
    {
        for (int column = 0; column < colLength; column++)
        {
            Console.Write($"{matrix[row, column]} ");
        }
        Console.WriteLine();
    }
}

static int FindLargestSquare(int[,] matrix)
{
    if (matrix is null || matrix.Length == 0)
        return 0;

    int rowLength = matrix.GetLength(0);
    int colLength = matrix.GetLength(1);

    var newMatrix = new int[rowLength, colLength];
    Array.Copy(matrix, 0, newMatrix, 0, matrix.Length);

    for (var c = 1; c < colLength; c++)
    {
        for (var r = 1; r < rowLength; r++)
        {
            if (matrix[r, c] == 1)
            {
                newMatrix[r, c] = 1 + Min(
                    newMatrix[r, c - 1],
                    newMatrix[r - 1, c],
                    newMatrix[r - 1, c - 1]);
            }
        }
    }

    return newMatrix.Cast<int>().Max();
}

static int Min(int val1, int val2, int val3) => Math.Min(val1, Math.Min(val2, val3));

Leader

Un élément d'un tableau est dit leader s'il est présent dans plus de la moitié des éléments du tableau.
Astuce: si on supprime 2 éléments différents du tableau, on supprime au plus un éléments leader.
Le leader reste donc leader du sous-tableau.

A = [4, 6, 6]
s = [4] → s = [4, 6] → 4 ≠ 6, on les supprime → s = [] → s = [6]

// on empile un à un les éléments du tableau
var s = new Stack<int>();
for (int i = 0; i < A.Length; i++)
{
    if (s.Count == 0)
    {
        s.Push(A[i]);
    }
    else
    {
        // si l'élément à empiler est différent de celui du sommet de la pile, on les supprime
        if (s.Peek() != A[i])
        {
            s.Pop();
        }
        else
        {
            s.Push(A[i]);
        }
    }
}

// si la pile est vide, c'est qu'il n'y a pas de leader
if (s.Count == 0)
{
    return -1;
}
// si la pile contient seulement 1 élément, il faut s'assurer qu'il est bien leader
// car ce pourrait être le dernier éléments d'un tableau de taille impair une fois qu'on a supprimer les paires différents
else if (s.Count == 1)
{
    int candidate = s.Peek();
                
    int count = 0;
    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] == candidate)
        {
            count++;
            if (count > A.Length / 2)
            {
                return candidate;
            }
        }
    }

    return -1;
}
// si la pile contient plusieurs éléments, ce sont tous les même et c'est le leader
else
{
    return s.Peek();
}

Inverser les éléments d'un tableau A

On parcourt seulement la première moitié du tableau dont on échange les éléments avec la seconde moitié.

for (int i = 0; i < A.Length / 2; i++)
{
    var temp = A[i];
    A[i] = A[A.Length - 1 - i];
    A[A.Length - 1 - i] = temp;
}

Trouver les cycles dans un graphe orienté

public void FindCycle(int vertex)
{
    // enregistrer le parcourt pour pouvoir afficher les cycles
    _path.Push(vertex);
    // enregistrer les sommets visités afin de pouvoir détecter les cycles
    _visited[vertex] = true;

    // pour tous les sommets adjacents: reliés au sommet courant par une arête sortante
    foreach (var adjacentVertex in _graph.OutEdges(vertex).Select(e => e.Target))
    {
        // si ce sommet adjacent a déjà été parcouru, nous avons trouvé un cycle
        if (_visited[adjacentVertex])
        { ... }
        // sinon on continue à parcourir le graphe à partir du sommet adjacent
        else
        {
            FindCycle(adjacentVertex);
        }
    }

    // après avoir atteint un sommet final (sans arêtes sortantes)
    // on rebrousse chemin: on marque le sommet courant comme non-parcouru et on l'enlève du parcourt
    _path.Pop();
    _visited[vertex] = false;
}

Lexique sur les graphes

Problèmes algorithmiques

Sommaire