Pagina anteriorIndiceProxima pagina

Algoritmos Computacionais

4.2 Ordenação de Vetores

Ordenar um vetor de N números inteiros em ordem crescente.

 Algoritmo
1.Repetir N vezes
2.Procurar o menor valor do vetor
3.Copiar este valor para a menor posição de um vetor alternativo
4.Mudar este valor para um valor bem alto
2.1 Índice_min <- 1
2.2 Para I <- 1 até N faça
2.3     Se VETOR[I] < VETOR[Índice_min]
          Então Índice_min <- I 
          Fim Se
3.1 Vetor_Alternativo[Posição_min] <- VETOR [Índice_min]
4.1 VETOR[Índice_min] <- 9999

Variáveis
Índice_Min: Inteira <- Posição do menor elemento
Vetor [ ]: Conjunto De N Números Inteiros Desordenados
Vetor_Alternativo [ ]: Ordenado
Posição_Min: Inteira <- Posição ainda não ocupada do Vetor_Al-ternativo
I: Inteira <- Controle do laço
N: Inteira <- Número de elementos
 
Algoritmo Ordena
Início
   Para Posição_Min <- 1 Até N Faça
      Índice_Min <- 1
      Para I <- 2 Até N Faça
          Se Vetor[I] < Vetor[Índice_Min]
          Então Índice_Min <- I
          Fim Se
      Fim Para
  Vetor_Alternativo[Posição_Min] <- Vetor[Índice_Min]
  Vetor[Índice_Min] <- 9999
 Fim Para
Fim de Ordena

Usando apenas um vetor, trocar o menor elemento numa passagem pelo elemento atualmente em teste.
 
Algoritmo Ordena
Aux:Inteiro
Início
 Para Posição_Min <- 1 Até N-1 Faça
  Índice_Min <- Posição_Min
  Para I <- Posição_Min + 1 Até N Faça
   Se Vetor[I] < Vetor[Índice_Min]
   Então Índice_Min <- I
   Fim Se
  Fim Para
  Se Índice_Min  <> Posição_Min
  Então Aux <- Vetor[Posição_Min]
        Vetor[Posição_Min] <- Vetor[Índice_Min]
        Vetor[Índice_Min] <- Aux
  Fim Se
 Fim Para
Fim de Ordena

1ºAlgoritmo tem complexidade     N*(N-1)
O segundo tem complexidade dada por: 
 O conceito de vetor pode ser generalizado para o conceito de matriz.
Ex.: MATRIZ_A [3,4] conjunto de inteiros
Matriz_A[1,1] = 10
Matriz_A[2,3] = 1


Pagina anteriorIndiceProxima pagina

araujo@eng.uerj.br