Next: 14 Matrizes ou Arrays Up: 1 Programação Básica em Previous: 12 O pré-processador
Considere o seguinte programa. Este programa pede ao usuário notas de 4 estudantes, calcula a média e imprime as notas e a média.
int main()
{
int nota0, nota1, nota2, nota3;
int media;
cout << "Entre a nota do estudante 0: ";
cin >> nota0;
cout << "Entre a nota do estudante 1: ";
cin >> nota1;
cout << "Entre a nota do estudante 2: ";
cin >> nota2;
cout << "Entre a nota do estudante 3: ";
cin >> nota3;
media = (nota0 + nota1 + nota2 + nota3) / 4;
cout << "Notas: " << nota0 << " " << nota1 << " " << nota2 << " "
<< nota3 << endl;
cout << "Media: " << media << endl;
}
Este programa é bem simples, mas ele tem um problema. O que acontece se o número de estudantes aumentar ? O programa ficaria muito maior (e feio !!). Imagine o mesmo programa se existissem 100 estudantes.
O que precisamos é uma abstração de dados para agrupar dados relacionados. Este é o objetivo de arrays em C++ .
Um array é uma coleção de um ou mais objetos, do mesmo tipo, armazenados em endereços adjacentes de memória. Cada objeto é chamado de elemento do array. Da mesma forma que para variáveis simples, damos um nome ao array. O tamanho do array é o seu número de elementos. Cada elemento do array é numerado, usando um inteiro chamado de índice. Em C++ , a numeração começa com 0 e aumenta de um em um. Assim, o último índice é igual ao número de elementos do array menos um.
Por exemplo, podemos definir um array nota de tamanho 100 para armazenar as notas dos cem estudantes:
int nota[100];Quando o compilador encontra esta definição, ele aloca 200 bytes consecutivos de memória (dois bytes - referente a cada int - para cada nota). Cada nota pode ser acessada dando o nome do array e o índice entre colchetes: como nota[0] (para a primeira nota), nota[1] para a segunda nota, e assim por diantes, até a última nota, nota[99].
Mas antes de prosseguirmos com as propriedades e algoritmos de vetores, vamos introduzir operadores especiais de atribuição aritmética e uma nova estrutura de repetição que é bastante adequada na manipulação de vetores.
É freqüente em programas C++ expressões do tipo:
tudo = tudo + parte;
tamanho = tamanho * 2.5;
x = x * (y + 1);
j = j - 1;
C++ fornece operadores adicionais que podem ser usados para tornar estes tipos de atribuições mais curtos.
Há um operador de atribuição para cada operação aritmética listada anteriormente:
Cada uma dessas operações podem ser usadas para tornar as expressões anteriores mais curtas:
tudo += parte;
tamanho *= 2.5;
x *= y + 1;
j -= 1;
Considere o laço while abaixo:
int i;
i = 0; /* valor inicial da variável de controle da repetição */
while (i <= 10) /* Testa variável de controle para saber se haverá
repetição ou não do corpo do "while" */
{
....
....
i += 1; /* expressão de incremento da variável de controle da
repetição */
}
Este laço pode ser expresso de forma diferente utilizando a estrutura de repetição for. A estrutura acima pode ser expressa de forma equivlente com um for da seguinte forma:
int i;
for (i = 0; i <= 10; i += 1)
{
....
....
}
Como pode-se observar, há 4 partes no laço for: inicialização, expressão de teste, expressão de incremento e o corpo do laço. O formato do laço for é:
for (inicialização ; expressão de teste ; incremento ){
corpo da repetição
}
A inicialização é executada uma única vez no início do laço. A expressão teste é então avaliada para verificar se o laço deve terminar. Caso a expressão seja verdadeira (isto é, diferente de Zero), o corpo da repetição é executado. Depois desta execução, a expressão de incremento é executada e o processo é repetido a partir da expressão teste. O corpo da repetição, por sua vez, pode ser uma sentença simples ou composta.
![\includegraphics[scale=1.0]{for}](notas-img43.png)
Veja abaixo um exemplo simples do laço for:
int contador;
for( contador = 0; contador < 5; contador += 1 )
cout << "contador = " << contador << endl;
cout << "ACABOU !!!!\n";
Saída do programa:
contador = 0
contador = 1
contador = 2
contador = 3
contador = 4
ACABOU !!!!
Se você examinar cuidadosamente este exemplo, poderá ver precisamente o que está acontecendo. Primeiro, a inicialização é executada, que é a sentença contador = 0. Isso modifica o valor da variável contador para 0. Então, o teste é executado. como 0 < 5 é verdadeiro, o laço continua. Assim, o corpo da repetição é executado, imprimindo a primeira linha da saída, contador = 0. Depois disso, o incremento é executado, que é a sentença contador++, que altera o valor da variável contador para 1.
Esta é a 1ª iteração do laço. Então, o teste é executado novamente (como 1 < 5 é verdadeiro, o laço continua), o corpo da repetição mostra contador = 1, e contador é incrementado novamente.
Este processo continua até que contador seja 4 e contador = 4 seja impresso. Depois disso, contador é incrementado para 5 e o teste é executado. Mas desta vez, 5 < 5 é falso, então o laço não continua. A execução do programa continua na sentença que segue o laço (no caso, imprimir a frase ACABOU !!!).
Após a execução do laço, a variável contador tem valor 5.
Ao invés de usar o teste contador < 5, você poderia também ter usado a expressão contador <= 4. O resultado seria o mesmo. Use a expressão que você preferir. Outra expressão que também poderia ter sido usada é contador != 5. Porém esta expressão torna o programa menos legível (não é tão evidente que o valor de contador está sendo incrementado até atingir o valor 5). Além disso, isso poderia causar problemas se mudássemos a inicialização para um valor maior que 5. Por exemplo, se a inicialização for contador = 25 e a expressão teste for contador != 5 o laço nunca terminaria, pois o contador começa com 25 e a cada iteração o valor é incrementado, o que nunca tornaria o teste falso.
Também poderíamos ao invés de usar contador += 1 como a expressão de incremento, usar ++contador, contador++ e contador = contador + 1. O resultado seria o mesmo (neste caso, o uso de pós- e pré-incremento não faz diferença).
Se você quisesse incrementos de dois, você poderia escrever contador += 2 (ou contador = contador + 2).
Em um for também podemos ter mais de uma expressão de inicialização ou incremento. Nestes caso, elas devem ser separadas por vírgula ( ,) o que é ilustrado no exemplo abaixo:
#include <iostream> using namespace std; int main( ){ int contador, total; for( contador = 0, total = 0; contador < 10; contador += 1 ){ total += contador; cout << "contador = " << contador << ", total = " << total << endl; } }
Saída:
contador = 0, total = 0
contador = 1, total = 1
contador = 2, total = 3
contador = 3, total = 6
contador = 4, total = 10
contador = 5, total = 15
contador = 6, total = 21
contador = 7, total = 28
contador = 8, total = 36
contador = 9, total = 45
No exemplo acima, contador = 0, total = 0 é a inicialização, contador < 10 é a expressão teste, e contador += 1 é a expressão de incremento.
#include <iostream> #include <iomanip> // Necessário para uso da função setw() em cout using namespace std; int main( ){ int i, soma; soma = 0; for( i = 30; i >= 5; i -= 1 ){ if( (i % 3) == 0 ){ cout << "\t" << setw(2) << i << endl; soma += i; } } cout << "\t soma = " << soma << endl; }
Saída do programa:
30
27
24
21
18
15
12
9
6
soma = 162
Embora qualquer laço possa ser escrito usando while ou for, a escolha é baseada principalmente no estilo. Por exemplo, se o laço precisa de uma inicialização e um incremento (como no caso do tratamento de vetores), então o for geralmente é usado. No caso em que o número de repetições não é pré-determinado em geral usa-se o while.
Como o comando for:
for( inicializacao; teste; incremento )
sentenca;
é equivalente a:
inicializacao;
while( teste ) {
sentenca;
incremento;
};
você pode escolher o que preferir, a princípio.
A definição de arrays é muito parecida com a definição de variáveis. A única diferença é que em array é necessário especificar seu tamanho (quantos elementos ele tem).
Os colchetes [ e ] são usados na definição do tamanho, como mostra os exemplos a seguir:
int total[5];
float tamanho[42];
O primeiro exemplo é um array de 5 inteiros (o tipo int) com o nome total. Como a numeração de arrays começa com 0, os elementos da array são numerados 0, 1, 2, 3 e 4.
O segundo exemplo é um array de 42 elementos do tipo float com índices de 0 a 41.
Cada elemento do array total é do tipo inteiro e pode ser usado do mesmo jeito que qualquer variável inteira. Para nos referirmos a um elemento do array, usamos colchetes também ([ e ]). O valor dentro dos colchetes pode ser qualquer expressão do tipo inteiro. Quando um array é definido, armazenamento suficiente (bytes contínuos na memória) são alocados para conter todos os elementos do array.
Note na tabela de precedência abaixo que [ ] tem precedência maior que todos os demais operadores.
| Operador | Associatividade |
() [] |
esquerda para direita |
! - & |
direita para esquerda |
* / % |
esquerda para direita |
+ - |
esquerda para direita |
< <= > >= |
esquerda para direita |
== != |
esquerda para direita |
&& |
esquerda para direita |
|| |
esquerda para direita |
= |
direita para esquerda |
, |
esquerda para direita |
Verifique se você entende as sentenças do programa abaixo.
int i, x, sala, total[5];
float area;
float tamanho[42];
x = total[3];
i = 4;
total[i] = total[i-1] + total[i-2];
total[4] = total[4] + 1;
tamanho[17] = 2.71828;
sala = 3;
area = tamanho[sala] * tamanho[sala];
cin >> tamanho[41];
Agora, podermos reescrever o programa que calcula a média de uma classe de 4 alunos:
int main()
{
int indice, nota[4];
float total;
indice = 0;
while (indice < 4)
{
cout << "Entre a nota do estudante " << indice << ": ";
cin >> nota[indice];
indice = indice + 1;
}
cout << "Notas: ";
total = 0;
indice = 0;
while (indice < 4)
{
cout << nota[indice] << " ";
total = total + nota[indice];
indice = indice + 1;
}
cout << endl << "Media: " << total / 4 << endl;
}
Exemplo de Saída:
Entre a nota do estudante 0: 93 Entre a nota do estudante 1: 85 Entre a nota do estudante 2: 74 Entre a nota do estudante 3: 100 Notas: 93 85 74 100 Media: 88
O código-fonte do programa é consideravelmente mais curto. Ele fica ainda mais elegante com o uso de operadores de atribuição aritmética (Seção 13.1) e da estrutura de repetição for (Seção 13.2)4:
int main()
{
int indice, nota[4];
float total;
for(indice = 0; indice < 4; indice += 1)
{
cout << "Entre a nota do estudante " << indice << ": ";
cin >> nota[indice];
}
cout << "Notas: ";
total = 0;
for(indice = 0; indice < 4; indice += 1)
{
cout << nota[indice] << " ";
total = total + nota[indice];
}
cout << endl << "Media: " << total / 4 << endl;
}
O único problema é que ainda não é fácil modificar o programa
para cem alunos porque 4 está em vários pontos do programa.
Nós podemos usar o
#define para manter o tamanho do array como uma constante
simbólica ao invés de utilizar uma constante numérica.
#define ESTUDANTES 4
int main()
{
int indice, nota[ESTUDANTES];
float total;
for(indice = 0; indice < 4; indice += 1)
{
cout << "Entre a nota do estudante " << indice << ": ";
cin >> nota[indice];
}
cout << "Notas: ";
total = 0;
for(indice = 0; indice < 4; indice += 1)
{
cout << nota[indice] << " ";
total = total + nota[indice];
}
cout << endl << "Media: " << total / ESTUDANTES << endl;
}
Os arrays podem ser inicializados quando são definidos. Se o array não for inicializado, então ele contem valores indefinidos (também conhecidos como lixo).
Para inicializar um array, um valor para cada elemento deve ser especificado. Estes valores devem estar entre chaves ({ e }) e são separados por vírgula (,). Alguns exemplos:
int valor[4] = { 1, 42, -13, 273 };
// o tamanho do array pode ser omitido
int peso[] = { 153, 135, 170 };
No primeiro exemplo, valor é um array de 4 inteiros onde valor[0] e' 1, valor[1] e' 42, valor[2] e' -13, e valor[3] e' 273.
Note que no segundo exemplo, o tamanho do array foi omitido. Neste caso, o compilador calcula o tamanho como sendo o número de elementos listados. Quando um array é definido, se ele não for inicializado, o tamanho do array deve ser especificado. Se o array for inicializado, o tamanho pode ser omitido. O segundo exemplo acima é equivalente a
int peso[3] = { 153, 135, 170 };
Se o tamanho não for omitido, o número de elementos presentes não deve exceder o tamanho. Se exceder, o compilador gerará uma mensagem de erro. Se houver menos elementos na lista de inicialização, então os elementos dados são usados para inicializar os primeiros elementos do array. Qualquer elemento não inicializado conterá lixo.
Note que este tipo de inicialização só é válido no contexto onde o array é definido. Uma sentença como a seguinte produzirá um erro do compilador, uma vez que arrays só podem ser inicializados quando definidos.
int erro[5];
erro = { 2, 4, 6, 8, 10 }; // ISTO ESTA' ERRADO
Há mais uma restrição na inicialização de um array. Os valores devem ser todos constantes - nenhuma variável ou expressão é permitida. O seguinte trecho de programa produz um erro porque um dos valores de inicialização é uma variável:
int x = 21;
int yy[3] = { 1, 2, x }; // ISTO ESTA' ERRADO
Se você executar uma atribuição a um elemento do array fora do seu limite, você estará escrevendo em um endereço de memória que pode conter algo importante, destruindo-o. Em geral, erros como estes são difíceis de encontrar, já que o programa pode até executar, só que faz algo “estranho”. Se você estiver usando o Code::Blocks , você poderá ver uma mensagem como “Esta aplicação violou a integridade do sistema devido a execução de uma instrução inválida e será cancelada.”. Não entre em pânico !! Você provavelmente terá que reinicializar o seu computador e examinar o seu programa cuidadosamente para achar acessos a array fora do seu limite. É claro que ao reinicializar o seu computador, você perderá todo o seu trabalho se não tiver salvado antes. MORAL: depois que seu programa compilar com sucesso, salve o seu programa em disco antes de executá-lo.
Por exemplo, considere o seguinte programa:
#include <iostream>
using namespace std;
#define TAM 10
int main()
{
int ops[TAM], i;
// Acesso fora dos limites quando i == TAM
for(i = 0; i <= TAM; i += 1)
{
ops[i] = 0;
}
}
Este programa inicializa cada elemento do array com 0. O problema ocorre quando i tem o valor 10. Neste ponto, o programa coloca 0 em ops[10]. Isto pode produzir resultados indefinidos (e desastrosos) embora o compilador não gere nenhum erro. O problema está na condição do while, que não deveria permitir que o corpo da repetição fosse executado quando i assumisse o valor 10.
Para passar um array como argumento (com todos os seus elementos) de uma função passamos o nome do array. Considere o exemplo abaixo:
#include <iostream> using namespace std; #define TAMANHO 5 // função array_max(a) // ação: acha o maior inteiro de um array de TAMANHO elementos // entrada: array a de inteiros // saida: o maior valor do array // suposições: a tem TAMANHO elementos // algoritmo: inicializa max com o primeiro elemento do array; em // uma repeticao compara o max com todos os elementos // do array em ordem e muda o valor de max quando um // elemento do array for maior que o max ja' encontrado. // int array_max(int a[]) { int i, max; // Achar o maior valor do array max = a[0]; i = 1; while (i < TAMANHO) { if (max < a[i]) { max = a[i]; } i = i + 1; } return max; } /* Programa principal */ int main() { int i, valor[TAMANHO]; i = 0; while (i < TAMANHO) { cout << "Entre um inteiro: "; cin >> valor[i]; i = i + 1; } cout << "O maior eh " << array_max(valor) << endl; }
Aqui está um exemplo de execução deste programa
Entre um inteiro: 73 Entre um inteiro: 85 Entre um inteiro: 42 Entre um inteiro: -103 Entre um inteiro: 15 O maior e' 85
Em main() a chamada para array
max() tem valor como seu argumento, que é copiado para o parâmetro formal
a, que é um array de inteiros. Note que o tamanho não foi
especificado, somente o nome do array, a. Porém é também
correto incluir o tamanho (isto é uma questão de estilo - escolha o
que você preferir):
int array_max(int a[TAMANHO])
{
...
}
A inclusão do tamanho de um array unidimensional na definição da função é somente por razões de legibilidade.
Até este ponto, parece que não há diferença entre passar uma variável simples e um array como argumento para uma função. Mas há uma diferença fundamental: QUANDO DEFINIMOS UM ARRAY COMO ARGUMENTO FORMAL, ALTERAÇÕES NO ARRAY FEITAS DENTRO DA FUNÇÃO ALTERAM O CONTEÚDO DO ARRAY PASSADO COMO PARÂMETRO REAL NA CHAMDA DA FUNÇÃO. EM OUTRAS PALAVRAS, QUANDO SÃO PARÂMETROS DE FUNÇÕES, ARRAYS SÃO PASSADOS POR REFERÊNCIA (sem a necessidade do & na definição do parâmetro formal, como foi visto na Seção 11).
Para ilustrar este conceito, considere o exemplo seguinte:
#include <iostream> using namespace std; // Troca o valor de uma variavel void troca( int a ){ a = 20; } // Troca valores de elementos em um vetor void troca_vet( int vet[] ){ vet[0] = 60; vet[1] = 70; vet[2] = 80; } // Programa Principal int main() { int x, y; int v[3]; x = 10; v[0] = 30; v[1] = 40; v[2] = 50; troca( x ); cout << "x=" << x << endl; troca_vet( v ); cout << "v[0]=" << v[0] << " v[1]=" << v[1] << " v[2]=" << v[2] ; }
A saída deste programa é:
x=10 v[0]=60 v[1]=70 v[2]=80
O valor da variável x do programa principal não se altera porque como já vimos nas notas de aula 7, quando a função troca é chamada, o valor do argumento real x é avaliado, que é 10, este valor é copiado para o parâmetro formal a da função troca e a função então é executada. O parâmetro a da função é tratada como variável local, portanto quando atribuímos 20 a a, estamos atribuindo 20 a uma variável local. Terminada a função, a execução retorna ao programa principal, que imprime o valor de x, que não foi alterado, ou seja, imprime x=10.
Quando a função troca_vet é chamada, o array v é passado como argumento e “copiado” para o parâmetro formal vet. A função é então executada, e os elementos do array são alterados para 60, 70, 80. Como mencionado anteriormente, quando passamos um array como parâmetro, as alterações feitas no array dentro da função alteram o array passado como parâmetro. Portanto, quando a função termina e a execução continua no programa principal com a impressão dos valores dos elementos de v, será impresso 60, 70, 80, os novos valores alterados de dentro da função troca_vet.
Vamos entender por que quando passamos só o nome do array como argumento as alterações afetam o array passado como parâmetro real. Como já mencionamos anteriormente, quando um array é definido, como v no programa principal acima, é alocado espaço suficiente na memória para conter todos os elementos do array. Na ilustração abaixo, são alocados 6 bytes de memória a partir do endereço 1342 para conter o array. O array como um todo não tem um valor, mas cada elemento do array tem (neste caso, foram inicializados com 30, 40, 50). O nome do array, na verdade, contém o endereço onde começa o array, neste caso, o endereço 1342.
Portanto, quando passamos o nome do array como argumento para uma função estamos na realidade passando como argumento o endereço de memória onde começa o array. No exemplo anterior, 1342 é passado como argumento para o parâmetro formal vet da função troca_vet. Portanto, da mesma forma que no caso da variável simples, o valor de v, que é o endereço 1342, é copiado para o parâmetro vet de troca_vet. Então, quando a função troca_vet é executada, vet é um array de elementos do tipo int que começa no endereço 1342. Quando atribuímos o valor 60 a vet[0], estamos atribuindo 60 ao primeiro elemento do array que começa no endereço 1342. Como este é o mesmo endereço onde começa o array v do programa principal, quando a função troca_vet termina, o array v “enxergará” o valor dos elementos do array que começa no endereço 1342, que foram alterados pela função.
![\includegraphics[scale=0.5]{ptrarr}](notas-img44.png)
Quando passamos variáveis simples como argumento para uma função estamos passando somente o valor da variável, portanto, de dentro da função não é possível saber qual o endereço da variável para poder alterá-la.
Lembre-se que o endereço só é passado para a função quando passamos o array COMO UM TODO (ou seja, o nome do array, sem ser indexado por um elemento). Se passarmos como argumento apenas um elemento do array, o comportamento é o mesmo que se passássemos uma variável simples. Ou seja, o nome do array indexado por um valor entre colchetes refere-se ao valor do elemento do array, enquanto o nome do array sozinho refere-se ao endereço onde começa o array. Assim, no programa abaixo:
#include <iostream> using namespace std; // Troca o valor de uma variavel void troca( int a ){ a = 20; } // Troca valores de elementos em um vetor void troca_v( int vet[] ){ vet[0] = 60; vet[1] = 70; vet[2] = 80; } // Programa Principal int main(){ int v[] = {30, 40, 50}; troca( v[0] ); cout << "v[0]=" << v[0] << endl; troca_v( v ); cout << "v[0]=" << v[0] << " v[1]=" << v[1] << " v[2]=" << v[2] ; }
A saída do programa é:
v[0]=30 v[0]=60 v[1]=70 v[2]=80
Outro exemplo: a função inicializaArray abaixo inicializa todos os elementos do array valor com um valor passado como argumento pelo programa principal.
#include <iostream> using namespace std; #define TAMANHO 30 // função inicializaArray(a, k) // ação: inicializa todos os elementos de a com k // entrada: array de inteiros a, inteiro k // saida: nenhum // suposições: a tem TAMANHO elementos // algoritmo: uma repeticao for, inicializando um elemento a // cada repeticao // void inicializaArray(int a[], int k) { int i; i = 0; while (i < TAMANHO) { a[i] = k; i = i + 1; } } // Programa principal int main() { int valor[TAMANHO]; // Inicializa todos os elementos do array com 42 inicializaArray(valor, 42); // O resto do programa principal // . // . // . }
Como as alterações feitas por inicializaArray são vistas do programa principal, depois da função inicializaArray ser executada, no programa principal todos os elementos do array valor terão o valor 42.
Pesquisar (procurar) em um array um determinado valor (chamado de chave) é um problema muito comum em programação. Ele tem diversas aplicações. Por exemplo, podemos pesquisar um array de notas para verificar se algum aluno tirou 100 na prova. Há diversos algoritmos de pesquisa: cada um com suas vantagens e desvantagens. Nestas notas de aula, discutiremos um algoritmo simples, chamado de pesquisa linear. A pesquisa é feita usando uma repetição e examinando cada elemento do array a cada repetição e comparando o elemento com a chave que buscamos. A pesquisa termina quando um elemento do array que “casa” com a chave é encontrada, ou quando o array todo é percorrido e a chave procurada não é encontrada.
linear que tem como argumento
de entrada: um array de inteiros a ser pesquisado, o tamanho do array,
e uma chave (um valor inteiro) a ser procurado. A função retorna
um inteiro: o índice do elemento do array (se a chave for achada) ou
-1 caso contrário.
int pesquisa_linear(int [], int, int);
/* Procura uma chave em um array
* entrada: array a ser pesquisado (arr ), tamanho do array (tam),
* chave a ser procurada (chave)
* saida: o indice do elemento que e' igual a chave ou -1 caso nao ache
* suposicao: nao assume que o array esteja ordenado
*/
int pesquisa_linear(int arr[], int tam, int chave)
{
int i;
for (i = tamanho - 1; i >= 0; i += 1)
{
if (arr[i] == chave)
{
return i;
}
}
return -1;
}
void soma_array( float [], float [], float [], int );
array():
void soma_array( float arr1[], float arr2[], float arr3[], int tam )
{
int i;
for(i = 0; i < tam; i += 1)
{
arr3[i] = arr1[i] + arr2[i];
}
}
Um outro programa muito popular com arrays é ordená-lo de acordo com algum critério. Por exemplo, um array de inteiros pode ser ordenado em ordem crescente ou decrescente. O apresentado a seguir é um algorítmo básico e nem um pouco eficiente, denominado Select sort.
Ele usa o fato simples de comparar cada elemento de um array com o restante deste. Quando se acha o menor, ocorre uma troca de valores entre o elemento sob análise e o outro elemento do array que é o menor.
Por exemplo, se começarmos com um array: 9 5 2 7 3 8 1 4 6, (o primeiro elemento é 9 e o último elemento é 6) isto é o que acontece com os elementos do array depois de cada passagem sobre ele (e consequente troca de valores):
passagem conteudo do array depois da passagem ~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 0 --> 9 5 2 7 3 8 1 4 6 1 --> 1 5 2 7 3 8 9 4 6 2 --> 1 2 5 7 3 8 9 4 6 3 --> 1 2 3 7 5 8 9 4 6 4 --> 1 2 3 4 5 8 9 7 6 5 --> 1 2 3 4 5 8 9 7 6 6 --> 1 2 3 4 5 6 9 7 8 7 --> 1 2 3 4 5 6 7 9 8 8 --> 1 2 3 4 5 6 7 8 9
Note que mesmo que se começássemos com um array ordenado de 9 elementos, ainda assim o algoritmo dado faz 8 passagens sobre o array.
void selectSort(int [], int);
#include <iostream> using namespace std; #define TAM 9 void imprimePassos (int v[], int tam, int passo) { int i; cout << "Passo " << passo << ": --> "; for(i = 0; i < tam; i += 1) { cout << v[i] << " "; } cout << endl; } /* Uma funcao que encontra o menor valor em um array entre os indices * "a" e "b" (inclusive) */ int menor_indice(int v[], int a, int b) { int i; int menor; menor = a; for (i = a+1; i <= b; i += 1) { if ( v[i] < v[menor] ) { menor = i; } } return menor; } /* Uma funcao que troca os valores entre dois elementos de um array */ void troca_v( int vet[], int i, int j) { int aux; aux = vet[i]; vet[i] = vet[j]; vet[j] = aux; } /* Uma funcao que ordena um array de inteiros usando o algoritmo de * Select sort. * Entrada: array a ser ordenado -- lista[] * tamanho do array -- tam */ void selectSort(int lista[], int tam) { int i,j, idx_menor_elem; /* indice do menor valor no array entre i e tam-1 */ for(i = 0; i < tam; i += 1) { imprimePassos( lista, tam, i ); idx_menor_elem = menor_indice ( lista, i, tam-1 ); troca_v ( lista, i, idx_menor_elem ); } } int main () { int vetor[TAM], i; for(i=0; i < TAM; i += 1) { cin >> vetor[i]; } selectSort(vetor, TAM); }
O algoritmo abaixo é ligeiramente melhor que o anterior e é chamado Bubble sort. Ele é bastante simples, porém ainda não muito eficiente.
Basicamente, o algoritmo funciona da seguinte forma:
Por exemplo, se começarmos com um array: 9 5 2 7 3 8 1 4 6, (o primeiro elemento é 9 e o último elemento é 1) isto é o que acontece com os elementos do array depois de cada passagem sobre ele (e troca de valores adjacentes):
passagem conteudo do array depois da passagem ~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 0 --> 9 5 2 7 3 8 1 4 6 1 --> 1 9 5 2 7 3 8 4 6 2 --> 1 2 9 5 3 7 4 8 6 3 --> 1 2 3 9 5 4 7 6 8 4 --> 1 2 3 4 9 5 6 7 8 5 --> 1 2 3 4 5 9 6 7 8 6 --> 1 2 3 4 5 6 9 7 8 7 --> 1 2 3 4 5 6 7 9 8 8 --> 1 2 3 4 5 6 7 8 9
Note que, também aqui, mesmo que se começássemos com um array ordenado de 9 elementos, ainda assim o algoritmo dado faz 8 passagens sobre o array.
Isto pode ser melhorado da seguinte forma: Antes de começar cada passagem, inicializamos uma variável ordenado com 1. Se durante a passagem uma troca de valores ocorrer, trocamos o valor da variável para 0. Assim, se depois da passagem, o valor da variável continuar sendo 1, isso significa que nenhuma troca ocorreu e que o array está ordenado.
void bubbleSort(int [], int);
#include <iostream> using namespace std; #define TAM 9 void imprimePassos (int v[], int tam, int passo) { int i; cout << "Passo " << passo << ": --> "; for(i = 0; i < tam; i += 1) { cout << v[i] << " "; } cout << endl; } /* Uma funcao que troca os valores entre dois elementos de um array */ void troca_v( int vet[], int i, int j) { int aux; aux = vet[i]; vet[i] = vet[j]; vet[j] = aux; } /* Uma funcao que ordena um array de inteiros usando o algoritmo de * Bubble sort. * Entrada: array a ser ordenado -- lista[] * tamanho do array -- tam */ void bubbleSort(int lista[], int tam) { int ordenado, /* se 1 depois da passagem o array esta' ordenado */ elem_final = 1, /* em uma passagem, elementos do ultimo ate' elem_final sao comparados com o elemento anterior */ i,j, temp; /* enquanto o array nao estiver ordenado, fazer uma passagem sobre ele */ ordenado = 0; while (ordenado == 0) { ordenado = 1; /* assume que array esta' ordenado */ /* Examina o array do ultimo elemento ate elem_final. Compara cada elemento com o anteior e troca seus valores se estiver fora de ordem. */ imprimePassos(lista, tam, elem_final - 1); for(i = tam - 1; i >= elem_final; i -= 1) { if (lista[i] < lista[i - 1]) /* troca os elementos de i e i-1 */ { troca_v (lista, i, i - 1); ordenado = 0; /* marca como nao ordenado */ } } elem_final = elem_final + 1; } } int main () { int vetor[TAM], i; for(i=0; i < TAM; i += 1) { cin >> vetor[i]; } bubbleSort(vetor, TAM); }
Neste curso, um dos únicos lugares que veremos o nome do array sem estar indexado é quando passamos o array (como um todo) para uma função. Para outras finalidades, veremos sempre o array indexado. Por exemplo, o seguinte trecho de programa está errado:
int main(){
int arr1[4] = {10, 20, 30, 40};
int arr2[4];
arr2 = arr1; // ERRADO: NÃO copia arr1 em arr2
// tem que copiar elemento por elemento
if( arr1 == arr2 ) // ERRADO: NÃO podemos comparar arrays inteiros
cout << "X"; // tem que comparar elemento por elemento
}
