# Curso Livre de Estruturas de Dados/Métodos de Ordenação

Um método de ordenação no meio da informática, é um algoritmo que é capaz se colocar todos os elementos em uma sequência predefinida de informação. Para tal, esses algoritmos fazem uso de uma função de comparação entre dois elementos que determina qual deles vem primeiro na ordem, para então realizar as operações de ordenação dos elementos. Em geral, se utiliza a ordem numérica crescente (a > b) para dados simples numéricos, e a ordem lexicográfica (popularmente, ordem alfabética) para cadeias de caracteres. A função de ordenação possui grande importância ao lidar com dados compostos, pois ela determina o tipo de ordenação que resultará da aplicação do método, e ela não se limita a comparar dados simples de estruturas compostas (por exemplo, uma função de ordenação pode aplicar funções sobre os dados, ou compará-los com elementos externos).

## Algoritmos
### Insertion Sort

A ideia do algoritmo é percorrer cada elemento e a cada iteração comparar com os elementos a esquerda (valores já ordenados previamente) enquanto seu valor for valor maior que o atual, caso seu valor for menor o item está ordenado e assim segue para o proximo item, repetindo o processo ate o final.

#### Complexidade de tempo

Média: O(n²).
Pior Caso: O(n²).
Melhor Caso: O(n).

#### Implementação
##### PHP:
### Bubble Sort

Este algoritmo de ordenação pode-se considerar um dos mais simples e por conta disso, pode-se também considerar um dos métodos mais lerdos, tendo uma complexidade de ordem quadrática, tendo assim O(n$^2$) comparações, no qual n é o número de elementos.
A ideia deste algoritmo consiste-se na ideia de percorrer todos os elementos, onde é feito a comparação das informações de dois em dois, ao encontrar um dos elementos que deve ser trocado, ele faz a troca da posição de um pelo outro e continua a percorrer o vetor caso ainda não tenha chegado ao final.

#### Complexidade de tempo

Média: O(n²).
Pior Caso: O(n²).
Melhor Caso: O(n).

#### Implementação
##### PHP:
### (Cocktail) Shaker Sort

Cocktail ou Shaker Sort é um algoritmo partindo da variação do Bubble Sort. Ao passo que o Bubble Sort percorre e troca os elementos da estrutura em uma direção por iteração, o Shaker Sort percorre e troca os elementos nas duas direções por iteração.

#### Complexidade de tempo

Média: O(n²)
Pior Caso: O(n²), ocorre quando a estrutura está ordenada de maneira inversa ao critério utilizado.
Melhor Caso: O(n), ocorre quando a estrutura já está ordenada.

#### Implementação
### Radix Sort

O radix sort é um algoritmo de ordenação estável e rápido que pode ser usado para ordenar itens que estão identificados por chaves únicas. As chaves são uma cadeia de números ou caracteres, e este método de ordenação ordena estas chaves em qualquer ordem relacionada com a lexicografia.
Dentro da ciência da computação, este algoritmo de ordenação é responsável por ordenar inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres (como nomes ou datas) e pontos flutuantes especialmente formatados, o radix sort não é limitado somente a inteiros.

#### Funcionamento

Em geral as máquinas representam os dados internos como números binários, então, tendo isso em mente, é muito mais conveniente processar os dígitos na forma de inteiros em grupos representados por dígitos binários. O radix sort pode ser dividido em dois tipos de classificações, sendo estes:
* radix sort de dígito menos significativo (LSD);
* radix sort de dígito mais significativo (MSD).
O radix sort LSD começa do dígito menos significativo até o mais significativo, geralmente, ordenando da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Assim coincide com a ordem normal de representação dos inteiros, como por exemplo a sequência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Os valores processados pelo algoritmo de ordenação, como se pode perceber, são chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.
Já o radix sort MSD funciona de maneira contrária, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. Por exemplo, a sequência "b, c, d, e, f, g, h, i, j, ba" seria ordenada como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída "1, 10, 2, 3, 4, 5, 6, 7, 8, 9".

#### Implementação
### Selection Sort

O Selection Sort Trabalha com a ideia de dois subarrays, um dos elementos já ordenados e outro de elementos desordenados. Dessa forma, itera-se o subarray do elementos desordenados (inicialmente o array inteiro) selecionando o menor elemento e trocando-o com o primeiro(ou último) desse subarray. A cada iteração o limite inferior do subarray dos elementos desordenados e o limite superior do subarray dos ordenados aumenta. Assim, quando o subarray dos elementos desordenados tiver tamanho 1, o array estará ordenado.

#### Complexidade de Tempo

Média: O(n²)
Pior Caso: O(n²), ocorre quando a estrutura está ordenada de maneira inversa ao critério utilizado.
Melhor Caso: O(n), ocorre quando a estrutura já está ordenada.

#### Implementação

A implementação pode ser feita dos seguintes modos:

##### PHP:

Interativo:
Recursivo:

### Merge Sort
#### Descrição

Também conhecido como ordenação por mistura, é um método de ordenação eficiente, operando por divisão e conquista. O Merge Sort tem seu funcionamento baseado em dividir os problemas em várias partes menores, resolve-las de maneira recursiva para então juntar novamente o total resolvido.
Como por exemplo, sejam dois vetores 'a' e 'b', sua junção sendo 'v'. Se a[3] e b[2] o tamanho de 'v' deve ser a soma do tamanho de 'a' e 'b' v[5].

#### Implementação

A partir do pseudo código de verificação listado a baixo, é possível compreender a imagem de exemplo.
No caso deste exemplo da foto, a varredura de um vetor acaba antes do outro, pois os dois possuem tamanhos diferentes.
Nesta etapa, os elementos restantes do vetor 'a' serão todos incluídos em ' v', já que 'b' terminou de verificas seus elementos.

#### Complexidade de Tempo

Para grandes quantidades de informações o Merge pode ser considerado uma melhor opção em relação aos métodos de comparação e troca como bubble, insertion e selection.
Média: O(n Log₂ n).
Pior Caso: O(n Log₂ n).
Melhor Caso: O(n Log₂ n).

#### Exemplos:
##### PHP:
### Quick Sort
#### Descrição

Assim como o Merge sort, é um algoritmo do paradigma "Dividir e conquistar".No Quick sort, é escolhido elemento como pivô(1) e então o array é particionado(1) em volta dele, em seguida são feitas chamadas recursivas da função para os subarrays à esquerda e direita do pivô.Dessa forma, quando todas as chamadas recursivas encontram um subarray unitário o array está ordenado.
(1) O processo chave para o Quick sort é o processo de particionamento, que consiste em escolher um pivô e colocar todos os elementos menores que o pivô à sua esquerda e os maiores à sua direita.Existem diversos algoritmos de particionamento que escolhem um ou mais pivôs de maneira diferente, alguns são:
* Particionamento de Lomuto: Escolhe o último elemento como pivô, o algoritmo mantém o index i enquanto varre o array com um index j tal que no final os elementos [low, i) são menores que o pivô e os elemementos [i,j] são maiores ou iguais que o pivô.Usando esse esquema, a complexidade de tempo do Quick sort quando o array já está ordenado cai para O(n^2).
* Particionamento Orignal de C.A.R. Hoare: Escolhe o primeiro elemento como pivô, e usa dois índices - um que aponta para o começo do array e outro para o final - que se movem em direção um ao outro até que é detectada uma inversão de elementos, que então são trocados.Quando os índices se encontram, o algoritmo para e retorna o índice final.É mais eficiente que o partionamento de Lomuto, uma vez que faz e média 3 vezes menos trocas que ele, porém também decai para a complexidade de tempo O(n^2) se o array já está ordenado.
* Existem outros particionamentos - como a mediana-de-três, pivô randômico, etc- que produzem resultados melhores em alguns casos específicos.

#### Complexidade de tempo:

A complexidade de tempo do Quick Sort nos casos extremos depende da posição do pivô encontrado.
* Média: O(nlog(n))
* Melhor Caso: O(nlog(n)), ocorre quando os pivôs encontrados são os elementos médios dos subarrays.
* Piores Casos: O(n^2) ocorre quando os pivôs encontrados estão nas bordas dos subarray,ou seja, o array já está ordenado(ou quase ordenado), está ordenado de maneira inversa, ou contém muitos elementos repetidos.
Observações e Links úteis:
O Quick sort é preferido em contrapartida ao Merge sort para estruturas contíguas na memória, como arrays.
* A implementação vanilla usando a maioia dos algoritmos de particionamento(como o de Lomuto e o de Hoare) não é estável(não mantém a ordem dos elementos com chaves de ordenação iguais).
* Pode ser modificado a fim de se tornar estável.
* Pela sua natureza recursiva, o Quick sort necessita de espaço auxiliar apenas para chamadas recursivas.

### Shell Sort
#### Descrição

Também chamado de “ordenação por incrementos diminutos”, aumenta o desempenho da ordenação por inserção ao quebrar a lista original em um número menor de sublistas, as quais são ordenadas usando a ordenação por inserção. A principal particularidade do shell sort é como essas sublistas são divididas.
A ideia principal do Shell Sort é a troca de elementos distantes, h-ordenando(1) o array para um valor grande de h, à medida que ele vai diminuindo na proporção definida. Assim, quando h=1, é realizado um Insertion Sort comum, porém necessitando de muito menos trocas.
(1) Um array é dito h-ordenado quando todas as sublistas de i + múltiplos de h está ordenada.
(2) O aspecto mais importante do Shell sort é o uso de diferentes proporções (ou lacunas) na h-ordenação do array. Alguns são:
* Incremento original de D.L. Shell: N/2^k (divisões consecutivas por 2).
* Incremento de Hibbard: 2^k-1 (potências de 2 menos um).
* Incremento de Knuth: (3^k-1)/2 (potências de 3 menos um sobre dois).
* Incremento de Sedgewick: {1, 5, 19, 41, 109, ...} (sequência definida experimentalmente).

#### Complexidade de tempo

A complexidade de tempo do Shell Sort depende do tipo de lacuna usada na h-ordenação do array, pode variar de O(n*log(n)) à O(n*log^2(n)),porém geramente é considerada perto de O(n) e menor que O(n^2).
Média: O(n^2)
Assim como o Insertion Sort, O Shell Sort é útil quando o conjunto de elementos está parcialmente ordenado.

#### Implementação
### Heapsort
#### Descrição

Desenvolvido em 1964 por J.W.J Williams e Robert W. Floyd O Heapsort é um algoritmo de ordenação cujo princípio de funcionamento e o mesmo do algoritmo Selectionsort (Ordenação por Seleção). É caracterizado por utilizar uma heap para organizar informação durante a execução do algoritmo.

#### Funcionamento

No Heapsort, o primeiro passo é construir uma estrutura de dados chamada heap, o segundo passo é selecionar o maior elemento da heap e alterar pelo elemento que está na última posição do vetor, e em sequência reconstruir a heap com n-1, onde n é o tamanho do vetor. O segundo passo é repetido com n-1 itens restantes, e depois n-2, até que n seja igual a 1.

#### Complexidade de tempo:

A complexidade de tempo do heapsort nos casos extremos depende da posição do pivô encontrado.
* Média: O(nlog(n)).
* Melhor Caso: O(nlog(n)).
* Pior Caso: O(nlog(n)).

#### Implementação
##### Javascript:
### Gnome sort
#### Descrição:

O Gnome sort foi originalmente proposto pelo iraniano Hamid Sarbazi-Azad em 2000 e primeiramente conhecido como “stupid sort” por ser um algoritmo com uma lógica muito simplista. O alemão Dick Grune deu o nome para o aloritmo de Gnome Sort, em homenagem ao duende de jardim alemão.
Este método é baseado na técnica usada pelo duende de jardim alemão onde basicamente ele olha o vaso de flor próximo a ele e o anterior; se eles estão na ordem certa ele avança um vaso, caso contrário ele troca os jarros e volta um passo, com as seguintes condições de parada: se não tem um jarro anterior ao atual, ele avança um passo, se não tem um jarro após o atual, está tudo organizado.

#### Funcionamento:

É semelhante ao tipo de inserção, na medida em que funciona com um item de cada vez, mas leva o item para o lugar adequado por uma série de trocas, semelhante a um Tipo de bolha. É conceitualmente simples, não requerendo loops aninhados. O tempo médio de execução é O(n2), mas tende a O(n) se a lista estiver inicialmente quase classificada.
O algoritmo encontra o primeiro lugar onde dois elementos adjacentes estão na ordem errada e os troca. Ele tira vantagem do fato de que realizar uma troca pode introduzir um novo par adjacente fora de ordem próximo aos elementos trocados anteriormente. Ele não assume que os elementos à frente da posição atual são classificados, portanto, ele só precisa verificar a posição diretamente anterior aos elementos trocados.

#### Complexidade:

Pior caso: O(n^2);
Melhor caso: O(n);
Média: O(n^2);
Complexidade do espaço de pior caso: O(1) auxiliar.

#### Implementação:
##### PHP:
### Stooge sort
#### Descrição:

O Stooge Sort é um algoritmo de classificação recursiva. É um algoritmo de classificação ineficiente, mas interessante. Ele divide a matriz em duas partes sobrepostas (2/3 cada). Em seguida, realiza a classificação na primeira parte 2/3 e, em seguida, realiza a classificação na última parte 2/3. Depois disso, a classificação é feita na primeira parte 2/3 para garantir que a matriz seja classificada. A ideia principal é que a classificação da parte sobreposta duas vezes troca os elementos entre as outras duas seções de acordo.

#### Funcionamento:

O algoritmo deste método se dá da seguinte forma:
* Se o valor no início for maior do que o valor no final, troque-os.
* Classifique recursivamente os primeiros 2/3 da matriz.
* Classifique recursivamente os últimos 2/3 partes do array.
* Novamente, classifique os primeiros 2/3 da matriz.
* A matriz é finalmente classificada.
Exemplo:
Entrada: 2 4 5 3 1
Saída: 1 2 3 4 5
* Inicialmente, troque 2 e 1 seguindo a etapa 1 acima.
** 1 4 5 3 2
* Agora, classifique recursivamente 2/3 dos elementos iniciais.
** 1 4 5 3 2
** 1 3 4 5 2
* Em seguida, classifique recursivamente os últimos 2/3 dos elementos.
** 1 3 4 5 2
** 1 2 3 4 5
* Novamente, classifique os 2/3 iniciais dos elementos para confirmar se os dados finais estão classificados.
** 1 2 3 4 5

#### Complexidade:

Média: O (n ^ log (3) /log(1.5))
Melhor caso: O (n ^ log (3) /log(1.5))
Pior caso: O (n ^ log (3) /log(1.5))
Complexidade de espaço de pior caso: O (n)

#### Implementação:
##### PHP:

* ↑ http://wiki.icmc.usp.br/images/7/7a/ICC2_06.Ordenacao_parte1.pdf
* 1 2 3 4 5 6 7 https://rosettacode.org/wiki/Category:Sorting_Algorithms
* ↑ https://osprogramadores.com/blog/2017/08/24/estrutura-bubblesort/
* 1 2 https://panda.ime.usp.br/panda/static/pythonds_pt/05-OrdenacaoBusca/OBubbleSort.html
* ↑ https://www.programiz.com/dsa/heap-sort
* ↑ https://pt.slideshare.net/GustavoSantos524/gnome-sort-149135415
* ↑ https://ao.ert.wiki/wiki/Gnome_sort
* ↑ https://iq.opengenus.org/stooge-sort/
* ↑ https://www.geeksforgeeks.org/stooge-sort/