Estruturação, conceitos e fundamentação
Por: Rafael Viana • 8/9/2015 • Projeto de pesquisa • 1.686 Palavras (7 Páginas) • 151 Visualizações
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–;
}
...