A maior rede de estudos do Brasil

Quais são os métodos de ordenação?

Quais as diferenças e empregabilidade dos métodos de ordenação Selection Sort, Insertion Sort e Bubble Sort?

Estrutura de Dados IESTÁCIO EAD

7 resposta(s) - Contém resposta de Especialista

User badge image

RD Resoluções Verified user icon

Há mais de um mês

Para responder essa pergunta devemos colocar em prática nosso conhecimento sobre Algoritmo e Estrutura de Dados.


Os algoritmos de ordenação são muito utilizados na resolução de problemas computacionais, servem para ordenar/organizar uma lista de números ou palavras de acordo com a sua necessidade. 

O Selection Sort a cada iteração, procura em toda a parcela não ordenada do vetor pelo menor (ou maior) elemento e o coloca na posição correta. Assim, na i-ésima iteração, o i-ésimo menor elemento vai para a posição i, e assim por diante.

Já o Insertion Sort, itera-se crescentemente entre as posições. Para cada posição, pega seu elemento e regride-o no vetor até encaixá-lo na posição correta (quando encontrar o primeiro elemento menor que ele).

Por fim o Bubble sort seleciona dois elementos adjacentes e troca-os de posição se, e somente se, estiverem fora de ordem. Faz isso com todos pares de elementos a cada iteração. Ao final da mesma, o menor (ou maior) elemento ainda não ordenado estará na posição correta. Repete-se isso até o final.

A escolha entre qual método de ordenação será utilizado depende da quantidade de elementos que se deseja ordenar, o poder de processamento da máquina e o tempo que o usuário deseja que sejam ordenados o vetores.


Portanto, enquanto que o Selection Sort vai ordenando seguindo a ordem final desejada, o Insertion vai ordenando a medida que vai lendo o vetor não ordenado e o Bubble sort vai fazendo a interação entre 2 a 2 elementos até estar totalmente ordenado, sendo que a escolha do método de ordenação depende da velocidade de processamento da máquina, quantidade de elementos a serem ordenados e o tempo de processamento que o usuário deseja (mais rápido ou não importando o tempo).

Para responder essa pergunta devemos colocar em prática nosso conhecimento sobre Algoritmo e Estrutura de Dados.


Os algoritmos de ordenação são muito utilizados na resolução de problemas computacionais, servem para ordenar/organizar uma lista de números ou palavras de acordo com a sua necessidade. 

O Selection Sort a cada iteração, procura em toda a parcela não ordenada do vetor pelo menor (ou maior) elemento e o coloca na posição correta. Assim, na i-ésima iteração, o i-ésimo menor elemento vai para a posição i, e assim por diante.

Já o Insertion Sort, itera-se crescentemente entre as posições. Para cada posição, pega seu elemento e regride-o no vetor até encaixá-lo na posição correta (quando encontrar o primeiro elemento menor que ele).

Por fim o Bubble sort seleciona dois elementos adjacentes e troca-os de posição se, e somente se, estiverem fora de ordem. Faz isso com todos pares de elementos a cada iteração. Ao final da mesma, o menor (ou maior) elemento ainda não ordenado estará na posição correta. Repete-se isso até o final.

A escolha entre qual método de ordenação será utilizado depende da quantidade de elementos que se deseja ordenar, o poder de processamento da máquina e o tempo que o usuário deseja que sejam ordenados o vetores.


Portanto, enquanto que o Selection Sort vai ordenando seguindo a ordem final desejada, o Insertion vai ordenando a medida que vai lendo o vetor não ordenado e o Bubble sort vai fazendo a interação entre 2 a 2 elementos até estar totalmente ordenado, sendo que a escolha do método de ordenação depende da velocidade de processamento da máquina, quantidade de elementos a serem ordenados e o tempo de processamento que o usuário deseja (mais rápido ou não importando o tempo).

User badge image

Lucas

Há mais de um mês

 

Os três algoritmos mais básicos de ordenação. A implementação é em Java.

O bubble sort consiste em prover, em cada passo i, os menores elementos para o início do vetor, de tal forma que o i-ésimo menor estará na sua posição correta.

O insertion sort consiste em manter os i primeiros elementos ordenados entre si. No passo i, insere o i+1 elemento na posição correta entre os i primeiros.

Já o selection sort consiste em, a cada passo i, colocar na i-ésima posição o menor elemento entre os n-i elementos restantes.

Abaixo seguem as implementações:


public void insertionSort(int a[]) {
for (int i=1;i< a.length;i++) {
for (int j=i;j>0;j--){
if (a[j]< a[j-1]) {
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
else {
break;
}
}
}
}


public void selectionSort(int a[]) {
for (int i=0;i< a.length-1;i++){
int menor = i;
for (int j=i+1;j< a.length;j++) {
if (a[j]< a[menor]){
menor = j;
}
}
int temp = a[menor];
a[menor] = a[i];
a[i] = temp;
}
}


public void bubbleSort(int[] a) {
for (int i=0;i< a.length;i++) {
for (int j=a.length-1;j>i;j--) {
if (a[j]< a[j-1]) {
int temp = a[j];
a[j]= a[j-1];
a[j-1] = temp;
}
}
}
}
User badge image

Aluna

Há mais de um mês

Métodos de Ordenação Simples: Bubble Sort, Insertion Sort e Selection Sort 

 

ü  BUBBLE SORT

 

O Bubble Sort é um algoritmo de ordenação simples que precisa de O(n2) comparações para ordenar n itens.

Ele é um dos mais simples algoritmos de ordenação conhecidos, mas geralmente é considerado muito

ineficiente para trabalhos que ordenam um grande número de elementos. É essencialmente equivalente ao

insertion sort --- ele compara e troca os mesmos pares de elementos, apenas em uma ordem diferente.

Apesar de serem muito simples, o insertion sort e o bubble sort tendem a ser os mais eficientes algoritmos de

ordenação que se destinam a ordenar um pequeno número de elementos.

O algoritmo bubble sort faz:

1. compara elementos adjacentes. Se o primeiro é maior do que o segundo, então a troca é realizada.

2. faz isto para cada par de elementos adjacentes, começando com os dois primeiros e terminando com

os dois últimos. Neste ponto o último elemento deve ser o maior de todos.

3. repete os passos para todos os elementos exceto para o último.

4. continua repetindo, cada vez com um elemento a menos, até não existam mais pares para se

comparar.

void bubbleSort(int array[], int length)

{

int i, j, temp;

for(i = length - 1; i > 0; i--)

for(j = 0; j < i; j++)

if(array[j] > array[j+1]) /* compara elementos vizinhos */

{

temp = array[j]; /* troca array[j] e array[j+1] */

array[j] = array[j+1];

array[j+1] = temp;

}

}

 

Casos a considerar:

Melhor caso: Verifica-se quando o vetor já está ordenado.

Pior caso: Verifica-se quando o vetor está ordenado na ordem inversa.

Neste algoritmo tanto o melhor caso, como o pior caso tem ordem "n2" porque em ambos os casos os ciclos

são sempre realizados até ao fim, mesmo quando os elementos já estão ordenados. 

 

ü  INSERTION SORT

 

O Insertion Sort é um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este

algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os

elementos mais a esquerda ordenados.

Obs.: Para colocar em ordem decrescente experimente trocar o > por < dentro do laço mais interno.

void insertion(int v[], int n)

{

int i, j, x;

for(j=1;j<n;j++) {

x = v[j];

for(i=j-1;i>=0 && v[i]>x;--i)

v[i+1] = v[i];

v[i+1] = x;

}

}

Casos a considerar:

Melhor caso: quando o array já está ordenado. Neste caso a comparação no laço interno sempre falhará na

primeira comparação e o tempo de execução dependerá apenas do laço externo. O tempo de execução

obedecerá a uma função linear e a complexidade do algoritmo será de O(n).

 

Pior caso: quando o array está na ordem inversa. Nesta situação para cada iteração do laço externo, o laço

interno executará n-1 vezes, onde n é o valor da variável j no laço externo. Temos que a complexidade de

tempo do algoritmo neste caso será de O(n(n-1)) = O(n2-n) = O(n2). 

 

ü  SELECTION SORT

 

O Selection Sort é um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar

o menor deles e movê-lo para uma posição final.

A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles.

1. No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior

item está agora na posição N.

2. No segundo passo você faz uma varredura apenas nos N-1 elementos. O maior dos itens é troca de

posição com o item na posição N-1. Assim o maior de todos os itens está agora na última posição; o

segundo maior na segunda maior posição.

3. Este processo é repetido, com um item sendo colocado na sua posição correta a cada vez.

4. Depois de N passos, a coleção inteira de dados está ordenada.

Uma variação simples é encontrar o menor item a cada vez e colocá-lo na frente.

Para ordenar em ordem decrescente, o maior item é encontrado a cada vez e movido para a frente.

void selectionSort(int vetor[],int tam)

{

int i,j;

int min,aux;

for (i=0;i<tam-1;i++)

{

min=i;

for (j=i+1;j<tam;j++)

{

if (vetor[j]<vetor[min])

min=j;

}

aux=vetor[i];

vetor[i]=vetor[min];

vetor[min]=aux;

}

}

Casos a considerar:

Pior e melhor caso: O(n2)

User badge image

Vitor

Há mais de um mês

Só esqueceu de especificar a linguagem né?

Essa pergunta já foi respondida por um dos nossos especialistas