Memória, algoritmos e medir tempo.

[Paulo Lara]

Olá pessoal,

Sou novo em C++, e posso contribuir pouco por enquanto. Sei que com o tempo serei mais capaz, mas por hora me reduzo a pedir ajuda em meus trabahos iniciais. O trabalho é o seguinte:

1) Gere um vetor v com n inteiros. Use n=1000 e 10 mil. Guarde em memória (variável).

2) Usando os dados do exercício anterior, escreva uma função que verifique se o vetor v[0..n-­‐1] está em ordem crescente.

3) Pesquise os seguintes algoritmos Heap Sort, Quick Sort e Merge Sort. Implemente-­‐os ou use implementações que encontrar (emC/C++) e aplique nos dados do item(1).

4) Aplique os algoritmos novamente nos dados já ordenados. Crie uma função para medir o tempo gasto nos 6 casos.

5) Implemente uma função que busque um determinado valor no vetor. Meça o tempo gasto para este processo, nos dados ordenados e não ordenados.

Não quero os códigos, quero dicas rápidas e importantes. O que realmente preciso está em negrito. Qualquer dica é valiosíssima.

Obrigado desde já.

Editado Agosto 21, 2012 por Paulo Lara

[Marcelo Utikawa da Fonseca]

Olá!

Como a dúvida é basicamente com os algoritmos de ordenamento, eu desenvolveria todo o restante do programa.

Criaria os vetores, o loop para carregamento deles com valores aleatórios e exibiria o menu com opções de ordenar os dados por determinado algoritmo.

Quanto aos pontos em negrito:

A) Para armazenar em memória, eu imagino que ele queira dizer para manter uma cópia do vetor original para realizar as novas operações. Assim você precisa criar dois vetores iguais, carregar um e então fazer uma cópia dos dados para o segundo vetor. Utilize memcpy.

B) Pesquise sobre os algortimos no google, por exemplo. Veja o que eu achei para o Heap Sort (com código!): http://pt.wikipedia.org/wiki/Heapsort. Com certeza você vai encontrar para os outros também.

C) Para o item 4, chame os algoritmos passando como argumento o vetor original. Para medir o tempo, utilize a função time.

D) Para o item 5, basta um loop até o final do vetor ou ao encontrar o dado procurado. Novamente, utilize a função time

Tente desenvolver o programa seguindo as orientações e envie as dúvidas que forem surgindo! :-)

Abraços,

Marcelo Utikawa da Fonseca

[Paulo Lara]

Resolvido! Muito obrigado pelas dicas, o wiki ajudou bastante.