 |
|
Você está aqui: Java ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
|
Java Insertion Sort - Como ordenar um vetor de inteiros usando a ordenação Insertion Sort (Ordenação por Inserção)Quantidade de visualizações: 4249 vezes |
|
|
A ordenação Insertion Sort, Insertion-Sort, ou Ordenação por Inserção, possui uma complexidade de tempo de execução igual à ordenação Bubble Sort (Ordenação da Bolha), ou seja, O(n2). Embora mais rápido que o Bubble Sort, e ser um algorítmo de ordenação quadrática, a ordenação Insertion Sort é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação, porém, nunca recomendada para um grande conjunto de dados. A forma mais comum para o entendimento da ordenação Insertion Sort é compará-la com a forma pela qual algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam à ordenação. A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até não receber mais cartas. Esta é a ideia por trás da ordenação por inserção. Percorra as posições do vetor (array), começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no sub-vetor ordenado à esquerda daquela posição. Vamos ver a implementação na linguagem Java agora? Observe o seguinte código, no qual temos um vetor de inteiros com os elementos {4, 6, 2, 8, 1, 9, 3, 0, 11}:
package arquivodecodigos;
public class Estudos{
// método que permite ordenar o vetor de inteiros
// usando a ordenação Insertion Sort
public static void insertionSort(int[] vetor){
// percorre todos os elementos do vetor começando
// pelo segundo elemento
for(int i = 1; i < vetor.length; i++){
int atual = vetor[i]; // o valor atual a ser inserido
// começa a comparar com a célula à esquerda de i
int j = i - 1;
// enquanto vetor[j] estiver fora de ordem em relação
// a atual
while((j >= 0) && (vetor[j] > atual)){
// movemos vetor[j] para a direita e decrementamos j
vetor[j + 1] = vetor[j];
j--;
}
// colocamos atual em seu devido lugar
vetor[j + 1] = atual;
}
}
public static void main(String args[]){
// vamos criar um vetor com 9 elementos
int valores[] = {4, 6, 2, 8, 1, 9, 3, 0, 11};
// exibimos o vetor na ordem original
System.out.println("Ordem original:\n");
for(int i = 0; i < valores.length; i++){
System.out.print(valores[i] + " ");
}
// vamos ordenar o vetor agora
insertionSort(valores);
// exibimos o vetor ordenado
System.out.println("\n\nOrdenado:\n");
for(int i = 0; i < valores.length; i++){
System.out.print(valores[i] + " ");
}
}
}
Ao executar este código Java nós teremos o seguinte resultado: Sem ordenação: 4 6 2 8 1 9 3 0 11 Ordenada usando Insertion Sort: 0 1 2 3 4 6 8 9 11 |
|
 Link para compartilhar na Internet ou com seus amigos: |
|
| Anúncio Patrocinado | |
|
|
GNU Octave ::: Dicas & Truques ::: Matemática e Estatística |
Como calcular raiz quadrada usando a função sqrt() do GNU OctaveQuantidade de visualizações: 4020 vezes |
|
A raiz quadrada de um algarismo é dada por um número positivo n, que ao ser elevado ao quadrado (multiplicado por ele mesmo), se iguala a x. Na área da matemática, a raiz quadrada auxilia na resolução de vários problemas, entre eles as equações de segundo grau e o Teorema de Pitágoras. Relembrando que a raiz quadrada é o inverso da potenciação com expoente dois, temos que: \[\sqrt{9} = 3\] então, pela potenciação: \[3^2 = 9\] Agora veremos como calcular a raiz quadrada usando a função sqrt() do GNU Octave. Se você ainda não o fez, abra o GNU Octave e digite a seguinte expressão na janela de comandos: >> raiz = sqrt(9) [ENTER] raiz = 3 >> Agora veja como podemos usar a função sqrt() em um script do GNU Octave:
valor = input("Informe o valor desejado: ");
raiz = sqrt(valor);
fprintf("A raiz quadrada do valor informado é %d\n",
raiz);
Uma saída deste código poderia ser: Informe o valor desejado: 25 A raiz quadrada do valor informado é 5 >> É importante ter em mente que a função sqrt() do GNU Octave retorna um erro caso o valor do radicando for negativo. Veja: Informe o valor desejado: -5 A raiz quadrada do valor informado é error: octave_base_value::int64_scalar_value (): wrong type argument 'complex scalar' >> |
PHP ::: Dicas & Truques ::: Strings e Caracteres |
Como concatenar strings em PHP usando o operador "."Quantidade de visualizações: 47318 vezes |
|
Todas as linguagens de programação oferecem o seu operador de concatenação, que nos permite juntar palavras, frases, textos e valores de variáveis. Na maioria das linguagens o operador de concatenação é o sinal de adição "+". Porém, em PHP, a concatenação é feita usando-se o operador ".". Veja um exemplo abaixo de como usá-lo: <?php $nome = "Carlos"; $cidade = "São Paulo"; echo "Meu nome é " . $nome . " e eu moro em " . $cidade . "."; ?> |
AutoCAD VBA ::: Dicas & Truques ::: Comprimentos, distâncias e ângulos |
Como calcular a distância entre dois pontos no AutoCAD usando AutoCAD VBAQuantidade de visualizações: 102 vezes |
|
Em várias situações nós precisamos calcular e retornar a distância entre dois pontos na área de desenho do AutoCAD. Esta tarefa pode ser facilmente realizada com o uso da linguagem AutoCAD VBA. Neste exemplo nós usaremos a função ThisDrawing.Utility.GetPoint() para pedir para o usuário selecionar dois pontos na área de desenho e em seguida vamos mostrar a distância entre eles. Veja o código AutoCAD VBA completo para o exemplo:
' Esta macro AutoCAD VBA demonstra como podemos
' calcular a distância entre dois pontos na área de
' desenho do AutoCAD
Sub DistanciaDoisPontos()
' vamos declarar os dois pontos geométricos
Dim p As Variant
Dim q As Variant
' para guardar as coordenadas temporárias
Dim x As Double, y As Double, z As Double
' para guardar a distância
Dim distancia As Double
' vamos pedir para o usuário informar os dois pontos
p = ThisDrawing.Utility.GetPoint(, vbCrLf & _
"Indique o primeiro ponto: ")
q = ThisDrawing.Utility.GetPoint(p, vbCrLf & _
"Indique o segundo ponto: ")
' agora calculamos a distância entre os dois pontos informados
x = p(0) - q(0)
y = p(1) - q(1)
z = p(2) - q(2)
distancia = Sqr((Sqr((x ^ 2) + (y ^ 2)) ^ 2) + (z ^ 2))
' e mostramos o resultado
MsgBox "A distância entre os dois pontos é: " & distancia
End Sub
Ao executar este código AutoCAD VBA nós teremos o seguinte resultado: A distância entre os dois pontos é: 64.6029 |
JavaScript ::: Fundamentos da Linguagem ::: Estruturas de Controle |
JavaScript para iniciantes - Como testar condições em JavaScript usando if e if..elseQuantidade de visualizações: 10018 vezes |
As estruturas if (se) e if..else (se..senão) da linguagem JavaScript são muito usadas quando queremos testar condições em nossos códigos e, dependendo do resultado do teste, efetuar desvios na execução das instruções. Veja a sintáxe do if:
if(condição){
// instrução ou conjunto de instruções
}
A condição é qualquer teste que resulte em um valor boolean (true ou false). Veja, por exemplo, como podemos verificar se um valor é maior que 10:
<html>
<head>
<title>Estudos JavaScript</title>
</head>
<body>
<script type="text/javascript">
var valor = 15;
// vamos testar se o valor é maior que 10
if(valor > 10){
document.write("O valor é maior que 10.");
}
</script>
</body>
</html>
Ao executarmos este código, o texto "O valor é maior que 10." será exibido na tela. Porém, também gostaríamos de exibir uma mensagem caso o valor não for maior que 10. Para isso podemos usar a cláusula else. Veja:
<script type="text/javascript">
var valor = 5;
// vamos testar se o valor é maior que 10
if(valor > 10){
document.write("O valor é maior que 10.");
}
else{
document.write("O valor NÃO é maior que 10.");
}
</script>
Ao executarmos o exemplo novamente, o texto "O valor NÃO é maior que 10." será exibido. Isso aconteceu porque, ao não satisfazer a condição do if, o fluxo de código caiu na cláusula else. Há algumas situações nas quais precisamos testar muitas condições ao mesmo tempo. Assim, além do if e else podemos empregar também a cláusula else if (senão se). Veja um exemplo no qual expandimos o exemplo anterior para testar se o valor é maior, menor ou igual a 10:
<html>
<head>
<title>Estudos JavaScript</title>
</head>
<body>
<script type="text/javascript">
var valor = 5;
// vamos testar se o valor é maior, menor ou igual a 10
if(valor > 10){
document.write("O valor é maior que 10.");
}
else if(valor < 10){
document.write("O valor é menor que 10.");
}
else{
document.write("O valor é igual a 10.");
}
</script>
</body>
</html>
Esta dica foi escrita e testada no Internet Explorer 8 e Firefox 3.6. |
C ::: Estruturas de Dados ::: Lista Ligada Simples |
Estruturas de Dados em C - Como inserir antes de um determinado nó em uma lista encadeada simples usando CQuantidade de visualizações: 1610 vezes |
|
Em algumas situações nós precisamos inserir o novo nó antes de um determinado nó na lista encadeada simples. Veja, por exemplo, uma lista com o seguintes valores: 45 | 3 | 98 | 47 Suponha que queremos inserir o valor 50 antes do 98, então o novo conteúdo da lista será: 45 | 3 | 50 | 98 | 47 Observe que neste exemplo eu tratei o caso de inserir antes do primeiro nó, ou seja, antes do 45, mas não tratei a lista vazia. Há também a questão do laço infinito caso o usuário queira inserir antes de um nó não existente (não tratada). Veja o código completo:
#include <stdio.h>
#include <stdlib.h>
// estrutura Nó
struct No{
int valor;
struct No *proximo;
};
// fim da estrutura Nó
// função que permite exibir os valores de
// todos os nós da lista
void exibir(struct No *n){
if(n != NULL){
do{
printf("%d\n", n->valor);
n = n->proximo;
}while(n != NULL);
}
else
printf("A lista esta vazia\n\n");
}
// função que permite inserir um novo nó
// antes de um determinado valor
struct No *inserir_antes_valor(struct No *n, int v, int v_antes){
// reserva memória para o novo nó
struct No *novo = (struct No*)malloc(sizeof(struct No));
novo->valor = v;
// guarda o nó antes do valor que procuramos
struct No *anterior = NULL;
struct No *temp = n; // aponta para o início da lista
// enquanto for diferente do valor que estamos procurando
while(temp->valor != v_antes){
anterior = temp; // anterior recebe temp
// e temp recebe o seu próximo
temp = temp->proximo;
}
// ATENÇÃO: não estamos tratando a condição
// de lista vazia. Para isso veja minha dica
// sobre como inserior no início da lista
// devemos inserior no início da lista?
if(anterior == NULL){
// o próximo do novo nó é o início da lista
novo->proximo = n;
n = novo; // início da lista é o novo nó
}
else{
// o proximo do anterior é o novo nó
anterior->proximo = novo;
// e o próximo do novo nó é temp
novo->proximo = temp;
}
return n;
}
// função que permite inserir nós no
// final da lista.
// veja que a função recebe o valor a ser
// armazenado em cada nó e um ponteiro para o
// início da lista. A função retorna um
// ponteiro para o início da lista
struct No *inserir_final(struct No *n, int v){
// reserva memória para o novo nó
struct No *novo = (struct No*)malloc(sizeof(struct No));
novo->valor = v;
// verifica se a lista está vazia
if(n == NULL){
// é o primeiro nó...não deve apontar para
// lugar nenhum
novo->proximo = NULL;
return novo; // vamos retornar o novo nó como sendo o início da lista
}
else{ // não está vazia....vamos inserir o nó no final
// o primeiro passo é chegarmos ao final da lista
struct No *temp = n; // vamos obter uma referência ao primeiro nó
// vamos varrer a lista até chegarmos ao último nó
while(temp->proximo != NULL){
temp = temp->proximo;
}
// na saída do laço temp aponta para o último nó da lista
// novo será o último nó da lista...o campo próximo dele deve
// apontar para NULL
novo->proximo = NULL;
// vamos fazer o último nó apontar para o nó recém-criado
temp->proximo = novo;
return n; // vamos retornar o início da lista intacto
}
}
int main(int argc, char *argv[])
{
// declara a lista
struct No *inicio = NULL;
// vamos inserir quatro valores no final
// da lista
inicio = inserir_final(inicio, 45);
inicio = inserir_final(inicio, 3);
inicio = inserir_final(inicio, 98);
inicio = inserir_final(inicio, 47);
// vamos exibir a lista
puts("Valores atuais:\n");
exibir(inicio);
// vamos inserir o valor 50 antes do 98
inicio = inserir_antes_valor(inicio, 50, 98);
// vamos exibir a lista novamente
puts("\nValores agora:\n");
exibir(inicio);
puts("\n\n");
system("pause");
return 0;
}
|
Desafios, Exercícios e Algoritmos Resolvidos de C |
Veja mais Dicas e truques de C |
Dicas e truques de outras linguagens |
|
Delphi - Como calcular o cateto oposto dadas as medidas da hipotenusa e do cateto adjascente em Delphi Python - Como converter Metros Quadrados em Quilômetros Quadrados em Python - Python para Física e Engenharia |
Códigos Fonte |
 Software de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimentoDiga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais |
 Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesTenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais |
Linguagens Mais Populares |
|
1º lugar: Java |
