# data[].attributes.headline
Introdução sobre os algoritmos de ordenação

# data[].attributes.subject
Introdução sobre os algoritmos de ordenação

# data[].attributes.body
Todos os algoritmos são baseados em uma maneira passo a passo, sequencial, lógica e explícita de resolver problemas. Falando em ordenação, o objetivo desta operação é transformar uma sequência aleatória de dados em uma determinada ordem. Uma das principais razões para ordenar uma sequência é acessar seus dados de forma mais eficiente. Além disso, fornece uma organização que facilita a pesquisa, análise e observação do comportamento que está sendo estudado. Vários desses algoritmos foram criados para otimizar o tempo de ordenação e lidar com diferentes características de uma sequência: considerar se ela é parcialmente ordenada, completamente caótica e outras possibilidades. Dependendo da aplicação, escolher o algoritmo certo terá uma vantagem no momento da execução do código.

# data[].attributes.attachment_caption
Select-sort - video explicando o funcionamento do algoritmo.

# data[].attributes.body
A ordenação por seleção é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos.

# data[].attributes.body
É composto por dois laços, um laço externo e outro interno. O laço externo serve para controlar o índice inicial e o interno percorre todo o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Isso ficará mais explícito no exemplo.

Exemplo:

vetor = 9 - 7 - 8 - 1 - 2 - 0 - 4

O primeiro laço o índice inicial é 0. O laço mais interno começa do índice 1 (índice_inicial_externo + 1) e percorre o vetor até achar o menor elemento, neste caso o número zero. O zero passa para a posição inicial do vetor que na primeira iteração do laço é 0.

0 - 7 - 8 - 1 - 2 - 9 - 4

Ao fim do laço interno, o laço externo incrementa uma unidade, agora a posição inicial do vetor passa a ser 1, pois o zero já se encontra no lugar dele, não é preciso mais fazer verificações pois ele é o menor elemento deste vetor. Agora o processo se repete, buscando o segundo menor elemento, neste caso o um.

0 - 1 - 8 - 7 - 2 - 9 - 4

Consequentemente o terceiro menor, quarto menor,...

Assim sucessivamente até o vetor está ordenado.

0 - 1 - 2 -7 - 8 - 9 - 4
...
0 - 1 - 2 - 4 - 8 - 9 - 7
...
0 - 1 - 2 - 4 - 7 - 9 - 8
...

0 - 1 - 2 - 4 - 7 - 8 - 9

# data[].attributes.attachment_caption
Estrutura básica do algoritmo. Os pseudocódigos só iteram até a penúltima posição, depois disso só restará o último elemento, que já estará na posição correta.

# data[].attributes.body
Também é possível pensar em uma estrutura mais conveniente implementando um método que retorna o índice do menor elemento de um vetor num certo intervalo (nesse exemplo, será o método min). O pseudocódigo é dado a seguir (ele utiliza o 1 como índice inicial).

1. selectionSort(A[1...n])
2. |  para i ← 1 até n - 1
3. |  |   minIndex ← min(A, i, n)
4. |  |   trocar(A, i, minIndex)
5. |  fim_para
6. fim_selectionSort

O método min é (k ≤ l)

1. min(A[1...n], k, l)
2. |  minIndex ← k
3. |  para i ← k + 1 até l
4. |  |   se(A[minIdex] > A[i])
5. |  |   |   minIndex ← i
6. |  |   fim_se
7. |  fim_para
8. |  retorne minIndex
9. fim_min

O método trocar(A, i, j) troca os valores das posições i e j do vetor A

1. trocar(A, i, j)
2. |  temp ← A[i]
3. |  A[i] ← A[j]
4. |  A[j] ← temp
5. fim_trocar

# data[].attributes.body
O Selection Sort segue uma rotina bem simples e direta: encontrar o menor elemento e colocá-lo na primeira posição. A ordenação nada mais é do que aplicar essa rotina repetidas vezes para o restante do array;

O Selection sort é in-place e O(n2);

A implementação clássica do Selection Sort não é estável;

Embora sejam da mesma classe de complexidade, o Selection Sort, na prática, é mais lento do que o Insertion Sort;

O Selection Sort não é considerado um algoritmo eficiente para grandes entradas.

# data[].attributes.headline
Site com animações dos algoritmos de ordenação

# data[].attributes.subject
Site com animações dos algoritmos de ordenação

# data[].attributes.body
Site contendo as animações de cada algoritmo de ordenação. Podendo facilitar a visualização do funcionamento dos mesmos.

# data[].attributes.attachment_link.readable_text
DISCUSSION
These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to:

Show how each algorithm operates.

Show that there is no best sorting algorithm.

Show the advantages and disadvantages of each algorithm.

Show that worse-case asymptotic behavior is not always the deciding factor in choosing an algorithm.

Show that the initial condition (input order and key distribution) affects performance as much as the algorithm choice.

The ideal sorting algorithm would have the following properties:

Stable: Equal keys aren't reordered.

Operates in place, requiring O(1) extra space.

Worst-case O(n·lg(n)) key comparisons.

Worst-case O(n) swaps.

Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

Sorting is a vast topic; this site explores the topic of in-memory generic algorithms for arrays. External sorting, radix sorting, string sorting, and linked list sorting-all wonderful and interesting topics-are deliberately omitted to limit the scope of discussion.

# data[].attributes.attachment_link.description
Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions.

# data[].attributes.headline
Vantagens e Desvantagens do uso do Selection Sort

# data[].attributes.subject
Vantagens e Desvantagens do uso do Selection Sort

# data[].attributes.body
Vantagens:

Ele é um algoritmo simples de ser implementado em comparação aos demais;

Não necessita de um vetor auxiliar (in-place);

Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória;

Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.

Desvantagens:

Ele é um dos mais lentos para vetores de tamanhos grandes;

Ele não é estável;

Ele faz sempre  comparações (n^2-n)/2, independentemente do vetor estar ordenado ou não.

# data[].attributes.body
Segundo Groner no livro Estruturas de dados e algoritmos com JavaScript, Selection Sort é um algoritmo de ordenação por comparação in-place, isso significa que a memória adicional requerida é independente do tamanho do vetor que está sendo ordenado. Além disso, possui complexidade O(n ²) pois contém dois laços aninhados responsáveis pela complexidade quadrática.

Diversos artigos acerca do algoritmo foram inscritos, realizando uma busca no Google Scholar foi possível obter como resultado cerca de 241.000 artigos de revisão.

Dentre esses, podemos citar alguns:

Optimized Selection Sort Algorithm is faster than Insertion Sort Algorithm: a Comparative Study (O algoritmo de ordenação por seleção otimizado é mais rápido que o algoritmo de ordenação por inserção: um estudo comparativo): O algoritmo de ordenação por seleção otimizado é um novo algoritmo de ordenação que foi desenvolvido para resolver as deficiências dos atuais algoritmos de ordenação populares. O objetivo desta pesquisa é realizar uma extensa análise empírica de Ordenação por Seleção Otimizada contra Algoritmos Ordenação por Seleção e Ordenação por Inserção. Os resultados provaram que a Ordenação por Seleção Otimizada é muito mais eficiente que o Algoritmo de Ordenação por Seleção; Além disso, a análise suporta o fato de que a Ordenação por Seleção Otimizada é melhor que a Ordenação por Inserção no pior cenário.

A sort implementation comparing with Bubble sort and Selection sort (Uma implementação de classificação comparando com a classificação por bolha e a classificação por seleção): Hoje, a implementação da classificação leva a um tempo de pedido menor e mais fácil. Nosso objetivo neste artigo é tentar introduzir um algoritmo com menor custo de ordenação por bolha e quase o mesmo que ordenação por seleção. Uma maneira é a inserção ordenada de elementos em outro array. Sort é um algoritmo que organiza todos os elementos de uma matriz, ordenadamente. Este algoritmo tem forma sequencial. A ordem de complexidade da ordenação por seleção é quase menor do que a ordenação por bolha.