| <<< Voltar | Avançar >>> |
|
|
Se esta página lhe ajudar, considere fazer uma doação |
12. Matrizes
12.1 Introdução as matrizes
Uma matriz é uma estrutura de dados que pode armazenar vários valores do mesmo tipo.
A sintaxe para declarar uma matriz é:
TIPO NOME[QUANTIDADE]; |
onde TIPO é o tipo dos dados que serão armazenados na matriz. Todos os dados colocados na matriz devem ser deste tipo. NOME é o nome a ser dado a matriz. Este nome identificará a matriz no código do programa. E QUANTIDADE é a quantidade máxima de itens a ser armazenados. Exemplos:
/* esta matriz pode armazenar até 50 valores do tipo int */ int nr_de_livros[50]; /* esta matriz pode armazenar até 30 valores do tipo float */ float nota[30]; |
Os valores armazenados na matriz são chamados de "elementos da matriz". O primeiro elemento da matriz é indexado como item zero e o último é indexado como QUANTIDADE menos 1. Assim, para nossa matriz nota, mostrada no exemplo acima, o primeiro elemento é nota[0] e o último elemento é nota[29].
Você pode inicializar os elementos de uma matriz na sua declaração usando a sintaxe:
int notas[5] = {60,70,35,50,68};
|
No exemplo acima o elemento zero da matriz notas receberá o valor 60, o elemento 1 receberá o valor 70, e assim por diante. Para melhorar o entendimento observe o código abaixo:
#include <stdio.h>
int main()
{
int notas[5] = {60,70,35,50,68};
printf("Analisando os elementos da matriz notas\n");
printf("O primeiro elemento tem o valor %d\n",notas[0]);
printf("O segundo elemento tem o valor %d\n",notas[1]);
printf("O terceiro elemento tem o valor %d\n",notas[2]);
printf("O quarto elemento tem o valor %d\n",notas[3]);
printf("O quinto e último elemento tem o valor %d\n",notas[4]);
return(0);
}
|
Este código pode ser otimizado usando um laço for e uma variável para manipular os elementos da matriz. Observe abaixo;
#include <stdio.h>
int main()
{
int notas[5] = {60,70,35,50,68};
int contador;
printf("Analisando os elementos da matriz notas\n");
for(contador = 0;contador < 5;contador++)
printf("O %do elemento tem o valor %d\n",contador+1,notas[contador]);
return(0);
}
|
Uma das matrizes mais comuns utilizadas em C é a matriz de caracteres. As strings manipuladas em C são matrizes de caracteres. Observe o exemplo abaixo para um melhor entendimento:
/* visualizando strings como matrizes de caracteres */
#include <stdio.h>
int main()
{
char palavra[7] = "matriz";
int contador;
printf("Em C strings são matrizes de caracteres e
podem ser manipuladas como tal.\n");
printf("\nA string é %s\n",palavra);
printf("\nExibindo cada elemento da matriz palavra\n");
for(contador = 0;contador < 7;contador++)
printf("%c\n",palavra[contador]);
return(0);
|
12.2 Passando uma matriz para uma função
Uma função que manipula uma matriz deve receber a matriz e a quantidade de elementos. Logicamente ao chamar a função você deve passar a matriz propriamente dita e seu número de elementos. Não há necessidade de passar o tamanho da matriz. Exemplo:
#include <stdio.h>
void exibe(int matriz[],int elementos)
{
int contador;
for(contador = 0;contador < elementos;contador++)
printf("O %do elemento tem o valor %d\n",
contador+1,matriz[contador]);
}
int main()
{
int notas[5] = {60,70,35,50,68};
int contador;
printf("Analisando os elementos da matriz notas\n");
exibe(notas,5);
return(0);
}
|
Observe os colchetes após a variável matriz na declaração da função exibe. Isto indica que a variável é uma matriz.
12.3 Matrizes bidimensionais
Imagine uma matriz bidimensional como uma tabela de linhas e colunas. Por exemplo, a matriz
pesos[3][5] |
pode ser imaginada como:
Observe que o primeiro índice ([3]) indica as linhas da matriz e o segundo ([5]) indica as colunas.
Como sabemos que [3] varia de zero a 2 e [5] varia de zero a 4, fica fácil determinar os índices de cada posição da matriz:
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 |
Visto a posição de cada índice vamos preencher nossa matriz pesos com valores
| 10 | 30 | 45 | 70 | 36 |
| 86 | 44 | 63 | 82 | 80 |
| 70 | 61 | 52 | 63 | 74 |
De tudo que foi exposto acima podemos entender que:
pesos[1][3] = 82 pesos[0][4] = 36 pesos[0][0] = 10 pesos[2][4] = 74 |
Para preencher nossa matriz com os valores mostrados na tabela acima podemos usar uma declaração como:
int pesos[3][5] = {{10,30,45,70,36},
{86,44,63,82,80},
{70,61,52,63,74}};
|
Podemos manipular os elementos de nossa matriz bidimensional usando duas variáveis e um laço for da mesma maneira que fizemos com as matrizes comuns. Observe o código abaixo:
/* manipulando uma matriz bidimensional */
#include <stdio.h>
int main()
{
int pesos[3][5] = {{10,30,45,70,36},
{86,44,63,82,80},
{70,61,52,63,74}};
int linha,coluna;
for(linha = 0;linha < 3;linha++)
for(coluna = 0;coluna < 5; coluna++)
printf("elemento[%d][%d] = %d\n",
linha,coluna,pesos[linha][coluna]);
return(0);
}
|
12.4 Passando uma matriz bidimensional para uma função
Uma função que manipula uma matriz bidimensional deve receber a matriz e o número de linhas desta matriz. O número de colunas da matriz também deve estar especificado nesta declaração. Ao chamar a função, deve-se passar a matriz e o número de linhas. Exemplo:
/* manipulando uma matriz bidimensional */
#include <stdio.h>
void exibe(int matriz[][5], int linhas)
{
int linha,coluna;
for(linha = 0;linha < 3;linha++)
for(coluna = 0;coluna < 5; coluna++)
printf("elemento[%d][%d] = %d\n",
linha,coluna,matriz[linha][coluna]);
}
int main()
{
int pesos[3][5] = {{10,30,45,70,36},
{86,44,63,82,80},
{70,61,52,63,74}};
exibe(pesos,3);
return(0);
}
|
12.5 Pesquisa sequencial
Para procurar um valor específico numa matriz você pode usar a pesquisa sequencial. A pesquisa sequencial inicia no primeiro elemento da matriz e vai até o último procurando o valor desejado. Observe abaixo o código de uma pesquisa sequencial numa matriz:
/* exemplo de uma pesquisa sequencial numa matriz */
#include <stdio.h>
int main()
{
int pesos[5]={65,77,84,80,69};
int ok=0,contador,valor;
printf("\nmatriz pesos\n\n");
for(contador = 0;contador < 5;contador++)
printf("pesos[%d] = %d\n",contador,pesos[contador]);
printf("\nEntre com o valor a ser pesquisado :");
scanf("%d",&valor);
/* realizando a pesquisa sequencial */
contador=0;
while((contador < 5) && (!ok))
if(pesos[contador] == valor)
ok = 1;
else
contador++;
if(contador < 5)
printf("O valor %d está no elemento pesos[%d]\n",valor,contador);
else
printf("A matriz pesos não possui o valor %d\n",valor);
return(0);
}
|
Este tipo de pesquisa pode ser demorado quando a matriz possui muitos elementos. Nestes casos use a pesquisa binária que será vista mais a frente.
12.6 Ordenando os elementos de uma matriz pelo método da bolha
Este método, apesar de simples, consome mais tempo do processador, então só deve ser usado para matrizes com poucos elementos (em torno de 30). Neste método os elementos da matriz vão sendo percorridos e os pares adjacentes são comparados e ordenados. Isto é feito até que toda a matriz esteja ordenada.
Para explicar melhor vamos a um exemplo prático. Imagine a seguinte matriz:
nota[0] = 67 nota[1] = 55 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Ordenando esta matriz em ordem crescente pelo método da bolha, nosso programa iniciaria compararando o elemento nota[0], que é 67, com o elemento nota[1], que é 55. Como nota[0] é maior que nota[1] os elementos seriam trocados. e nossa matriz ficaria assim:
nota[0] = 55 nota[1] = 67 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Agora nosso programa compararia nota[1] com nota[2] e como os valores estão ordenados não haveria troca.
Continuando, compararia nota[2] com nota[3] e haveria troca ficando nossa matriz assim:
nota[0] = 55 nota[1] = 67 nota[2] = 79 nota[3] = 86 nota[4] = 68 |
Agora compararia nota[3] com nota[4] e novamente haveria troca:
nota[0] = 55 nota[1] = 67 nota[2] = 79 nota[3] = 68 nota[4] = 86 |
Agora, nosso programa iniciaria novo ciclo de comparações comparando novamente nota[0] com nota[1], nota[1] com nota[2], etc .... até que todos os elementos da matriz estivessem na ordem crescente.
Abaixo segue um exercício que ordena uma matriz de cinco valores inteiros, em ordem crescente, pelo método da bolha:
/* ordenando uma matriz pelo método da bolha *
*
* neste método a matriz é percorrida e os pares
* adjacentes são comparados e ordenados. Isto é
* feito até que toda a matriz esteja ordenada */
#include <stdio.h>
int main()
{
int vetor[5],contador,ordenados,auxiliar;
printf("Ordenando uma matriz utilizando o método da bolha.\n");
/* entrada de dados */
for(contador=0;contador < 5; contador++)
{
printf("Entre com o %do valor :",(contador+1));
scanf("%d",&vetor[contador]);
}
/* ordenação */
/* indica que os elementos adjacentes não estão ordenados */
ordenados = 0;
while(ordenados == 0)
{
/* considera todos os elementos ordenados corretamente */
ordenados = 1;
for(contador=0;contador < 4;contador++)
{
/* se os elementos adjacentes não estiverem
ordenados executa a troca */
if(vetor[contador] > vetor[(contador + 1)])
{
auxiliar = vetor[contador];
vetor[contador] = vetor[(contador + 1)];
vetor[(contador + 1)] = auxiliar;
/* força outra passagem no laço while */
ordenados = 0;
}
}
}
/* imprimindo os valores ordenados */
printf("\n");
for(contador=0;contador < 5;contador++)
printf("%d ",vetor[contador]);
printf("\n");
return(0);
}
|
12.7 Ordenando os elementos de uma matriz pelo método da seleção
Este método também só deve ser usado com matrizes pequenas. Neste método o programa procura o menor valor entre todos os elementos da matriz e troca-o pelo primeiro elemento; depois procura o menor entre o segundo e o último elemento da matriz e troca-o pelo segundo elemento; depois procura o menor valor entre o terceiro e o último elemento da matriz e troca-o pelo terceiro, e assim por diante.
Vamos ver um exemplo prático. Dada a matriz:
nota[0] = 67 nota[1] = 55 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Vamos ordená-la em ordem crescente pelo método da seleção:
Primeiro nosso programa teria que determinar o menor valor da matriz, que é 55 e trocá-lo pelo primeiro elemento da matriz (nota [0]). Nossa matriz ficaria assim:
nota[0] = 55 nota[1] = 67 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Agora seria determinado o menor valor entre o segundo (nota [1]) e o último elemento (nota [4]), que é 67, e este seria trocado com o segundo elemento (nota [1]), ficando a matriz da seguinte maneira:
nota[0] = 55 nota[1] = 67 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Agora seria determinado o menor valor entre o terceiro (nota [2]) e o último elemento (nota [4]), que é 68, e este seria trocado com o terceiro elemento (nota [2]). Agora a matriz está assim:
nota[0] = 55 nota[1] = 67 nota[2] = 68 nota[3] = 79 nota[4] = 86 |
Agora seria determinado o menor valor entre nota [3] e nota [4](no caso 79) e este valor trocado com o quarto elemento da matriz. E nossa matriz estaria ordenada:
nota[0] = 55 nota[1] = 67 nota[2] = 68 nota[3] = 79 nota[4] = 86 |
Abaixo segue um exercício que ordena uma matriz de cinco valores inteiros, em ordem crescente, pelo método da seleção:
/* ordenando uma matriz pelo método da seleção *
*
* neste método a ordenação é feita da seguinte maneira:
* - identifica-se o menor valor da matriz
* - troca-se este com o primeiro elemento
* - identifica-se o menor valor entre o segundo e o último elemento
* - troca-se este com o segundo elemento
* - identifica-se o menor valor entre o terceiro e o último elemento
* - troca-se este com o terceiro elemento
* - identifica-se o menor valor entre o quarto e o último elemento
* - troca-se este com o quarto elemento
*
* e assim por diante, até que toda a matriz esteja ordenada */
#include <stdio.h>
int main()
{
int vetor[5],contador1,contador2,indice_do_menor, menor;
printf("Ordenando uma matriz utilizando o método da seleção.\n");
/* entrada de dados */
for(contador1 = 0;contador1 < 5; contador1++)
{
printf("Entre com o %do valor :",(contador1+1));
scanf("%d",&vetor[contador1]);
}
/* ordenação */
for(contador1 = 0;contador1 < 4;contador1++)
{
indice_do_menor = contador1;
menor = vetor[contador1];
/* verificando qual o menor */
for(contador2=(contador1 + 1);contador2 < 5;contador2++)
if(vetor[contador2] < menor)
{
indice_do_menor = contador2;
/* executando a troca de valores */
menor = vetor[indice_do_menor];
vetor[indice_do_menor] = vetor[contador1];
vetor[contador1] = menor;
}
}
/* imprimindo os valores ordenados */
printf("\n");
for(contador1 = 0;contador1 < 5;contador1++)
printf("%d ",vetor[contador1]);
printf("\n");
return(0);
}
|
12.8 Ordenando os elementos de uma matriz pelo método da inserção
Neste método, também usado com matrizes pequenas, o programa inicialmente ordena os dois primeiros elementos da matriz. Depois insere o terceiro elemento na posição ordenada em relação aos dois primeiros. Depois insere o quarto elemento em sua posição ordenada em relação aos três já posicionados, e assim por diante até que toda a matriz esteja ordenada.
Vamos a um exemplo prático. Dada nossa matriz:
nota[0] = 67 nota[1] = 55 nota[2] = 86 nota[3] = 79 nota[4] = 68 |
Vamos ordená-la em ordem crescente pelo método da inserção:
Primeiro nosso programa ordenaria os dois primeiros elementos da matriz:
nota[0] = 55 nota[1] = 67 |
Depois o programa pegaria o terceiro elemento da matriz e o introduziria na posição ordenada em relação aos dois primeiros:
nota[0] = 55 nota[1] = 67 nota[2] = 86 |
Depois o programa pegaria o quarto elemento da matriz e o introduziria na posição ordenada em relação aos três primeiros:
nota[0] = 55 nota[1] = 67 nota[2] = 79 nota[3] = 86 |
Depois o programa pegaria o quinto elemento da matriz e o introduziria na posição ordenada em relação aos quatro primeiros:
nota[0] = 55 nota[1] = 67 nota[2] = 68 nota[3] = 79 nota[4] = 86 |
E nossa matriz estaria ordenada.
Abaixo segue um exercício que ordena uma matriz de cinco valores inteiros, em ordem crescente, pelo método da inserção:
/* ordenando uma matriz pelo método da inserção *
*
* neste método a ordenação é feita da seguinte maneira:
* - os dois primeiros elementos da matriz são ordenados
* - o terceiro elemento é introduzido em sua posição ordenada
em relação aos dois primeiros
* - o quarto elemento é introduzido em sua posição ordenada
em relação aos três primeiros
* - o quinto elemento é introduzido em sua posição ordenada
em relação aos quatro primeiros
*
* e assim por diante até que toda a matriz esteja ordenada.*/
#include <stdio.h>
int main()
{
int vetor_original[5], vetor_ordenado[5];
int contador,contador2,contador3;
int ok = 0;
printf("Ordenando uma matriz utilizando o método da inserção.\n");
/* entrada de dados */
for(contador=0;contador < 5; contador++)
{
printf("Entre com o %do valor :",(contador+1));
scanf("%d",&vetor_original[contador]);
}
/* ordenação */
/* ordenando os dois primeiros elementos */
if(vetor_original[0] < vetor_original[1])
{
vetor_ordenado[0] = vetor_original[0];
vetor_ordenado[1] = vetor_original[1];
}
else
{
vetor_ordenado[0] = vetor_original[1];
vetor_ordenado[1] = vetor_original[0];
}
/* ordenando os outros elementos */
for(contador = 2;contador < 5; contador++)
{
/* introduzindo o elemento vetor_original[contador]
no vetor_ordenado */
ok = 1; /* considera vetor_ordenado não ordenado */
/* verificando se algum dos elementos de vetor_ordenado
é maior que vetor_original[contador] */
for(contador2 = 0;contador2 < contador;contador2++)
{
if(vetor_ordenado[contador2] > vetor_original[contador]){
/* jogando os elementos de vetor_ordenado
para frente */
for(contador3 = contador;contador3 > contador2;contador3--)
vetor_ordenado[contador3] = vetor_ordenado[contador3 - 1];
/* inserindo vetor_original[contador
em sua posição ordenada */
vetor_ordenado[contador2] = vetor_original[contador];
ok =0; /* considerando vetor_ordenado ordenado */
break;
}
}
/* se nenhum elemento de vetor_ordenado é maior que
vetor_original[contador] ... */
if(ok == 1)
vetor_ordenado[contador] = vetor_original[contador];
}
/* imprimindo os valores ordenados */
printf("\n");
for(contador = 0;contador < 5;contador++)
printf("%d ",vetor_ordenado[contador]);
printf("\n");
return(0);
}
|
12.9 Ordenando os elementos de uma matriz pelo método shell
Este método de ordenação oferece uma performance bem melhor que os anteriormente mostrados. Nele compara-se elementos separados por uma distância específica ordenando-os. Esta distância então é dividida por dois e o processo continua até que a matriz esteja ordenada.
Vamos ao nosso exemplo prático com a matriz:
nota[0] = 67 nota[1] = 55 nota[2] = 86 nota[3] = 79 nota[4] = 68 nota[5] = 99 nota[6] = 0 nota[7] = 34 nota[8] = 18 nota[9] = 27 |
Nossa matriz tem dez elementos. Vamos começar nossa ordenação ordenando os elementos separados de cinco posições. Então compararemos nota[0] e nota[5]. Como estes elementos estão ordenados, nosso programa nada faria.
Agora serão comparados nota[1] e nota[6]. Como estão fora de ordem, serão ordenados e nossa matriz ficará assim:
nota[0] = 67 nota[1] = 0 nota[2] = 86 nota[3] = 79 nota[4] = 68 nota[5] = 99 nota[6] = 55 nota[7] = 34 nota[8] = 18 nota[9] = 27 |
Agora nota[2] e nota[7]. Como estão desordenados, haverá ordenação e a matriz ficará assim:
nota[0] = 67 nota[1] = 0 nota[2] = 34 nota[3] = 79 nota[4] = 68 nota[5] = 99 nota[6] = 55 nota[7] = 86 nota[8] = 18 nota[9] = 27 |
Agora nota[3] e nota[8]:
nota[0] = 67 nota[1] = 0 nota[2] = 34 nota[3] = 18 nota[4] = 68 nota[5] = 99 nota[6] = 55 nota[7] = 86 nota[8] = 79 nota[9] = 27 |
E nota[4] com nota[9]:
nota[0] = 67 nota[1] = 0 nota[2] = 34 nota[3] = 18 nota[4] = 27 nota[5] = 99 nota[6] = 55 nota[7] = 86 nota[8] = 79 nota[9] = 68 |
Terminado este ciclo de comparações a nossa distância será dividida por dois, sendo agora igual a três, já que devemos usar números inteiros para definir esta distância. Agora vamos a outro ciclo de comparações, só que desta vez com os elementos separados por três posições.
Iniciando com a comparação de nota[0] e nota[3], haveria ordenação e nossa matriz agora ficará assim:
nota[0] = 18 nota[1] = 0 nota[2] = 34 nota[3] = 67 nota[4] = 27 nota[5] = 99 nota[6] = 55 nota[7] = 86 nota[8] = 79 nota[9] = 68 |
Agora nota[1] com nota[4], como estão ordenados não há nenhuma mudança.
Agora nota[2] com nota[5], também sem mudanças.
nota[3] com nota[6]. Estão desordenados. Nossa matriz agora ficará assim:
nota[0] = 18 nota[1] = 0 nota[2] = 34 nota[3] = 55 nota[4] = 27 nota[5] = 99 nota[6] = 67 nota[7] = 86 nota[8] = 79 nota[9] = 68 |
Agora nota[4] com nota[7]. Como os elementos estão ordenados, não há mudanças.
nota[5] com nota[8] estão desordenados, então haverá reordenação:
nota[0] = 18 nota[1] = 0 nota[2] = 34 nota[3] = 55 nota[4] = 27 nota[5] = 79 nota[6] = 67 nota[7] = 86 nota[8] = 99 nota[9] = 68 |
E terminando este ciclo a comparação de nota[6] com nota[9] não alterará a matriz pois os elementos estão ordenados.
Agora a distância é novamente dividia por dois e nossa nova distância será dois, pois não podemos usar a distância 1,5.
Abaixo temos as comparações deste novo ciclo;
nota[0] com nota[2] => estão ordenados, matriz inalterada.
nota[1] com nota[3] => estão ordenados, matriz inalterada.
nota[2] com nota[4] => estão desordenados, a matriz fica assim:
nota[0] = 18 nota[1] = 0 nota[2] = 27 nota[3] = 55 nota[4] = 34 nota[5] = 79 nota[6] = 67 nota[7] = 86 nota[8] = 99 nota[9] = 68 |
nota[3] com nota[5] => estão ordenados, matriz inalterada.
nota[4] com nota[6] => estão ordenados, matriz inalterada.
nota[5] com nota[7] => estão ordenados, matriz inalterada.
nota[6] com nota[8] => estão ordenados, matriz inalterada.
nota[7] com nota[9] => estão desordenados, a matriz fica assim:
nota[0] = 18 nota[1] = 0 nota[2] = 27 nota[3] = 55 nota[4] = 34 nota[5] = 79 nota[6] = 67 nota[7] = 68 nota[8] = 99 nota[9] = 86 |
E agora o ciclo final. Dividindo nossa distância atual (2) por dois teremos a comparação dos elementos separados por uma posição.E ao final deste ciclo nossa matriz estaria ordenada.
O único detalhe a ser observado é evitar sequências de distâncias que são potência de dois, pois elas reduzem a eficiência deste algoritmo.Por exemplo: a sequência "8,4,2,1" não é interessante,seria melhor "7,3,2,1".
Abaixo segue uma codificação deste exemplo:
/* ordenando uma matriz pelo método shell *
*
* neste método a ordenação é feita da seguinte maneira:
* - compara-se os elementos separados por uma distância específica
* - divide-se esta distância por dois
* - compara-se os elementos separados pela nova distância
* - divide-se a distância por dois novamente
* e assim por diante, até que toda a matriz esteja ordenada */
#include <stdio.h>
int main()
{
int QDE = 10;
int vetor[QDE],contador1,contador2,distancia,auxiliar;
printf("Ordenando uma matriz utilizando o método shell.\n");
/* entrada de dados */
for(contador1 = 0;contador1 < QDE; contador1++)
{
printf("Entre com o %do valor :",(contador1+1));
scanf("%d",&vetor[contador1]);
}
/* ordenação */
distancia = QDE;
do
{
distancia = (distancia + 1) / 2;
for(contador2 = 0;contador2 < (QDE - distancia); contador2++)
{
if(vetor[contador2] > vetor[contador2 + distancia])
{
auxiliar = vetor[contador2 + distancia];
vetor[contador2 + distancia] = vetor[contador2];
vetor[contador2] = auxiliar;
}
}
}
while (distancia > 1);
/* imprimindo os valores ordenados */
printf("\n");
for(contador1 = 0;contador1 < QDE;contador1++)
printf("%d ",vetor[contador1]);
printf("\n");
return(0);
}
|
12.10 Ordenando os elementos de uma matriz pelo método quick sort
Para matrizes com muitos elementos este é o método de ordenação mais rápido. Neste tipo de ordenação o programa considera sua matriz uma lista de valores. Inicialmente é selecionado o valor que está posicionado no meio da lista que chamaremos de elemento central. Depois a matriz é dividida e ordenada em duas listas menores separando numa os elementos cujo valor é maior que o valor do elemento central e e na outra os elementos cujo valor é menor que o valor do elementro central. A partir daí o mesmo processo é feito com cada uma das listas recursivamente. Isso continua até que a matriz esteja toda ordenada.
Considere a matriz formada pelos valores inteiros: 6, 2, 1, 3, 4, 5, 8, 7 e 0. A figura abaixo mostra como poderíamos classificar esta matriz em ordem crescente usando o quick sort.
Abaixo segue o exemplo de um código que ordena em ordem crescente, pelo método quick sort, uma matriz de valores inteiros:
/* ordenando uma matriz pelo método quick sort */
#include <stdio.h>
void quick_sort(int matriz[], int primeiro, int ultimo)
{
int temp, baixo,alto,separador;
baixo = primeiro;
alto = ultimo;
separador = matriz[(primeiro + ultimo) / 2];
do
{
while(matriz[baixo] < separador)
baixo++;
while(matriz[alto] > separador)
alto--;
if(baixo <= alto)
{
temp = matriz[baixo];
matriz[baixo++] = matriz[alto];
matriz[alto--] = temp;
}
}
while(baixo <= alto);
if(primeiro < alto)
quick_sort(matriz,primeiro,alto);
if(baixo < ultimo)
quick_sort(matriz,baixo,ultimo);
}
int main()
{
int QDE = 10;
int vetor[QDE],contador;
printf("Ordenando uma matriz utilizando o método quick sort.\n");
/* entrada de dados */
for(contador = 0;contador < QDE; contador++)
{
printf("Entre com o %do valor :",(contador+1));
scanf("%d",&vetor[contador]);
}
quick_sort(vetor,0,(QDE-1));
/* imprimindo os valores ordenados */
printf("\n");
for(contador = 0;contador < QDE;contador++)
printf("%d ",vetor[contador]);
printf("\n");
return(0);
}
|
|
|
Se esta página lhe ajudou, considere fazer uma doação |
| <<< Voltar | Avançar >>> |