Estruturação, conceitos e fundamentação

Insertion sort

Estruturação, conceitos e fundamentação

 é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer

O seu beneficio é poder ser muito mais rápido do que qualquer outro método  básico conhecido e sua principal característica consiste em ordenar o arranjo utilizando um sub-arranjo ordenado localizado em seu inicio, e a cada novo passo, acrescentamos a este sub-arranjo mais um elemento, até que atingimos o último elemento do arranjo fazendo assim com que ele se torne ordenado


Aplicações que fazem uso da técnica
Suas aplicações podem ser utilizadas neste caso, usando-o como exemplo

FUNÇÃO INSERTION_SORT (A[], tamanho)
.         Variáveis
                i, J
                eleito
PARA I <- 1 ATÉ (tamanho-1) FAÇA
eleito <- A[i];
j <- i-1;
ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA
A[j+1]:= A[j];
j:=j-1;
FIM_ENQUANTO
A[j+1] <- eleito;  
 FIM_PARA
FIM


Discussão comparativa entre esta técnica e outras conhecidas / utilizadas

Como podemos ver, as diferenças entre esta ténica comparada com as outras conhecidas, é a sua eficiência e rapidez e em relação aos outros, o insertion sort verifica se por exemplo o numero 5 é maior que o 3, já que essa condição é falsa, logo, ele não troca de lugar.
É verificado se o quatro é menor que o 5 e o 3, ele só é menor que o 5, então

os dois trocam de posição. É verificado se o 2 é menor que o 5, 4 e o 3, como ele é menor que 3, então o 5 passa a ocupar a posição do 2, o 4 ocupa a
posição do 5 e o 3 ocupa a posição do 4, assim a posição do 3 fica vazia e o 2 passa para essa posição.

Vulnerabilidades, falhas e melhorias

Suas vulnerabilidades e falhas são para as grandes listas, o que as tornam extremamente lentas sua funcionalidade, portanto, esse método é rápido apenas para pequenas listas. Uma ótima proposta para este método seria poder agir de forma mais eficiente nessas listas complexas.

Bubble Sort

Estruturação, conceitos e fundamentação

O bubble sort é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes,o que o torna extremamente lento, a cada passagem fazendo flutuar para o topo o menor 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.

Aplicações que fazem uso da técnica

Código em C:
void bubble( int v[], int qtd )
void bubble( int v[], int qtd )
{
int i;
int j;
int aux;
int k = qtd – 1 ;

for(i = 0; i < qtd; i++)
{
for(j = 0; j v[j+1])
{
aux = v[j];
v[j] = v[j+1];
v[j+1]=aux;
}
}
k–;
}
}
Por exemplo:
8 | 25 | 9 | 21 | 18 |
8 é maior que 25 ?
Não, então continua a mesma coisa

8 | 25 | 9 | 21 | 18 |
25 é maior que 9 ?
Sim, então troca com o 9

8 | 9 | 25 | 21 | 18 |
25 é maior que 21 ?
Sim, então troca com o 21

8 | 9 | 21 | 25 | 18 |
25 é maior que 18 ?
Sim, então troca com o 18

Benefícios em relação às técnicas anteriores

Seus benefícios em relação aos outros métodos é poder ser um método simples para o uso, de fácil uso, podendo assim percorrer inúmeras vezes o vetor desejado.

Discussão comparativa entre esta técnica e outras conhecidas / utilizadas

Podemos fazer uma comparação do bubble sort falando sobre sua forma de atuar, justamente por essa forma de passar inúmeras vezes no vetor, a cada passagem fazendo flutuar para o topo o menor elemento da sequência

Vulnerabilidades, falhas e melhorias

Porém, temos uma vulnerabilidade neste método, já que ele passa tantas vezes no vetor, a cada vez vai ficando mais lento, A ideia é percorrer o vetor diversas vezes o que o torna extremamente lento, por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes. Seria de grande ajuda uma melhoria nesta parte.




Selection sort


Estruturação, conceitos e fundamentação

Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.

Neste algoritmo de ordenação é escolhido um número a partir do primeiro, este número escolhido é comparado com os números a partir da sua direita, quando encontrado um número menor, o número escolhido ocupa a posição do menor número encontrado. Este número encontrado será o próximo
número escolhido, caso não for encontrado nenhum número menor que este


escolhido, ele é colocado na posição do primeiro número escolhido, e o próximo número à sua direita vai ser o escolhido para fazer as comparações. É repetido esse processo até que a lista esteja ordenada.

Podemos dar como exemplo a aplicação desta forma


Aplicações que fazem uso da técnica
Código em C:
void selectionSort(int vetor[],int tam)
{
int i,j;
int min,aux;
for (i=0;i
{
min=i;
for (j=i+1;j
{
if (vetor[j]
min=j;
}
aux=vetor[i];
vetor[i]=vetor[min];
vetor[min]=aux;
}
}

Benefícios em relação às técnicas anteriores
Como podemos ver neste método, seu beneficio em relação as outras tenicas conhecidas é de poder passar o seu menor valor para a primeira posição e depois o menor para a segunda posição de forma sucessivamente.

Discussão comparativa entre esta técnica e outras conhecidas / utilizadas

Logo, podemos comparar que esta forma são procurados sucessivos elementos que se encontram fora de ordem e retira o elemento da lista e depois insere o elemento de forma ordenada.

Vulnerabilidades, falhas e melhorias

Podemos encontrar uma vulnerabilidade em relação as grandes listas, pois Esse tipo de ordenação em pequenas listas é rapido, sendo extremamente lento para grandes listas. O que poderia ser melhorado a eficiência.



Quick sort

Estruturação, conceitos e fundamentação

O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista

para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.

Aplicações que fazem uso da técnica

Código em C:
void quicksort(int array[], int begin, int end) {
if(end – begin > 0) {
int aux;
int pivot = array[begin];
int left = begin + 1;
int right = end;
while(left < right) {
if(array[left] pivot) {
left–;
}