n > 0 números inteiros,
faça uma função para ordenar os seus elementos em ordem crescente.
Solução 1:
Utilizaremos a seguinte função auxiliar
para realizar a troca entre os elementos do vetor,
nos índices a e b:
void troca(int V[], int a, int b){
int tmp;
tmp = V[a];
V[a] = V[b];
V[b] = tmp;
}
A primeira solução apresentada utiliza a função
auxiliar abaixo que devolve o índice do maior elemento do
vetor com n elementos.
int indice_maior(int V[], int n){
int i,imax;
imax = 0;
for(i = 1; i < n; i++){
if(V[i] > V[imax])
imax = i;
}
return imax;
}
No algoritmo abaixo, a cada passo o maior elemento do vetor de n elementos
é encontrado, e colocado na sua posição final definitiva
de índice n-1 no final do vetor.
O processo se repete para o trecho do vetor remanescente,
composto pelos primeiros n-1 elementos ainda não ordenados
(do índice zero até n-2),
e assim por diante para subtrechos cada vez menores, até ter todo o vetor ordenado.
Este algoritmo é conhecido como algoritmo de ordenação
por seleção simples.
/*Ordenação por seleção:
A cada passo o maior elemento
do vetor é encontrado, e colocado na sua
posição final definitiva. O processo se
repete para o vetor remanescente. */
void ordenacao_selecao(int V[], int n){
int tam,imax;
for(tam = n; tam > 1; tam--){
imax = indice_maior(V, tam);
troca(V, imax, tam-1);
}
}
No código acima, o laço controla em tam
o tamanho da porção
do vetor a ser ordenada (elementos de
V[0] até V[tam-1]).
A chamada da função indice_maior
busca e armazena em imax o índice do maior elemento
presente no subtrecho do vetor a ser ordenado.
O elemento V[imax] é então
movido para a última posição
do subtrecho (V[tam-1]),
ocupando assim a sua posição definitiva.
Inicialmente, o subtrecho a ser ordenado
corresponde a todo o vetor (elementos de
V[0] até V[n-1]).
A medida que os maiores valores são movidos
para o final do vetor, temos a correspondente redução
do subtrecho remanescente a ser ordenado.
Solução 2:
O próximo algoritmo é conhecido como
bubble sort.
O laço mais interno percorre o vetor
em j
comparando elementos consecutivos do vetor (V[j] e
V[j+1]) e trocando a sua ordem sempre que
eles estiverem fora de ordem, isto é V[j] > V[j+1].
Após a primeira varredura, o maior elemento do vetor
vai ocupar a última posição do vetor,
ou seja sua posição final definitiva no vetor ordenado.
A medida que os maiores valores são movidos
para o final do vetor, temos a correspondente redução
do subtrecho remanescente a ser ordenado, até que
todo o vetor esteja ordenado.
void ordenacao_bolha(int V[], int n){
int i,j;
for(i = n-1; i > 0; i--){
for(j = 0; j < i; j++){
if(V[j] > V[j+1])
troca(V, j, j+1);
}
}
}
Uma segunda versão do algoritmo bubble sort
é apresentada abaixo.
Essa variante possui um segundo critério de parada
do laço. Sempre que o vetor é percorrido
no laço mais interno, sem que haja trocas de elementos,
podemos concluir que o vetor já se encontra ordenado
e podemos interromper o processo.
void ordenacao_bolha2(int V[], int n){
int i,j,houvetroca;
for(i = n-1; i > 0; i--){
houvetroca = 0;
for(j = 0; j < i; j++){
if(V[j] > V[j+1]){
troca(V, j, j+1);
houvetroca = 1;
}
}
if(!houvetroca)
break;
}
}
Solução 3:
Ordenação por inserção: Assume que uma parte da sequência já está ordenada, e insere mais um elemento no lugar apropriado.
void ordenacao_insercao(int V[], int n){
int i,j,x;
for(i = 0; i < n-1; i++){
/* Insere v[i+1] em v[0..i]. */
x = V[i+1];
j = i;
while(j >= 0 && V[j] > x){
V[j+1] = V[j];
j--;
}
V[j+1] = x;
}
}
n > 0 valores inteiros, em um vetor
int V[TAM],
e um inteiro x, testa se
x pertence ao vetor.
Solução 1:
Solução por busca exaustiva percorrendo o vetor.
int pertence(int x, int V[], int n){
int i = 0;
while(i < n){
if(V[i] == x)
return 1;
i++;
}
return 0;
}
Solução 2:
Essa solução aproveita o fato de que o vetor tem,
na verdade, TAM > n posições disponíveis,
e atribui na posição seguinte a do último elemento
o valor de x, conseguindo com isso a
simplificação do laço que passa agora a realizar
uma única comparação para cada iteração.
Essa técnica de busca é
conhecida como busca com sentinela.
/* busca com sentinela */
int pertence2(int x, int V[], int n){
int i = 0;
V[n] = x;
while(V[i] != x){
i++;
}
if(i == n)
return 0;
else
return 1;
}
Solução 3:
Essa terceira solução se aplica somente a vetores previamente ordenados. A cada iteração, o valor procurado é comparado com o elemento na posição central do vetor, eliminando metade do intervalo de busca.
/* Busca binária: */
int pertence3(int x, int V[], int n){
int inic, fim, meio;
inic = 0;
fim = n-1;
while(inic <= fim){
meio = (inic+fim)/2;
if(x == V[meio])
return 1;
else if(x > V[meio])
inic = meio+1;
else
fim = meio-1;
}
return 0;
}
Exemplo de função principal que chama as
funções anteriores.
#include <stdio.h>
#define TAM 100
int main(){
int V[TAM] = {6,3,9,2,7,1,0,4,8,5};
int i, x, n = 10;
ordenacao_insercao(V, n);
for(i = 0; i < n; i++){
printf("%d ", V[i]);
}
printf("\n");
printf("Digite x: ");
scanf("%d", &x);
if(pertence(x, V, n))
printf("%d pertence\n", x);
else
printf("%d não pertence\n", x);
return 0;
}