Sorting Algorithms Overview

Sortieren

• This part gives an overview of different sorting algorithms.
• It includes their worst-case, average-case, and best-case time complexities.
• It also includes the worst-case memory usage.

Übersicht

• Selection Sort has a time complexity of $\mathcal{O}(n^2)$ in all cases and a space complexity of $\mathcal{O}(1)$.
• Insertion Sort has a worst-case and average-case time complexity of $\mathcal{O}(n^2)$, a best-case time complexity of $O(n)$, and a space complexity of $\mathcal{O}(1)$.
• Shellsort has a worst-case time complexity of $\mathcal{O}(n^2)$, a best case of $O(n)$ and a space complexity of $\mathcal{O}(1)$, the average case depends on the Gap Sequence.
• Heapsort has a time complexity of $\mathcal{O}(n \log n)$ in all cases and a space complexity of $\mathcal{O}(1)$.
• Quicksort has a worst-case time complexity of $\mathcal{O}(n^2)$, an average-case and best-case time complexity of $\mathcal{O}(n \log n)$, and a space complexity of $\mathcal{O}(n)$.
• Mergesort has a time complexity of $\mathcal{O}(n \log n)$ in all cases and a space complexity of $\mathcal{O}(n)$.
• Radixsort has a time complexity of $\mathcal{O}(nk)$ in all cases and a space complexity of $\mathcal{O}(n + k)$.
• Bucketsort has a worst-case time complexity of $\mathcal{O}(n^2)$, an average-case time complexity of $\mathcal{O}(n)$, a best case of $O(n)$, and a space complexity of $\mathcal{O}(n)$.
• Counting Sort has a time complexity of $\mathcal{O}(n + k)$ in all cases and a space complexity of $\mathcal{O}(k)$.
• Inplace Mergesort has a worst-case time complexity of $\mathcal{O}(n^2)$, and an average-case time complexity of $\mathcal{O}(n \log n)$, and a space complexity of $\mathcal{O}(1)$.
• Blockwise Mergesort has a time complexity of $\mathcal{O}(n \log n)$ in all cases and a space complexity of $\mathcal{O}(\sqrt{n})$.
• Timsort has a worst-case and average-case time complexity of $\mathcal{O}(n \log n)$, a best case of $O(n)$ and a space complexity of $\mathcal{O}(n)$.
• Library Sort has a worst-case time complexity of $\mathcal{O}(n^2)$, and an average-case time complexity of $\mathcal{O}(n \log n)$, and a space complexity of $\mathcal{O}(n)$.
• Patience Sorting has a worst-case time complexity of $\mathcal{O}(n^2)$, and an average-case time complexity of $\mathcal{O}(n \log n)$, and a space complexity of $\mathcal{O}(n)$.
• Permutation Sorting has a worst-case time complexity of $\mathcal{O}(n*n!)$, and an average-case time complexity of $\mathcal{O}(n!)$, a best case of $O(n)$ and a space complexity of $\mathcal{O}(1)
• Pancake Sorting has a time complexity of $\mathcal{O}(n)$.
• Spaghetti Sort has a time complexity of $\mathcal{O}(n)$.
• n is the number of elements to be sorted.
• k is the size of the key range.

Anmerkungen

• Quicksort is often faster than Mergesort in practice due to a lower constant runtime, despite its inferior worst-case complexity.
• Mergesort is stable, so the relative order of equal elements is preserved.
• Heapsort is in-place
• Radixsort/Bucketsort are suitable only for certain data types, like integers with a known range.
• A sorting algorithm is stable if elements with the same key value maintain their original relative order after sorting.

Listen

• This is a list of the different list types
• Verkettete Liste = Linked List
• Doppelt verkettete Liste = Doubly Linked List
• Arraylist = Array List

Bäume

• This is a list of the different Trees you can make in code
• Binärbaum = Binary Tree
• Binärer Suchbaum = Binary Search Tree
• AVL-Baum = AVL Tree
• B-Baum = B-Tree
• Rot-Schwarz-Baum = Red-Black Tree
• Trie = Trie

Algorithmes de Division : Revue et Exemples

• Division is a math operation to divide the dividend by the divisor.
• The result contains a quotient and a remainder

Algorithme de Division Longue

• The long division algorithm is for complex numbers if the divisor contains multiple digits.
• It's done iteratively, finding a digit for the quotient each time.
• Preparation: Write the dividend and divisor in long division format.
• Division: Divide the first digits of the dividend by the divisor.
• Multiplication: Multiply the partial quotient by the divisor.
• Soustraction: Subtract the result from the partial dividend.
• Abaissement: Drop the next digit of the dividend.
• The steps above are repeated until all the dividend's digits have been used.

Algorithme de Division Rapide

• It's useful for comupters.
• It uses binary shifts to speed up the division.
• Initialisation: Align the dividend and the divisor.
• Décalage: Shift the divisor left until it aligns with the dividend.
• Soustraction: If the divisor is less than the partial dividend, record a 1 in the quotient, else record a zero
• Restore: if the substraction is negative, add the divisor to restore it.

Algorithme de Division par Réciproque

• This is done by multiplying the divident by the inverse of the divisor.
• This is useful when dividing multiple times by the same divisor.
• Invert the divisor
• Multiply the dividend by the inverse of the divisor.

Comparaison des Algorithmes

• Each algorithm has it's own advantages and disadvantages, and the choice of the algorithm depends on the context and the specific requirements.
• Division Longue = High Complexity
• Division Rapide = Medium Complexity
• Division par Réciproque = Low Complexity

Algèbre linéaire

• Summaries of linear algebra including matrices, equations, determinants, vector spaces, linear applications and eigenvalues

Matrices

• A matrix is a number table. Distinctions are made
• Matrices carrées = Square matrix: number of rows = number of columns
• Matrices lignes = Row Matrix: one line
• Matrices colonnes = Column matrix: one row
• Matrices nulles = Null matrix: all elements are zero
• Matrices diagonales = Diagonal matrix: Non-diagonal elements are zero
• Matrices identités = Identity matrices: diagonal of 1, other elements zero
• Matrices triangulaires supérieures = Upper triangular matrices: Elements below the diagonal are zero
• Matrices triangulaires inférieures = Lower triangular matrices: Elements above the diagonal are zero
• Matrices symétriques = Symmetric matrices: $A = A^T$ (transposed)
• Matrices antisymétriques = Skew-symmetric matrices: $A = -A^T$

Opérations sur les matrices

• Somme de deux matrices = Sum of two matrices: $C = A + B$, where $c_{ij} = a_{ij} + b_{ij}$
• Produit d'une matrice par un scalaire = Product of a matrix by a scalar: $B = \lambda A$, where $b_{ij} = \lambda a_{ij}$
• Produit de deux matrices = Product of two matrices: $C = AB$, where $c_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}$

Transposition

• The transpose of a matrix A, written $A^T$ is obtained by swapping the rows and columns of A.

Inverse

• The inverse of a square matrix A, written $A^{-1}$, is such that $AA^{-1} = A^{-1}A = I$, where I is the identity matrix

Systèmes d'équations linéaires

• A system of linear equations is a set of equations of the form

Définitions

• A system of linear equations is a set of equations of the form: $\qquad \begin{cases} \qquad a_{11}x_1 + a_{12}x_2 +... + a_{1n}x_n = b_1 \ \qquad a_{21}x_1 + a_{22}x_2 +... + a_{2n}x_n = b_2 \ \qquad... \ \qquad a_{m1}x_1 + a_{m2}x_2 +... + a_{mn}x_n = b_m \end{cases}$

Résolution

• Gauss Method : Elimination of variables by elementary operations on rows.
• Cramer's Method: Using determinants to find solutions.
• Matrix Inversion: $AX = B \Rightarrow X = A^{-1}B$

Déterminants

• The determinant of a square matrix.

Définition

• The determinant of a square matrix, noted det(A) or |A|, is a scalar that characterizes certain properties of the matrix.

Propriétés

• $\det(A^T) = \det(A)$
• $\det(AB) = \det(A) \det(B)$
• If A is invertible, $\det(A^{-1}) = \frac{1}{\det(A)}$
• If A has a row or column of zeros, $\det(A) = 0$
• If A has two identical rows or two columns, $\det(A) = 0$

Calcul

• Matrices 2x2: $\det(A) = ad - bc$ for $A = \begin{pmatrix} a & b \ c & d \end{pmatrix}$
• Matrices 3x3: Sarrus rule or development with respect to a row or column.

Espaces vectoriels

• Covers vector spaces with examples.

Définitions

• A vector space is a set with two operations (addition and multiplication by a scalar) that satisfy certain properties (commutativity, associativity, existence of a neutral element and an inverse).

Exemples

Sous-espaces vectoriels

• A subset of a vector space which is itself a vector space

Base et dimension

• A basis of a vector space is a set of linearly independent vectors that generate the space.
• The dimension of a vector space is the number of vectors in a basis.
• $\mathbb{R}^n$ : Set of n-tuples of real numbers
• $\mathbb{C}^n$ : Set of n-tuples of complex numbers
• Space of continuous functions over an interval
• Space of polynomials

Applications linéaires

• A linear function is the function of spaces, with properties.

Définitions

• A linear function is a function between two vector spaces that preserves the operations of addition and multiplication by a scalar.

Propriétés

• $f(u + v) = f(u) + f(v)$
• $f(\lambda u) = \lambda f(u)$

Noyau et image

• Noyau (Ker) = Kernel : Set of vectors that are sent to the zero vector.
• Image (Im) = Image: Set of vectors that are reached by the application.

Représentation matricielle

• A linear application can be represented by a matrix

Valeurs propres et vecteurs propres

• Covers Eigenvalues and Eigenvectors

Définitions

• An eigenvector of a matrix A is a non-zero vector v such that Av = λv, where λ is an eigenvalue of A/

Polynôme caractéristique

• The characteristic polynomial of A is given by det(A - λI). The roots of this polynomial are the eigenvalues of A.

Diagonalisation

• A matrix A is diagonalizable if there exists an invertible matrix P such that $P^{-1}AP$ is a diagonal matrix.
• The columns of P are the eigenvectors of A.

Automorphisms

• An automorphism of a graph $G = (V, E)$ is a permutation $\phi$ of $V$ such that $(u, v) \in E$ if and only if $(\phi(u), \phi(v)) \in E$.
• An automorphism is an isomorphism of a graph with itself.

Properties

• The set of all automorphisms of a graph $G$ forms a group under composition, called the automorphism group of $G$ , denoted by $Aut(G)$.
• Automorphisms preserve graph properties, such as degree, connectivity, and planarity.
• Determining the automorphism group of a graph is, in general, a difficult problem.

Applications

• Graph isomorphism testing
• Symmetry detection
• Network analysis
• Chemistry (e.g., studying symmetries of molecules)

Probability

Sample Space

• A sample space, denoted by S, is the set of all possible outcomes of a random experiment.

Examples

• Toss a coin once. $S = {H, T}$
• Toss a coin twice. $S = {HH, HT, TH, TT}$
• Pick a number between 0 and 1. $S = {x: 0 \leq x \leq 1}$
• Toss a coin until a head appears. $S = {H, TH, TTH, TTTH,...}$

Events

• An event is a subset of the sample space.

Examples

• Consider the experiment of tossing a coin twice. $S = {HH, HT, TH, TT}$
• The event of getting at least one head is $E_1 = {HH, HT, TH}$
• The event of getting two tails is $E_2 = {TT}$

Set Operations

• Let A and B be two events in the sample space S.
• Complement: The complement of A, denoted by $A^c$, is the set of all outcomes in S that are not in A. $A^c = {x \in S: x \notin A}$
• Intersection: The intersection of A and B, denoted by $A \cap B$, is the set of all outcomes that are in both A and B. $A \cap B = {x \in S: x \in A \text{ and } x \in B}$
• Union: The union of A and B, denoted by $A \cup B$, is the set of all outcomes that are in A or B or both. $A \cup B = {x \in S: x \in A \text{ or } x \in B}$

Mutually Exclusive Events

• Two events A and B are mutually exclusive (or disjoint) if they have no outcomes in common. $A \cap B = \phi$

Example

• Consider the experiment of tossing a coin twice. $S = {HH, HT, TH, TT}$
• Let $E_1$ be the event of getting two heads. $E_1 = {HH}$
• Let $E_2$ be the event of getting two tails. $E_2 = {TT}$ $E_1$ and $E_2$ are mutually exclusive events. $E_1 \cap E_2 = \phi$