Métodos de ordenação

Hoje iremos falar sobre métodos de ordenação.

Ordenação é o ato de classificar uma sequência de elementos em uma ordem predefinida, geralmente em ordem crescente ou decrescente.

Dado uma sequência de n elementos:
<a₁, a₂, a₃, ..., a_n>

A saída será uma permutação (reordenada):
<a'₁, a'₂, a'₃, ..., a'_n>

tal que:
a'₁ ≤ a'₂ ≤ a'₃ ≤ ... ≤ a'_n
Os algoritmos que ordenam um conjunto de elementos são os algoritmos de ordenação, são exemplos de algoritmos de ordenação BubbleSort, InsertionSort, SelectionSort, MergeSort e QuickSort.

A princípio introduziremos com os métodos de ordenação mais simples, BubbleSort, InsertionSort e SelectionSort.

Para os psuedo-códigos adotaremos A sendo o vetor de elementos, p a posição de início do vetor e r a posição final do vetor.

• BubbleSort

A ordenação por flutuação. A ideia é percorrer o vetor e a cada passagem flutuando para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

Pseudo-código
Algoritmo BubbleSort (A, p, r)
    para ls ← n até 2 faça
        para i ← 1 até ls - 1 faça
            se A[i] > A[i+1] então
                troca (A[i], A[i+1])

Complexidade:
Melhor caso: Θ(n²)
Pior caso: Θ(n²)

• InsertionSort

A ordenação por inserção. O funcionamento do algoritmo é percorrer um vetor da esquerda para a direita de forma que os elementos mais à esquerda fiquem ordenados. O algoritmo de inserção é similar a organização das cartas em um jogo de baralho.

Foto: Wikipédia

Pseudo-código
Algoritmo InsertionSort (A, p, r)
    para i ← p + 1 até r faça
        k ← A[i]
            j ← i - 1
        enquanto j ≥ p e A[j] > k
            A[j+1] ← A[j]
            j ← j + 1
    A[j+1] ← k

Complexidade:
Melhor caso: Θ(n)
Pior caso: Θ(n²)

• SelectionSort

A ordenação por seleção tem o objetivo colocar o menor valor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim sucessivamente.

Foto: Wikipédia

Pseudo-código
Algoritmo SelectionSort (A, p, r)
    para i ← p até r - 1 faça
        j ← i + 1
        para k ← j + 1 até r faça
            se A[k] < A[j] então
                j ← k
        se A[j] < A[i] então
            troca(A[i], A[j])

Complexidade:
Melhor caso: Θ(n²)
Pior caso: Θ(n²)