Selection Sort

Páginas: 8 (1905 palavras) Publicado: 21 de julho de 2014
Estudo Detalhado do Algoritmo de Ordenação Insertion Sort
Gabriela N. Pereira¹, Igor S. O. Lima¹, José Gomes S. Júnior¹, Matheus S. Araújo¹
¹Curso de Ciência da Computação – Universidade Federal de Alagoas (UFAL)
Caixa Postal 61 – 57.600­000 – Arapiraca – AL – Brazil
{aiuec,igrsme,jnoj,mtesma7}galcm
gbnnsc io.ios uir9 ahu.s2,@mi.o

Abstract.  The  purpose  of  this  article  is to present a sorting algorithm Insertion
Sort,  making  us  reflect  on  its  importance,  analyzing  it  and  noting  its  main
features  ,  such  as  the  runtime  of  the  algorithm  in  a  worst,  and  in  a  best  case
and the issues we can have because of its use.
Resumo.  A  finalidade  deste  artigo  é  apresentar  o  algoritmo  de  ordenação
Insertion  Sort,  fazendo­nos  refletir sobre  sua  importância,  analizando­o  e
observando  suas  principais  características,  tais  como  o  tempo  de  execução do
algoritmo  em  um  pior  caso,  em  um  melhor  caso,  e  os  problemas  que podemos
obter através de seu uso.

1. Introdução
Relembrando  o  conceito  de  algoritmo,  podemos  afirmar  que  este  é um conjunto de regras ou
passos  definidos  e  ordenados  com  a finalidade  de  resolver  um  ou  mais  problemas.  Um
algoritmo  pode  ser  descrito  basicamente  de  duas  formas  (BERG  e  FIGUEIRÓ,  1998):  uma
forma  gráfica  a  partir  da  utilização  de  diagramas   de  blocos  e  outra  forma  textual  com  a
utilização  de  uma  linguagem  de  projeto  de  programação  ou  mesmo  de  uma  linguagem  de
programação   de  computadores  formal. Num  sentido  mais  amplo,  algoritmo  é  um  processo
sistemático  para   a  resolução  de  um  determinado  problema  (SZWARCFITER  &
MARKENZON,  1994)  ou  de  uma  sequência  ordenada  de  passos  para  a  realização  de  uma
determinada tarefa (SALIBA, 1992; BERG & FIGUEIRÓ, 1998).
Algoritmos  de  ordenação  são  algoritmos  responsáveis  por  ordenar  uma sequência de
dados  de acordo  com   uma  ordem  predefinida,  com  a  finalidade  de   acessar  esses  dados  de
maneira  mais  eficiente.  O  Insertion  Sort, como o próprio nome sugere, é um tipo de algoritmo
de  ordenação,  que  assim  como  os  demais  algoritmos,  ordena  conjuntos  de  dados  de acordo
com a ordem desejada, seja ela númerica ou alfabética.

2. Insertion Sort
2.1. Conceito
Como  já  foi introduzido  anteriormente,  o  Insertion  Sort  é um algoritmo de ordenação. Dentre
algoritmos  mais  simples  de  ordenação(Bubble  Sort  e  Selection  Sort)  e  se  tratando  da
aplicação  de   um  pequeno  número  de  elementos,  é  considerado  o  mais  eficiente,  e  também
considerado por muitos um dos melhores para ser implementado.
  Para  exemplos  do  insertion  sort,  podemos  ter  uma  lista  de  nomes,  ou  um  exemplo
mais  clássico  e  fácil  de  entender,  uma  sequência  de  cartas de baralho na mão de um jogador,
onde  o  jogador  irá  tirando  carta  por  carta,  e  cada  carta  que  é tirada será comparada com as
demais, de uma por uma, e alocada no seu devido local.
O  algoritmo  não  possui  um  custo  fixo,  pois  isso é determinado de acordo com o grau
de  ordenação  do  vetor,  que  caso  já  esteja  ordenado,  não  precisará  realizar  trocas,  dessa
forma  será  executado  bem  mais  rápido  do  que  se  o  vetor  estiver  totalmente  em  ordem
decrescente.
● Melhor  caso  é  quando  todos  os  elementos  já  estão  ordenados,  característica   essa,
muito  importante,  pois  é  neste  caso  que  acontece  o  menor  número  de trocas  e
comparações. Custo: 
● Pior caso é quando os elementos estão em ordem decrescente. Custo: 
Vantagens:
● Algorítmo Estável;
● Fácil Implementação;
● Com  um  vetor  já  ordenado,   ele  vai  favorecer  a  ordenação,  sendo  o  melhor
caso 
.
Desvantagens:
● Tem um número grande de movimentações;
● Ordem de complexidade quadrática 
, pior caso;
● Ineficiente quando  o...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Selection sort
  • SELECTION SORT
  • Selection sort
  • SELECTION SORT
  • Ordenação por Selection Sort
  • ALGORITMOS DE ORDENAÇÃO BUBBLE SORT e SELECTION SORT
  • Trabalho Em Grupo Sobre Selection Sort
  • Comparação entre os algoritmos de ordenação de dados: buble sort, quick sort, selection sort, inserction sort,...

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!