oi gente eu tenho que fazer um trabalho explicando oq ele faz sera que alguem poderia me dar um exemplo desse metodo pois procurei e achei um no wikipedia mais so que por la eu não entendi pois ele fala resumidamente como funciona esse metodo sera que alguem poderia me dar um exemplo em java.Se alguem poder me ajudar ficaria muito grata obrigada.
Talvez isso te ajude,
segundo Cormen e outros, o método de ordenação por inserção é similar ao processo de organização de cartas que uma pessoa faz.
Segundo ele, você deve considerar as cartas colocadas na mesa (com o verso para cima) e a mão esquerda que irá segurar as cartas vazias.
Levanta-se a primeira carta e coloque-a na mão esquerda.
Levante a segunda carta
Compare-a com a primeira, se menor, deverá ser posicionada a esquerda, caso contrário a direita.
Ao ser colocada a esquerda, você deve observa o deslocamento de todas as cartas para uma posição mais a direita, no final do processo, elas estarão em ordem.
Bom dessa forma, um método que realize o processo de ordenação por inserção pode seguir dois caminhos:
- o vetor está vazio, então você recebe um novo valor e insere nele, recebe o segundo valor e faz a inserção antes ou depois da primeira posição e assim sucessivamente.
- o vetor está completo, vamos supor com 3 posições, então inicia-se o processo na segunda posição, comparando-o com a primeira, depois com a terceira até o fim.
exemplos em java, para o primeiro caso:
public static void insert(int[] vetor, int valor, int tam_logico) {
// localiza a posição de inserção
int i=0;
while( i<tam_logico && vetor[i] < valor ) {
i++;
}
// se i for menor que o tamanho lógico, significa que a inserção não será na úlima posição e
// você terá que "deslocar" os valores para realizar a inserção
for(int t = tam_logico ; t>i ; t-- ) {
vet[t] = vet[t-1];
}
// o valor contido na posição i, agora está em duas posições do vetor, logo você pode inserir o novo valor na posição i.
vet[i] = valor;
}
Segundo caso, em que você recebe um vetor completo, mas deorganizados.
public static void insertSort(int[] vetor) {
for(int i=1 ; i<vetor.length ; i++) {
int valor = vetor[i];
for( int j=0 ; j<i ; j++) {
if( vetor[j] > valor ) {
for(int t=i ; t>j ; t-- ) {
vetor[t] = vetor[t-1];
}
vetor[j] = valor;
break;
}
}
}
}
espero que te ajude.
fw
muito obrigada eu tentei fazer assim ta certo
package javaapplication20;
public class QuickSort {
public static int v[]={9,3,4,0,2,6,1,8,10,7,5};
public static void main(String[] args) {
QuickSort qs = new QuickSort();
qs.quickSort(v,0,10);
for (int ni = 0; ni < v.length; ni++) {
System.out.println(v[ni]);
}
}
public void quickSort ( int[] c,int a, int j){
int i=a, b=j, h;
int x=c[(a+j)/2];
do
{
while (c[i]<x) i++;
while (c[b]>x) b--;
if (i<=b)
{
h=c[i]; c[i]=c[b]; c[b]=h;
i++; b--;
}
} while (i<=b);
if (a<b) quickSort(c,a,b);
if (i<=j) quickSort(c,i, j);
}
}
e agora eu tenho de fazer o teste de mesa vc pode me explicar como fazer da para fazer no net beans?
grata muito obrigada mesmo
hum,
você utilizou o quicksort, que é considerado o melhor algoritmo de ordenação em memória, porém esse algoritmo não é considerado uma técnica de inserção. Até onde eu me lembro, ele é um algoritmo de seleção não estável…
bom mas deixa para lá,
com relação ao teste de mesa, se você quiser usar o netbeans, rode o seu programa passo a passo (step-by-step) F7 e depois F8.
em watches você poderá monitorar as variáveis.
ok?
Mais uma coisa,
você pode usar for dessa forma:
for(int i:v)
System.out.println(i);
para substituir:
for (int ni = 0; ni < v.length; ni++) {
System.out.println(v[ni]);
}
até mais
desculpa passei errado queria saber se esse aqui ta certo
package insertionsort;
public class Main {
public static int colecao[]={2,9,3,0,4,6,1,8,10,7,5};
public static void main(String[] args) {
for (int i = 0; i < colecao.length; i++)
{
int n = colecao[i];
int j = i;
while (j > 0 && colecao[j - 1] > n)
{
colecao[j] = colecao[j - 1];
j = j - 1;
}
colecao[j] = n;
}
}
}Eu acredito que sim.
fw
mais se eu quizer que aparece na tela eu coloco aonde o System.in
Grata pela força
[code]package insertionsort;
public class Main {
public static int colecao[]={2,9,3,0,4,6,1,8,10,7,5};
public static void main(String[] args) {
for (int i = 0; i < colecao.length; i++)
{
int n = colecao[i];
int j = i;
while (j > 0 && colecao[j - 1] > n)
{
colecao[j] = colecao[j - 1];
j = j - 1;
}
colecao[j] = n;
}
for(int i:colecao)
System.out.println(i);
}
}[/code]muito obrigada foco muito grata por isso.