Complexidade: O melhor caso é O(1) e o pior caso é O(log n).

Algoritmos de Ordenação

Bubble Sort (Ordenação por flutuação): Compara pares de elementos adjacentes e os troca de lugar se estiverem fora de ordem. Repete esse processo até a lista estar ordenada. Pseudocódigo:

funcao bubbleSort(lista) {
    para i de 0 até tamanho(lista) - 1 {
        para j de 0 até tamanho(lista) - i - 2 {
                se lista[j] > lista[j+1] então
                        trocar lista[j] com lista[j+1]
        }
    }
}

Complexidade: O(n²).

Selection Sort (Ordenação por seleção): Encontra o menor valor da lista e o coloca na primeira posição. Depois, encontra o segundo menor e o coloca na segunda posição, e assim por diante. Pseudocódigo:

funcao selectionSort(lista) {
        para i de 0 até tamanho(lista) - 2 {
                menor = i
                para j de i+1 até tamanho(lista) - 1 {
                                se lista[j] < lista[menor] então
                                                                menor = j
                }
                trocar lista[i] com lista[menor]
        }
}
Complexidade: O(n²).

Insertion Sort (Ordenação por inserção): Insere cada elemento da lista em sua posição correta, como se estivesse organizando cartas na mão. Pseudocódigo:

funcao insertionSort(lista) {
        para i de 1 até tamanho(lista) - 1 {
                chave = lista[i]
                j = i - 1
                enquanto j >= 0 e lista[j] > chave {
                                lista[j + 1] = lista[j]
                                j = j - 1
                }
                lista[j + 1] = chave
        }
}
Complexidade: O melhor caso é O(n) e o pior caso é O(n²).