Ordenar indices de vetores (em C) , como?

Gordon · 16-04-2005, 14:41

Ja tentei mas sempre da algum erro de logica, entao como posso pegar , por exemplo um vetor v[50] e criar um outro y[50], com os indices de v em ordem crescente?

vlw

Wormer · 16-04-2005, 15:03

Aqui tem vários exemplos de algoritmos: http://yagni.com/combsort/index.php

Gordon · 16-04-2005, 15:32

Citação:

Postado Originalmente por Wormer

Aqui tem vários exemplos de algoritmos: http://yagni.com/combsort/index.php

cara nao achei nada la q resolvesse meu problema, mas valew tava procurando info sobre o quicksort tb!

Gordon · 16-04-2005, 19:51

tentei aprender o quicksort sozinho mas nao consegui implementar ele no meu prog... ele eh a melhor solucao , a mais inteligente.... mas sera q alguem ai pode me dar uma dica pra resolver isso de uma outra maneira , nem q seja bem ruim, mas q funcione?

flw
[]´s

pflynn · 16-04-2005, 20:17

Citação:

tentei aprender o quicksort sozinho mas nao consegui implementar ele no meu prog... ele eh a melhor solucao , a mais inteligente.... mas sera q alguem ai pode me dar uma dica pra resolver isso de uma outra maneira , nem q seja bem ruim, mas q funcione?

O algoritimo quicksort é tão utilizado que ele é implementado por uma funcão na biblioteca padrão:

Código:


#include <stdlib.h>

 void
     qsort(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *));

Gordon · 16-04-2005, 21:56

Citação:

Postado Originalmente por pflynn

O algoritimo quicksort é tão utilizado que ele é implementado por uma funcão na biblioteca padrão:

[code]

#incl...

pra C eu uso stdio.h ?

kao00 · 17-04-2005, 8:52

Vê se é isso que vc queria...

Código:

#include <stdio.h>
#include <time.h>

void ordenar_vetor(int [], const int);

int main(void){
    
    int i;
    const int tamanho = 20;
    
    int v[tamanho];
    
    /* coloca alguns números no vetor */
    for(i = 0; i < tamanho; i++)
        v[i] = rand() % 100;
    
    /* mostra o vetor v desordenado */
    printf("Vetor v desordenado:\n");
    for(i = 0; i < tamanho; i++)
        printf("%d ", v[i]);
        
    /* ordena o vetor em ordem crescente */
    ordenar_vetor(v, tamanho);
    
    /* mostra o vetor v ordenado */
    printf("\n\nVetor v em ordem crescente:\n");
    for(i = 0; i < tamanho; i++)
        printf("%d ", v[i]);
        
    /* agora se quiser passar o vetor v ordenado para o vetor y, faz isso */
    int y[tamanho];
    for(i = 0; i < tamanho; i++)
        y[i] = v[i];
        
    /* mostra o vetor y */
    printf("\n\nVetor y em ordem crescente:\n");
    for(i = 0; i < tamanho; i++)
        printf("%d ", y[i]);
        
    return 0;
}

void ordenar_vetor(int v[], const int tamanho)
{
     int i, j, temp;
     
     for(i = 0; i < tamanho - 1; i++){
             
         for(j = 0; j < tamanho - 1; j++){
             if(v[j] > v[j + 1]){
                 temp = v[j];
                 v[j] = v[j + 1];
                 v[j + 1] = temp;
             }
         }
     }
}

jackinabox · 17-04-2005, 10:45

Citação:

Postado Originalmente por Gordon

...e criar um outro y[50], com os indices de v em ordem crescente?

"ordenar os índices" ou "ordenar os elementos"?

Gordon · 17-04-2005, 11:31

Citação:

Postado Originalmente por jackinabox

"ordenar os índices" ou "ordenar os elementos"?

acho q eu fui poco claro entao, sao os elementos, assim

v[5]={3,4,5,1,9}

u[5]=v ordenado > u[5]={1,3,4,5,9}

Gordon · 17-04-2005, 11:40

Citação:

Postado Originalmente por kao00

Vê se é isso que vc queria...
[code]
#include <stdio.h>
#include <time.h>

void ordenar_vetor(in...

ae cara vlw consegui resolver :lol:

pflynn · 17-04-2005, 11:43

Citação:

pra C eu uso stdio.h ?

Leia com atencão o trecho de código que escrevi lá em cima

!

jackinabox · 17-04-2005, 12:55

Citação:

Postado Originalmente por Gordon

acho q eu fui poco claro entao, sao os elementos, assim

Às vezes, os elementos de um array A são índices de um outro array B, o qual contém elementos mais complexos (structs, por exemplo). Dependendo do caso, em vez de ordenar fisicamente os elementos de B, pode ser mais eficiente ordenar apenas os índices de B (que estão contidos em A), segundo determinado critério.

Foi isso que eu pensei (erradamente) que você poderia estar querendo fazer.

jose_silva_neto · 17-04-2005, 15:20

Citação:

Postado Originalmente por kao00

Vê se é isso que vc queria...
[code]
#include <stdio.h>
#include <time.h>

void ordenar_vetor(in...

Boa tarde,

Essa função que você definiu, é um método força bruta não ? Os loops aninhados (tamanho^{2}) é para garantir que o vetor seja ordenado...hummm, se for um vetor com letras, suponhamos apenas minúsculas, a ordem "natural" é a alfabética, então fazendo algo do tipo:

a---> 1
b---> 2
...
...
z---> 26

Podemos ordenar qualquer vetor com apenas uma letra por entrada, mas e se for um vetor com strings genéricas em cada entrada ?
Me desculpe, não estou te interrogando, apenas gosto de algoritmos e acabo me empolgando...=)

Té+

Kali

jackinabox · 17-04-2005, 15:52

Citação:

Postado Originalmente por kalicrates

Essa função que você definiu, é um método força bruta não?

É um bubble sort. Não sei se utilizar o termo "força bruta" seria aplicável para algoritmos de ordenação...

Citação:

mas e se for um vetor com strings genéricas em cada entrada?

Se o objetivo for tornar a função mais genérica, você pode substituir a comparação direta (com o operador > por uma função de comparação) - que aliás, é o que faz a função qsort da stdlib, que já foi citada pelo pflynn. Dessa forma, o algoritmo de ordenação (seja qual for) irá funcionar para qualquer tipo de elemento que esteja armazenado no vetor.

Gordon · 17-04-2005, 18:35

Com as repostas de vcs acabei , tirando mais duvidas q tinha inicialmente vlw ai! :lol:

jose_silva_neto · 17-04-2005, 18:45

Citação:

Postado Originalmente por jackinabox

É um bubble sort. Não sei se utilizar o termo "força bruta" seria aplicável para algoritmos de ordenação...

...

Eu sei o que é um "brute force" (varrer todas as possibilidades - procurando uma senha por exemplo), foi apenas uma força de expressão...mas eu tenho uma pergunta:

Dado um vetor com N números, com provar que os loops aninhados (N^{2} passos) sempre devolvem um vetor ordenado (de forma crescente por exemplo) ?
Ou seja, como se demonstra matematicamente a validade da ordenação bolha ?

Té+

Kali

jackinabox · 17-04-2005, 19:28

Citação:

Postado Originalmente por kalicrates

Ou seja, como se demonstra matematicamente a validade da ordenação bolha?

Talvez lendo "The Art of Computer Programming Vol. 3 - Sorting and Searching", onde consta o teorema e a prova correspondente.

Um trechinho:

Citação:

Postado Originalmente por Donald Knuth

"A probabilidade de que exatamente k passos são necessários é de:"

Ak = (1 / n!) * (k ^ (n - k) * k! - (k - 1) ^ (n - k + 1) * (k - 1)!)

sml0180

jose_silva_neto · 18-04-2005, 6:08

Citação:

Postado Originalmente por jackinabox

Talvez lendo "The Art of Computer Programming Vol. 3 - Sorting and Searching", onde consta o teorema e a prova...

Bom dia,

Obrigado por citar tio Knuth, se ele não sabe...esqueça...;-)
Por outro lado, definindo:
f(n,k) = (k^{n-k}k!)
Então:

P_{n}(k) = \frac{1}{n!}(f(n,k) - f(n,k-1))

O n! é o número de elementos do espaço amostral, onde n é o tamanho do vetor (digamos assim), e a diferença entre as f's é o número de configurações que podem ser ordenadas com apenas k passos.
Bem...deixa quieto, preciso voltar a estudar SQL...

Obrigado pela dica...=)

Té+

Kali

jqueiroz · 18-04-2005, 18:58

kali, eu vou banir vc por excesso de complicação... :mrgreen:

Seguinte, no meu tempo de graduação (e já se vão bem uns 15 anos nessa brincadeira), estudamos variados algoritmos de ordenação.

O Bubble Sort, que foi codificado pelo kao00, é um algoritmo conhecido, acho que com algum esforço dá até pra sair uma prova matemática de que ele funciona. Mas o que importa é que ele tem complexidade O(n²), ou seja, o tempo de execução dele é proporcional ao quadrado do número de elementos do vetor.

Já o Quick Sort (também dá pra conseguir uma prova matemática dele), outro algoritmo conhecido, tem complexidade O(log2(n)), ou seja, o tempo de execução dele é proporcional ao logaritmo na base 2 do número de elementos do vetor.

Existem variações do Bubble Sort que tentam deixá-lo mais inteligente; uma delas altera o loop interno, assim:

Código:

for i := 1 to n do
   for j := 1 to n-i do
      if( v[j] > v[j+1] ) then
         swap( v[j], v[j+1] );

Esta variação admite que a cada passagem o maior elemento não ordenado vai para seu lugar correto, e portanto não é preciso mais ser ordenado. Assim, o tamanho do vetor verificado é reduzido de 1.

Outra variação tenta lembrar a última posição alterada, e assume que todos os elementos a partir daí estão ordenados. Assim, ele reduz o tamanho do vetor para terminar a comparação aí.

Código:

   k := n-1;
   for i := 1 to n do
      for j := 1 to k do
         if( v[j] > v[j+1] ) then
         begin
            swap( v[j], v[j+1] );
            k := j-1;
         end;

Esta variação se comporta melhor para os casos de vetores parcialmente ordenados.

jose_silva_neto · 19-04-2005, 12:04

Citação:

Postado Originalmente por jqueiroz

kali, eu vou banir vc por excesso de complicação... :mrgreen:

Seguinte, no meu tempo de graduação (e já se vão bem...

Muito obrigado pelas explicações

Té+

Kali

16-04-2005, 14:41	#1 (permalink)
Gordon GeeK Registrado em: Dec 2001 Localização: Campinas - SP Mensagens: 2.324 Reputação: 174	Ordenar indices de vetores (em C) , como? Ja tentei mas sempre da algum erro de logica, entao como posso pegar , por exemplo um vetor v[50] e criar um outro y[50], com os indices de v em ordem crescente? vlw

16-04-2005, 15:03	#2 (permalink)
Wormer Zumbi Registrado em: Mar 2002 Localização: Salto - SP Idade: 28 Mensagens: 6.339 Reputação: 28	Aqui tem vários exemplos de algoritmos: http://yagni.com/combsort/index.php __________________ Por favor evitem fazer perguntas técnicas por MP, o fórum existe para isso. EeePC 4G 701 + Windows Vista Ultimate

18-04-2005, 18:58	#19 (permalink)
jqueiroz Highlander Registrado em: May 2002 Localização: Tijuca/RJ Idade: 9 Mensagens: 87.724 Reputação: 778	kali, eu vou banir vc por excesso de complicação... :mrgreen: Seguinte, no meu tempo de graduação (e já se vão bem uns 15 anos nessa brincadeira), estudamos variados algoritmos de ordenação. O Bubble Sort, que foi codificado pelo kao00, é um algoritmo conhecido, acho que com algum esforço dá até pra sair uma prova matemática de que ele funciona. Mas o que importa é que ele tem complexidade O(n²), ou seja, o tempo de execução dele é proporcional ao quadrado do número de elementos do vetor. Já o Quick Sort (também dá pra conseguir uma prova matemática dele), outro algoritmo conhecido, tem complexidade O(log2(n)), ou seja, o tempo de execução dele é proporcional ao logaritmo na base 2 do número de elementos do vetor. Existem variações do Bubble Sort que tentam deixá-lo mais inteligente; uma delas altera o loop interno, assim: Código: for i := 1 to n do for j := 1 to n-i do if( v[j] > v[j+1] ) then swap( v[j], v[j+1] ); Esta variação admite que a cada passagem o maior elemento não ordenado vai para seu lugar correto, e portanto não é preciso mais ser ordenado. Assim, o tamanho do vetor verificado é reduzido de 1. Outra variação tenta lembrar a última posição alterada, e assume que todos os elementos a partir daí estão ordenados. Assim, ele reduz o tamanho do vetor para terminar a comparação aí. Código: k := n-1; for i := 1 to n do for j := 1 to k do if( v[j] > v[j+1] ) then begin swap( v[j], v[j+1] ); k := j-1; end; Esta variação se comporta melhor para os casos de vetores parcialmente ordenados. __________________ Visite Quepolis (link de indicação) \| "chmod 777 nunca ajudou ninguém" (c) 2002-2010 JQueiroz/FGdH CCNP: √ ² CCSI: □ \| Conheça o Novo Bebuns

		FórumGdH > Profissional > Programação, scripts, web e banco de dados
Ordenar indices de vetores (em C) , como?

1. Ordenar uma estrutura pela data(dia, mes, ano) (em C ) 2. Ordenar Vetor em Java (no Eclipse) 3. Ordenar sempre uma lista em Linguagem C (titl.edit)	4. Excel...ordenar por aniversário pela data de nascimento 5. ordenar Lista Encadeada - linguagem C
Mais resultados? Use nossa pesquisa.

16-04-2005, 19:51	#4 (permalink)
Gordon GeeK Registrado em: Dec 2001 Localização: Campinas - SP Mensagens: 2.324 Reputação: 174	tentei aprender o quicksort sozinho mas nao consegui implementar ele no meu prog... ele eh a melhor solucao , a mais inteligente.... mas sera q alguem ai pode me dar uma dica pra resolver isso de uma outra maneira , nem q seja bem ruim, mas q funcione? flw []´s

17-04-2005, 18:35	#15 (permalink)
Gordon GeeK Registrado em: Dec 2001 Localização: Campinas - SP Mensagens: 2.324 Reputação: 174	Com as repostas de vcs acabei , tirando mais duvidas q tinha inicialmente vlw ai! :lol:

Opções do Tópico
Exibir Versão para Impressão Envie essa página por e-mail