Big O notation

It describes the worst-case scenario for the number of operations an algorithm takes as a function of the size of the input. The notation is used to classify algorithms according to how their running time or space requirements grow as the size of the input increases.

For example, in the O(N^2) the number of instructions in a program/space occupied by a program is quadratic. When the input size doubles, the time increases by 4 times.

When a algorithm is stable?

In programming, stability refers to the property of an algorithm that its output does not change significantly for small changes in the input. A stable algorithm is predictable and its results are consistent and reliable, even for inputs that are only slightly different from each other.

Basic sorting algorithms

Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and swapping it with the first element. The algorithm then moves on to the next unsorted element and repeats the process until the entire list is sorted.

void selection_sort(int a[], int left, int right) {
    int i, j;
    for (i = left; i < right; i++) {
        int aux, min = i;
        for (j = i + 1; j <= right; j++) { /* procura o menor */
            if (a[j] < a[min]) {
                min = j;
            }
        }
        aux = a[i]; /* troca elementos */
        a[i] = a[min];
        a[min] = aux;
    }
}

The time complexity of selection sort is O(n^2) in the worst and average case, but O(n) in the best case (when the array is already sorted). This is because for each element in the array, the algorithm must compare it with every other element in the array.

Time complexity: O(n^2)

Insertion Sort (keep the deck in order)

It iterates through the list, comparing each element to the elements that come before it, and shifting those elements to the right as necessary to make room for the current element. We can think of this algorithm as someone who plays cards and likes to keep his deck in order: whenever he receives a new card, he goes through the list from beginning to end (or vice versa), trying to place the card between an element with key below yours and one above yours.

void insertion_sort(Item a[], int left, int right) {
    int i, j;
    for (i = left + 1; i <= right; i++) {
        Item v = a[i]; /* var auxiliar para guardar o valor de a[i] */
        j = i - 1;
        while (j >= left && less(v, a[j])) { /* percorrer o vetor */
                                             /* até encontrar o elemento menor que v */
            a[j + 1] = a[j];                 /* percorrer uma casa para a direita */
            j--;
        }
        a[j + 1] = v; /* guarda o valor na casa acima ao valor menor */
    }
}

The time complexity of insertion sort is O(n^2) in the worst and average case, but O(n) in the best case (when the list is already sorted). This is because for each element in the list, the algorithm must compare it with every element that comes before it in the list, and may need to shift several elements to the right to make room for the current element.