Ordenação vetores

Ordenação por Inserção (Insertion Sort) Ordenação por inserção (Insertion Sort), é um dos métodos de ordenação simples de implementar e também fácil de compreender o seu funcionamento. Entrada: Uma sequencia de n números (a1, a2, ... , an). Saída: Uma permutação (reordenação) (a1', a2', ..., an') da sequencia de entrada, de modo que a1' < a2' < ... < an' Os números que desejamos ordenar são conhecidos por chaves(keys). A ordernação por inserção é eficiente para ordenar um número pequeno de elementos, e ela funciona de modo muito semelhante a forma como as pessoas ordenam as cartas de um jogo de pôquer. Começamos com a mão esquerda vazia e as cartas viradas com a face para baixo na mesa. Em seguida, removeremos uma carta de cada vez da mesa, inserindo-a na posição correta na mão esquerda. Para saber qual a posição correta de uma carta devemos compará-la com as cartas que já estão na mão, da direita para a esquerda. Em cada instante as cartas na mão esquerda são ordenadas. Exemplo: Considere o vetor A representado na figura seguinte: 1 6 2 1 3 0 4 5 5 4

1 6

Algoritmo Ord_Inserção sobre o vetor A: i=2 3 4 1=chave 0 5

5 4

a) O elemento 6 é deslocado uma posição à direita e o valor chave é inserido na posição A[1]. 1 1 2 6 i=3 0=chave 4 5 5 4

b) Os elementos 6 e 1 são deslocados para a direita e o valor chave é inserido na posição A[1]. 1 0 2 1 3 6 i=4 5=chave 5 4

c) O elemento 6 é deslocado uma posição à direita e o valor chave é inserido na posição A[3]. 1 0 2 1 3 5 4 6 i=5 4=chave

d) Os elementos 6 e 5 são deslocados para a direita e o valor chave é inserido na posição A[3].

Vetor A ordenado: 1 0 2 1 3 4 4 5 5 6

ALGORÍTMO DO INSERTION SORT
SUB-ROTINA Ord_Inserção (A[n] NUMÉRICO) DECLARE inteiro i, j, chave NUMÉRICO 1 PARA i ←2 até n FAÇA INÍCIO 2 chave ←A[ i] 3 j←i-1 4 ENQUANTO j > 0 e A[j] > chave FAÇA INÍCIO 5 A[j+1] ← A[j] 6 j←j-1 FIM 7 A[j+1] ← chave FIM

CÓDIGO C DO INSERTION SORT
#include # define TAMANHO 6 void