PO2_ufc

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

2011
Gerardo Valdisio Rodrigues Viana
Glauber Ferreira Cintra
Pesquisa e Ordenação de Dados
 !"#$%&'(
 ! "#$%&'!(!)'(*+#,-!.-!('.#%-/0(
 ! 1)'#2#%3-'!(2!,43(.(2!.#!5+-22&$5-/0(!&%3#'%-
 ! 1%-+&2-'!-!5(,)+#6&.-.#!.(2!-+7('&3,(2!.#!('.#%-/0(!
Ordenação Interna
Capítulo
2
21PESQUISA E ORDENAÇÃO DE DADOS
Apresentação
8#23#!5-)93:+(!&%&5&-,(2!.#$%&%.(!;(',-+,#%3#!(!)'(*+#,-!.-!('.#-
%-/0(!#!(2!)'&%5&)-&2!5'&34'&(2!.#!5+-22&$5-/0(!.#!.-.(2<!=,!2#7:&.->!-)'#-
2#%3-,(2! #,!.#3-+?#2! (2!,43(.(2! .#! ('.#%-/0(! &%3#'%->! .&25:3&%.(! 2:-!
#$5&@%5&-!#,!3#',(2!.#!5(%2:,(!.#!3#,)(!#!.#!,#,A'&-!#!(:3'(2!-2)#53(2!
'#+#B-%3#2<!8-!('.#,>!-*('.-'#,(2!(2!,43(.(2!C(+?->!D%2#'/0(!#!E#+#/0(!
F:#!20(!*-23-%3#!2&,)+#2!#!2#'B#,!)-'-!&%3'(.:G&'!&.#&-2!-!2#'#,!:3&+&G-.-2!
#,!(:3'(2!,43(.(2!,-&2! #$5&#%3#2<!E#7:&,(2! 5(,!(2!,43(.(2!E?#++2('3>!
H#'7#2('3>!I:&5J2('3!#!K#-)2('3>!5(%2&.#'-.(2!2:)#'&('#2!-(2!-%3#'&('#2>!
3-,*4,>!5(,(!#+#2>! !*-2#-.(2!%-!()#'-/0(!.#!5(,)-'-/0(<!L('!$,>!.&2-
5:3&'#,(2!(2!,43(.(2!M(:%3&%72('3>!C:5J#32('3! #!N-.&62('3! F:#! 3@,!#,!
5(,:,!(!;-3(!.#!%0(!:3&+&G-'#,!-!()#'-/0(!.#!5(,)-'-/0(!#>!2(*!-+7:,-2!
?&)A3#2#2>!#+#2!('.#%-,!#,!3#,)(! +&%#-',#%3#!)'()('5&(%-+!-(! 3-,-%?(!
da lista.
1. Ordenação Interna
M(,(!.&3(!%(!5-)93:+(!-%3#'&('>!-!('.#%-/0(!.#!.-.(2!4!:,!.(2!)'(*+#-
mas mais importantes e mais estudados dentro da ciência da computação. 
Em diversas situações cotidianas é preciso colocar uma lista em ordem 
para facilitar a busca de informações nela contidas.
8#23#!5-)93:+(!.&25(''#,(2!2(*'#!(2!)'&%5&)-&2!5'&34'&(2!.#!('.#%-/0(>!
.#$%&%.(!-%3#2>!%-!2#/0(!O>!;(',-+,#%3#!(!)'(*+#,-!.-!('.#%-/0(<!8-2!2#-
/P#2!2#7:&%3#2!20(!-)'#2#%3-.(2!#,!.#3-+?#2!(2!.&B#'2(2!,43(.(2!.#!('.#-
%-/0(!&%3#'%-<!L-'-!5-.-!:,!.#+#2!4!,(23'-.-!2:-!#$5&@%5&-!#,!3#',(2!.#!
5(%2:,(!.#!3#,)(!#!.#!,#,A'&-!#!(:3'(2!-2)#53(2!5(%2&.#'-.(2!'#+#B-%3#2<!
D%&5&-+,#%3#>! %-2! 2#/P#2! Q>! R! #! S>! -*('.-'#,(2! (2!,43(.(2!Bolha, 
Inserção e Seleção. Tais métodos, considerados inferiores, são bastante sim-
)+#2>!,-2!&%3'(.:G#,!&.#&-2!F:#!2#'B#,!.#!*-2#!)-'-!(:3'(2!,43(.(2!,-&2!
#$5&#%3#2<!=22#2!,43(.(2!:3&+&G-,!5(,(!:,-!.#!2:-2!()#'-/P#2!*T2&5-2!-!
comparação de elementos da lista.
Em seguida, nas seções 6, 7, 8 e 10, apresentaremos os métodos Shell-
sort, Mergesort, Quicksort e Heapsort. Esses métodos, considerados supe-
'&('#2>!:3&+&G-,!#23'-347&-2!,-&2!2($23&5-.-2!5(,(>!)('!#6#,)+(>!divisão e 
conquista!#!(!:2(!.#!#23':3:'-2!.#!.-.(2!5(%?#5&.-2!5(,(!heaps binários, 
.#25'&3(2!%-!E#/0(!U<!=22#2!,43(.(2!3-,*4,!20(!*-2#-.(2!%-!()#'-/0(!.#!
comparação.
L('!$,>!%-2!2#/P#2!VV>!VO!#!VQ>!.&25:3&'#,(2!(2!,43(.(2!Countingsort, 
Bucketsort e Radixsort<!=22#2!W+3&,(2!,43(.(2!3@,!#,!5(,:,!(!;-3(!.#!%0(!
:3&+&G-'#,!-!()#'-/0(!.#!5(,)-'-/0(<!1+4,!.&22(>!2(*!5#'3-2!?&)A3#2#2>!#+#2!
('.#%-,!#,!3#,)(!+&%#-',#%3#!)'()('5&(%-+!-(!3-,-%?(!.-!+&23-<
22 PESQUISA E ORDENAÇÃO DE DADOS
2. O Problema da Ordenação
L-'-!F:#!:,-!+&23-!)(22-!2#'!('.#%-.-!(2!2#:2!#+#,#%3(2!.#B#,!2#'!
dois a dois comparáveis<! D22(!2&7%&$!5-!F:#!.-.(2!.(&2!#+#,#%3(2!.-! +&23-!
.#B#!2#'!2#,)'#!)(229B#+!.#3#',&%-'!2#!#+#2!20(!#F:&B-+#%3#2!(:!2#!:,!.#+#2!
4!X,#%('Y!F:#!(!(:3'(<!1!&.4&-!-22(5&-.-!-(!3#',(!X,#%('Y!.#)#%.#!.(!5'&Z
34'&(!.#!5(,)-'-/0(!:3&+&G-.(<
"&GZ2#!F:#!:,-! +&23-!#23T!#,!('.#,!5'#25#%3#!2#!5-.-!:,!.#!2#:2!
elementos é menor ou igual ao seu sucessor segundo algum critério de 
5(,)-'-/0(<!1!.#$!%&/0(!.#!('.#,!.#5'#25#%3#!4!-%T+(7-<!M(,(!.&3(>!:,-!
lista somente pode ser colocada em ordem se os seus elementos forem dois 
-!.(&2!5(,)-'TB#&2<![!)'(*+#,-!.-!('.#%-/0(!5(%2&23#!#,>!.-.-!:,-!+&23->!
5(+(5TZ+-! #,!('.#,!5'#25#%3#!(:!.#5'#25#%3#<![2!)'&%5&)-&2! 5'&34'&(2! 20(!
5(,)-'-/0(!%:,4'&5->!5(,)-'-/0(!-+;-*43&5-!#!5(,)-'-/0(!5'(%(+A7&5-<!
 ! M(,)-'-/0(!%:,4'&5-\!:,!%W,#'(!x!4!,#%('!.(!F:#!:,!%W,#'(!y 
2#!-!#6)'#220(!x – y!'#2:+3-!#,!:,!%W,#'(!%#7-3&B(<!=22#!4!(!3&)(!
mais comum de comparação e, de certa forma, todos os demais cri-
térios de comparação derivam dele.
 ! M(,)-'-/0(!-+;-*43&5-\!:,!5-'-53#'#!4!,#%('!.(!F:#!(:3'(!2#!)'#Z
5#.#!#22#!(:3'(!%-!('.#,!.(!-+;-*#3(<!L('!#6#,)+(>!(!5-'-53#'#!X-Y!
)'#5#.#!(!X*Y>!(!X*Y!)'#5#.#!(!X5Y!#!-22&,!)('!.&-%3#<!8(!5(,):3-.('>!
(2!5-'-53#'#2!20(!'#)'#2#%3-.(2!-3'-B42!.#!%W,#'(2!]2#7:%.(!-+7:Z
,-!5(.&$!5-/0(>!)('!#6#,)+(>!1EMDD>!^8DM["=!#35_<!"#22-!;(',->!-!
comparação entre caracteres acaba sendo uma comparação entre os 
2#:2!5A.&7(2!%:,4'&5(2!#>!)('3-%3(>!4!:,-!5(,)-'-/0(!%:,4'&5-<
 ! M(,)-'-/0(!5'(%(+A7&5-\!^,-!.-3-!4!,#%('!.(!F:#!(:3'-!2#!#+-!-%Z
tecede essa outra. Uma data pode ser representada através de três 
%W,#'(2>!:,!)-'-!'#)'#2#%3-'!(!-%(>!(:3'(!)-'-!(!,@2!#!(:3'(!)-'-!
o dia. Ao comparar uma data com outra, comparamos o ano. Em 
caso de empate, comparamos o mês. Em caso de novo empate, com-
)-'-,(2!(!.&-<!E#%.(!-22&,>!-!5(,)-'-/0(!5'(%(+A7&5-!3-,*4,!4!
;#&3-!5(,)-'-%.(Z2#!%W,#'(2<
`!)(229B#+!.#$!%&'!(:3'(2!5'&34'&(2!.#!5(,)-'-/0(<!L('!#6#,)+(>!)(.#Z
,(2!5(,)-'-'!5-&6-2>!5(%2&.#'-%.(!,#%('!-F:#+-!F:#!-)'#2#%3-'!,#%('!
B(+:,#<!M(,(!(!B(+:,#!4!#6)'#22(!)('!:,!%W,#'(>!#22#!3&)(!.#!5(,)-'-Z
ção também é uma comparação numérica. 
L(.#'9-,(2>!%(!#%3-%3(>!5(%2&.#'-'!:,-!5-&6-!,#%('!.(!F:#!(:3'-!2#!
ela cabe!%#22-!(:3'-<!8#22#!5-2(>!)(.#,(2!3#'!5-&6-2!&%5(,)-'TB#&2<!^3&Z
+&G-%.(!#22#!5'&34'&(!.#!5(,)-'-/0(>!)(.#,(2!3#'!:,-!+&23-!.#!5-&6-2!F:#!
%0(!)(.#!2#'!('.#%-.-<!1+4,!.&22(>!F:-%.(!3#,(2!+&23-2!?#3#'(7@%#-2>!)(.#!
%0(!2#'!)(229B#+!('.#%TZ+-<!L('!#6#,)+(>!-! +&23-! ]R>! X*(+-Y>!O>!VSabOaObVV_!
não pode ser ordenada, pois seus elementos não são todos dois a dois com-
)-'TB#&2<
"&G#,(2!F:#!:,-!+&23-!#23T!#,!ordem crescente se cada elemento da 
+&23-!4!,#%('!(:!&7:-+!]2#7:%.(!(!5'&34'&(!.#!5(,)-'-/0(!-.(3-.(_!-(!2#:!2:Z
5#22('<!E#!5-.-!#+#,#%3(!.-!+&23-!4!#23'&3-,#%3#!,#%('!.(!F:#!2#:!2:5#22('>!
.&G#,(2!F:#!-!+&23-!#23T!#,!ordem estritamente crescente. Analogamente, 
.&G#,(2!F:#!:,-!+&23-!#23T!#,!ordem decrescente se cada elemento da lista 
4!,-&('!(:!&7:-+!-(!2#:!2:5#22('<!E#!5-.-!#+#,#%3(!.-!+&23-!4!#23'&3-,#%3#!
,-&('!.(!F:#!2#:!2:5#22('>!.&G#,(2!F:#!-!+&23-!#23T!#,!ordem estritamente 
decrescente<![*B&-,#%3#>!('.#%-/0(!#23'&3-!2(,#%3#!4!)(229B#+!2#!3(.(2!(2!
elementos da lista forem distintos.
1EMDD! Z! 1,#'&5-%! E3-%Z
.-'3!M(.#!;('!D%;(',-3&(%!
D%3#'5?-%7#! Z! MA.&7(! )-Z
drão americano para o in-
tercâmbio de informação
1F:&+(! F:#! .#$!%&,(2!
como ordem crescente é 
5?-,-.-! )('! -+7:%2! -:Z
tores de ordem não de-
crescente!#%F:-%3(!F:#!(!
F:#! 5?-,-,(2! .#! ordem 
estritamente crescente é 
5?-,-.-! )('! #22#2! ,#2Z
mos autores de ordem 
crescente<! [! F:#! 5?-,-Z
mos de ordem decrescen-
te! 4! 5?-,-.-! )('! -+7:%2!
de ordem não crescente 
#%F:-%3(! F:#! -! ordem 
estritamente decrescente 
4! 5?-,-.-! .#! ordem de-
crescente.
23PESQUISA E ORDENAÇÃO DE DADOS
[!)'(*+#,-!.-!('.#%-/0(!5(%2&23#!#,>!.-.-!:,-!+&23-!5:c(2!#+#,#%3(2!
2#c-,!3(.(2!.(&2!-!.(&2!5(,)-'TB#&2>!)#',:3-'!-!('.#,!.#!2#:2!#+#,#%3(2!
.#!,(.(!-!.#&6-'!-!+&23-!#,!('.#,!5'#25#%3#!(:!.#5'#25#%3#<
E#!-!+&23-!%0(!;('!,:&3(!7'-%.#!#+-!)(.#!2#'!-',-G#%-.-!%-!,#,A'&-!
)'&%5&)-+!]&%3#'%-_!.(!5(,):3-.('!#!2#'!('.#%-.-!:2-%.(!-)#%-2!-!,#,A'&-!
&%3#'%-<![2!-+7('&3,(2!F:#!('.#%-,!:3&+&G-%.(!-)#%-2!,#,A'&-!&%3#'%-!20(!
5?-,-.(2!.# métodos de ordenação de interna. 
=,!5(%3'-)-'3&.->!(2!-+7('&3,(2!F:#!;-G#,!:2(!.#!,#,A'&-!#63#'%-!
20(!5?-,-.(2!.# métodos de ordenação de externa. Alguns desses métodos 
2#'0(!.&25:3&.(2!%(!M-)93:+(!Q<
8(!'#23-%3#!.#23#!5-)93:+(!.#25'#B#'#,(2!.&B#'2(2!,43(.(2!.#!('.#-
%-/0(! &%3#'%-<!=,*('-!:,-! +&23-!)(22-!2#'!-',-G#%-.-!:2-%.(Z2#!:,-!
+&23-!#%5-.#-.->!.#25'#B#'#,(2!(2!-+7('&3,(2!5(%2&.#'-%.(!F:#!-!+&23-!#23T!
-',-G#%-.-!%:,!B#3('!&%.#6-.(!-!)-'3&'!.-!)(2&/0(!G#'(<!1+4,!.&22(>!5(%-
2&.#'-'#,(2!F:#!(!B#3('!-',-G#%-!%W,#'(2!#>!)('3-%3(>!(!5'&34'&(!.#!5(,-
)-'-/0(!2#'T!%:,4'&5(<!8-!.#25'&/0(!.(2!-+7('&3,(2!.#!('.#%-/0(>!B-,(2!
2#,)'#!5(%2&.#'-'!F:#!(!B#3('!4!)-22-.(!)('!'#;#'@%5&-<
M(%B4,!2-+&#%3-'!F:#!-!+&23-!)(.#!2#'!5(%23&3:9.-!.#!'#7&23'(!#!)(.#-
,(2!('.#%TZ+-!)('!:,!.#!2#:2!5-,)(2>!F:#!5?-,-,(2!.#!5?-B#!.#!('.#-
nação. A comparação entre os elementos da lista é feita comparando-se os 
B-+('#2!.-2!5?-B#2!.#!('.#%-/0(!.(2!.(&2!#+#,#%3(2<
[*B&-,#%3#>!(2!,43(.(2!-F:&!.#25'&3(2!)(.#,!2#'!;-5&+,#%3#!-.-)3--
.(2!)('!('.#%-'!+&23-2!#%5-.#-.-2!5:c(2!#+#,#%3(2!20(!'#7&23'(2<!=,!-+7:%2!
#6#'595&(2!3-&2!-.-)3-/P#2!20(!'#F:#'&.-2<
3. Bolha
[!H43(.(!C(+?-!4!*-23-%3#!2&,)+#2!#!&%3:&3&B(<!8#22#!,43(.(!(2!#+#-
,#%3(2!.-!+&23-!20(!,(B&.(2!)-'-!-2!)(2&/P#2!-.#F:-.-2!.#!;(',-!5(%39%:->!
-22&,!5(,(!:,-!*(+?-!,(B#Z2#!%:,!+9F:&.(<!E#!:,!#+#,#%3(!#23T!&%&5&-+-
,#%3#!%:,-!)(2&/0(!&!#>!)-'-!F:#!-!+&23-!$F:#!('.#%-.->!#+#!.#B#!(5:)-'!-!
)(2&/0(!c>!#%30(!#+#!3#'T!F:#!)-22-'!)('!3(.-2!-2!)(2&/P#2!#%3'#!&!#!c<
=,!5-.-!&3#'-/0(!.(!,43(.(>!)#'5(''#,(2!-!+&23-!-!)-'3&'!.#!2#:!&%9-
cio comparando cada elemento com seu sucessor, trocando-os de posição 
2#!?(:B#'!%#5#22&.-.#<!`!)(229B#+!,(23'-'!F:#>!2#!-!+&23-!3&B#'!n elementos, 
-)A2!%(!,T6&,(!]%dV_!&3#'-/P#2!-!+&23-!#23-'T!#,!('.#,<!1!2#7:&'!;('%#5#-
,(2!:,-!.#25'&/0(!#,!)2#:.(5A.&7(!.(!C(+?-<
ALGORITMO BOLHA 
 ENTRADA: UM VETOR L COM N POSIÇÕES 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 PARA i = 1 até n - 1 
 PARA j = 0 até n – 1 - i 
 SE L[j] > L[j+1] 
 AUX = L[j] // SWAP 
 L[j] = L[j+1] 
 L[j+1] = AUX
FIM {BOLHA}
Algoritmo 2.1: Bolha
8-!.#25'&/0(!.(!1+7('&3,(!C(+?-!.#&6-,(2!5+-'(!5(,(!'#-+&G-'!-!3'(5-!
(swap_!.#!#+#,#%3(2!.-! +&23-<!8(!'#23-%3#!.#23#!5-)93:+(>! ;-'#,(2!(!swap 
24 PESQUISA E ORDENAÇÃO DE DADOS
usando o procedimento troca<!122&,>!-!5?-,-.-!troca(L[i], L[j]) serve para 
3'(5-'!(2!5(%3#W.(!.-2!)(2&/P#2!&!#!c!.(!B#3('!e<
`!;T5&+!)#'5#*#'!F:#!-(!$!%-+!.-!)'&,#&'-!&3#'-/0(!.(!+-/(!,-&2!#63#'%(!
.(!1+7('&3,(!C(+?->!(!,-&('!#+#,#%3(!.-!+&23-!#23-'T!%-!W+3&,-!)(2&/0(!.(!
B#3('<!E#%.(!-22&,>!%-! &3#'-/0(!2#7:&%3#!%0(!)'#5&2-,(2!,-&2!%(2!)'#(Z
5:)-'!5(,!-!W+3&,-!)(2&/0(!.(!B#3('<!1(!$!%-+!.-!2#7:%.-!&3#'-/0(>!(2!.(&2!
,-&('#2!B-+('#2!.-!+&23-!#23-'0(!%-2!.:-2!W+3&,-2!)(2&/P#2!.(!B#3('!e>!#,!
('.#,!5'#25#%3#<!80(!)'#5&2-,(2!#%30(!%(2!)'#(5:)-'!5(,!-2!.:-2!W+3&,-2!
posições do vetor. 
"#!;-3(>!%(!1+7('&3,(!C(+?-!4!BT+&.(!(!2#7:&%3#!&%B-'&-%3#\!-(!$!%-+!.-!
&3#'-/0(!J!.(!+-/(!,-&2!#63#'%(>!(2!J!,-&('#2!B-+('#2!.-!+&23-!#23-'0(!%-2!J!W+Z
timas posições do vetor, em ordem crescente. A corretude do algoritmo decorre 
.#22#!&%B-'&-%3#<!1+4,!.&22(>!(!&%B-'&-%3#!#6)+&5-!)('F:#!%(!+-/(!,-&2!&%3#'%(!
(!5(%3-.('!c!2A!)'#5&2-!B-'&-'!.#!b!])'&,#&'-!)(2&/0(!.(!B#3('_!-34!%!d!V!d!&<
M+-'-,#%3#>!-! &%23':/0(!5'93&5-!.(!1+7('&3,(!C(+?-!4!-!5(,)-'-/0(!
]2#_<!=,!5-.-!&3#'-/0(!.(!+-/(!,-&2!&%3#'%(!4!;#&3-!:,-!5(,)-'-/0(<!M(,(!
-!F:-%3&.-.#!.#!&3#'-/P#2!.(!+-/(!&%3#'%(!.&,&%:&!f!,#.&.-!F:#!&!-:,#%3->!
(!%W,#'(!.#!5(,)-'-/P#2!'#-+&G-.-2!)#+(!-+7('&3,(!4\
i M(,)-'-/P#2
0 n – 1
1 %!d!O
... ...
n – 1 1
Total (nO!Z!%_aO
122&,>!-!5(,)+#6&.-.#!3#,)('-+!.(!1+7('&3,(!C(+?-!)#'3#%5#!-! (nO_<!
1+4,!.(2!)-'g,#3'(2!.#!#%3'-.-!]e!#!%_>!(!-+7('&3,(!:3&+&G-!-)#%-2!3'@2!B-Z
'&TB#&2!#25-+-'#2!]&>!c!#!-:6_<!"#22-!;(',->!-!F:-%3&.-.#!#63'-!.#!,#,A'&-!
:3&+&G-.-!)#+(!-+7('&3,(!4!5(%23-%3#<!E#%.(!-22&,>!2:-!5(,)+#6&.-.#!#2)-Z
cial pertence a O]V_<![2!,43(.(2!.#!('.#%-/0(!5:c-!5(,)+#6&.-.#!#2)-5&-+!
pertence a O]V_!20(!5?-,-.(2!,43(.(2!.#!('.#%-/0(!in situ. Esse é o caso 
.(!H43(.(!C(+?-<!
Outro aspecto importante dos métodos de ordenação é a estabilidade. 
"&G#,(2!F:#!:,!,43(.(!.#!('.#%-/0(!4!estável se ele preserva a ordem 
'#+-3&B-!#6&23#%3#!#%3'#!(2!#+#,#%3(2!'#)#3&.(2!.-!+&23-<!L('!#6#,)+(>!2#!-!
('.#%-/0(!.-!+&23-!]R>!h>!i>!7>!O_!'#2:+3-!#,!]O>!R>!i>!h>!7_>!-!('.#%-/0(!;(&!#2Z
3TB#+<![*2#'B#!F:#!(!2#3#!2:*+&%?-.(!#23-B-!f!.&'#&3-!.(!(:3'(!2#3#!#!-(!$!%-+!
.-!('.#%-/0(!#+#!5(%3&%:(:!f!.&'#&3-<!E#!3(.-2!-2!('.#%-/P#2!)'(.:G&.-2!
)('!:,!,43(.(!.#!('.#%-/0(!20(!#23TB#&2>!.&G#,(2!F:#!(!,43(.(!4!#23TB#+<!
[*2#'B#!F:#!%(!1+7('&3,(!C(+?->!F:-%.(!5(,)-'-,(2!.(&2!#+#,#%3(2!
.-!+&23->!2(,#%3#!;-G#,(2!(!swap!2#!(!-%3#5#22('!;('!,#%('!.(!F:#!(!2:5#2Z
2('>!)(&2!3&B#,(2!(!5:&.-.(!.#!:3&+&G-'!:,-!.#2&7:-+.-.#!#23'&3-!%-!5(,)-Z
'-/0(<!M(,(!5(%2#F:@%5&->!(!1+7('&3,(!C(+?-!4!#23TB#+<!
1!2#7:&'!#6&*&,(2!(!5(%3#W.(!.#!:,!B#3('!-)A2!5-.-!&3#'-/0(!.(!+-/(!
,-&2!#63#'%(!.(!1+7('&3,(!C(+?-<
1!+#3'-!7'#7-!jkj!4!:2-.-!
para denotar a ordem de 
5(,)+#6&.-.#!,#.&-!#!j[j
para o pior caso.
In situ: =6)'#220(!+-3&%->!
:2-.-! #,! BT'&(2! 5(%3#6Z
3(2>! F:#! 2&7%&$!5-! X%(! +:Z
7-'Y<
25PESQUISA E ORDENAÇÃO DE DADOS
0 1 O Q R 5
e&23-!('&7&%-+ U R 5 10 5 8
1ª iteração R 5 U 5 8 10
Ol!&3#'-/0( R 5 5 8 U 10
Ql!&3#'-/0( R 5 5 8 U 10
Rl!&3#'-/0( R 5 5 8 U 10
5ª iteração R 5 5 8 U 10
Figura 2.1: Ordenação com o Algoritmo Bolha
8#23#!#6#,)+(!)#'5#*#,(2!F:#!%(!$%-+!.-!2#7:%.-! &3#'-/0(!-! +&23-!
cT!#23-B-!('.#%-.-<!8-!3#'5#&'-!&3#'-/0(!%0(!?(:B#!%#%?:,-!-+3#'-/0(!%-!
+&23-<!=22-!;-3(!%(2!)#',&3&'&-!5(%5+:&'!F:#!-!+&23-!cT!#23-B-!#,!('.#,>!.#!
,(.(!F:#!-2!.:-2!W+3&,-2!&3#'-/P#2!;('-,!&%W3#&2<!
L(.#,(2! &%3'(.:G&'! :,-!)#F:#%-!,(.&$5-/0(!%(!H43(.(!C(+?-!.#!
,(.(! -! 3('%TZ+(! :,! )(:5(!,-&2! X#2)#'3(Y! #! #B&3-'! &3#'-/P#2! &%W3#&2<! m-+!
,(.&$5-/0(!5(%2&23#!#,!:2-'!:,-!B-'&TB#+!] !"_!)-'-!2&%-+&G-'!2#!;(&!'#-+&-
G-.-!-+7:,-!3'(5-!.#!#+#,#%3(2!%:,-!&3#'-/0(!.(!,43(.(<!M-2(!%#%?:,-!
3'(5-!3#%?-!2&.(!'#-+&G-.->!-!+&23-!cT!#23-'T!#,!('.#,!#>!)('3-%3(>!(!,43(.(!
.#B#!)-'-'<!8(!#6#,)+(!-%3#'&('>!-)A2!-!3#'5#&'-!&3#'-/0(!-!('.#%-/0(!2#'&-!
$%-+&G-.-<
=22-!B-'&-%3#!.(!C(+?-!4!5(%?#5&.-!5(,(!Bolha com Flag e seu pseu-
.(5A.&7(!4!;('%#5&.(!-!2#7:&'<
ALGORITMO BOLHA_COM_FLAG 
 ENTRADA: UM VETOR L COM N POSIÇÕES 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 i = 0 
 FAÇA 
 FLAG = FALSO 
 PARA j = 0 até n – 1 - i 
 SE L[j] > L[j+1] 
 TROCA(L[J], L[J+1]) 
 FLAG = VERDADEIRO 
 i = i + 1 
 ENQUANTO FLAG = VERDADEIRO
FIM {BOLHA_COM_FLAG}
Algoritmo 2.2: Bolha com Flag
=%F:-%3(!F:#!(!3#,)(!'#F:#'&.(!)#+(!C(+?-!4!2#,)'#!F:-.'T3&5(!#,!
'#+-/0(!-(!3-,-%?(!.-!+&23->!(!5(,)('3-,#%3(!.(!C(+?-!5(,!n+-7!4!2#%29B#+!
-(!3&)(!.#!+&23-!;('%#5&.-!5(,(!#%3'-.-<!8(!,#+?('!5-2(>!F:#!(5(''#!F:-%-
.(!-!+&23-!;('%#5&.-!cT!#23-!('.#%-.->!(!1+7('&3,(!C(+?-o5(,on+-7!'#F:#'!
tempo ]%_!)(&2!-!5(,)-'-/0(!2#'T!2#,)'#! ;-+2-!#!-!B-'&TB#+!p-7! c-,-&2!
'#5#*#'T!(!B-+('!B#'.-.#&'(<!"#22-!;(',->!-)A2!-!)'&,#&'-!&3#'-/0(!.(!+-/(!
#63#'%(!(!-+7('&3,(!2#'T!$%-+&G-.(<!
E:)(%?-!-7('-!F:#!(!,#%('!#+#,#%3(!#23T!&%&5&-+,#%3#!%-!W+3&,-!)(-
2&/0(!.-!+&23-<![*2#'B#!F:#!-!5-.-!&3#'-/0(!.(!+-/(!#63#'%(!(!,#%('!#+#,#%3(!
2#'T!,(B&.(!-)#%-2!:,-!)(2&/0(!)-'-!-!#2F:#'.-<!!E#'0(!%#5#22T'&-2!%!d!V!
&3#'-/P#2!)-'-!F:#!(!,#%('!#+#,#%3(!-+5-%5#!-!)'&,#&'-!)(2&/0(!.-!+&23-<!
8#22#! 5-2(>! (! 5(,)('3-,#%3(! .(! 1+7('&3,(!C(+?-o5(,on+-7! 2#'T! &.@%3&-
5(!-(!.(!1+7('&3,(!C(+?-<!M(%5+:9,(2!F:#!%(!)&('!5-2(!(!C(+?-!5(,!n+-7!
'#F:#'!3#,)(! (nO_<!n&%-+,#%3#>!4!)(229B#+!,(23'-'!F:#!(!.#2#,)#%?(!.(!
C(+?-!5(,!n+-7!%(!5-2(!,4.&(!3-,*4,!)#'3#%5#!-! (nO_<
26 PESQUISA E ORDENAÇÃO DE DADOS
4. Inserção
[!H43(.(!D%2#'/0(>!3-,*4,!5(%?#5&.(!5(,(!D%2#'/0(!"&'#3->!4!*-2-
3-%3#!2&,)+#2!#!-)'#2#%3-!:,!.#2#,)#%?(!2&7%&$5-3&B-,#%3#!,#+?('!F:#!
(!H43(.(!C(+?->!#,!3#',(2!-*2(+:3(2<!1+4,!.&22(>!5(,(!B#'#,(2!%(!$%-+!
.#22-!2#/0(>!#+#!4!#63'#,-,#%3#!#$5&#%3#!)-'-!+&23-2!F:#!cT!#23#c-,!2:*2-
tancialmente ordenadas.
8#22#!,43(.(!5(%2&.#'-,(2!F:#!-!+&23-!#23T!.&B&.&.-!#,!)-'3#!#2F:#'-
.->!cT!('.#%-.->!#!)-'3#!.&'#&3->!#,!)(229B#+!.#2('.#,<!D%&5&-+,#%3#>!-!)-'3#!
#2F:#'.-!5(%34,!-)#%-2!(!)'&,#&'(!#+#,#%3(!.-!+&23-<!M-.-!&3#'-/0(!5(%2&2-
3#!#,!&%2#'&'!(!)'&,#&'(!#+#,#%3(!.-!)-'3#!.&'#&3-!])&Bq_!%-!)(2&/0(!-.#F:--
.-!.-!)-'3#!#2F:#'.->!.#!,(.(!F:#!-!)-'3#!#2F:#'.-!5(%3&%:#!('.#%-.-<!
`!;T5&+!)#'5#*#'!F:#!2#!-!+&23-!)(22:&!%!#+#,#%3(2>!-)A2!%!d!V!&%2#'/P#2!#+-!
#23-'T!('.#%-.-<
L-'-! &%2#'&'!(!)&Bq!)#'5(''#,(2!-!)-'3#!#2F:#'.->!.-!.&'#&3-!)-'-!-!
#2F:#'.->!.#2+(5-%.(!(2!#+#,#%3(2!#23'&3-,#%3#!,-&('#2!F:#!(!)&Bq!:,-!
)(2&/0(!)-'-!.&'#&3-<![!)&Bq!.#B#!2#'!5(+(5-.(!&,#.&-3-,#%3#!f!#2F:#'.-!.(!
W+3&,(!#+#,#%3(!,(B&.(<
ALGORITMO INSERÇÃO 
 ENTRADA: UM VETOR L COM N POSIÇÕES 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 PARA i = 1 até n - 1 
 PIVO = L[i] 
 j = i - 1 
 !"#$%"&' ( ) * + ,-./ 0 123' 
 L[j+1] = L[j] 
 j = j - 1 
 L[j+1] = PIVO
FIM {INSERÇÃO}
Algoritmo 2.3: Inserção
 !"#$%&!'"()*!+",-$"!(!''$",-)./!")"%0*1)"2!'.$(0/)"(!#!"$.1')/)"34"
$*14"!'/$.)/)+"()/)"0.*$'56!"7"2$01)"$#"1$#8!"(!.*1).1$+"8!0*"!"809:"7"#)0!'"
!-"0;-)%")"1!/!*"!*"$%$#$.1!*"/)"8)'1$"$*,-$'/)"$")"(!./056!"/!"%)5!"0.1$'-
.!".-.()"7"9$'/)/$0')<" $**$"()*!+")"(!#8%$=0/)/$"1$#8!')%"/!">%;!'01#!"
Inserção pertence a ?.@<"
 !"80!'"()*!+",-$"!(!''$",-)./!")"%0*1)"$*14"0.9$'*)#$.1$"!'/$.)/)+"
()/)"0.*$'56!"'$,-$'",-$"1!/!*"!*"$%$#$.1!*"/)"8)'1$"$*,-$'/)"*$3)#"#!-
90/!*"8)')")"/0'$01)+"8!0*"1!/!*"$%$*"*$'6!"#)0!'$*"/!",-$"!"809:<" $**$"()*!+"
)",-).10/)/$"1!1)%"/$"01$')5A$*"/!"%)5!"0.1$'.!"*$'4"?.B"C".@DB"$")"(!#8%$=0-
/)/$"1$#8!')%"/!">%;!'01#!"E.*$'56!"*$'4" (nB@<"
>"(!#8%$=0/)/$"1$#8!')%"/!">%;!'01#!"E.*$'56!".!"()*!"#7/0!"1)#F7#"
pertence a (nB@<"E**!"/$(!''$"/!"2)1!"/$",-$+"$#"#7/0)+"()/)"01$')56!"'$,-$'"
,-$"#$1)/$"/!*"$%$#$.1!*"/)"8)'1$"$*,-$'/)"*$3)#"#!90/!*"8)')")"/0'$01)<"
G"8!**H9$%"#!*1')'")0./)",-$"*$"1!/!*"!*"$%$#$.1!*"/)"%0*1)"$*16!"0.0-
(0)%#$.1$"I"/0*1J.(0)".!"#4=0#!"("?!./$"("7"-#)"(!.*1).1$@"/)"8!*056!"$#"
,-$"/$9$"K()'",-)./!")" %0*1)"$*109$'"!'/$.)/)+"!"L71!/!"E.*$'56!"'$,-$'"
tempo linear.
M">%;!'01#!"E.*$'56!"'$,-$'"!"-*!"/$")8$.)*"1'N*"9)'049$0*"$*()%)'$*<"
O$./!")**0#+"*-)"(!#8%$=0/)/$"$*8)(0)%"7"O?P@<"MF*$'9$",-$"-#"$%$#$.1!"
/)"8)'1$"$*,-$'/)"*!#$.1$"7"#!90/!"8)')")"/0'$01)"*$"$%$"2!'"$*1'01)#$.1$"
#)0!'"/!",-$"!"809:<"Q!'"(!.1)"/0**!+"!">%;!'01#!"E.*$'56!"7"$*149$%<"
27PESQUISA E ORDENAÇÃO DE DADOS
 )"K;-')")"*$;-0'"$=0F0#!*"!"(!.1$R/!"/$"-#"9$1!'")8S*"()/)"01$')-
56!"/!"%)5!"#)0*"$=1$'.!"/!">%;!'01#!"E.*$'56!<">"8)'1$"$*,-$'/)"/)"%0*1)"
aparece sombreada.
0 1 B T U 5
V0*1)"!'0;0.)% W U 5 10 5 8
1ª iteração U W 5 10 5 8
BX"01$')56! U 5 W 10 5 8
TX"01$')56! U 5 W 10 5 8
UX"01$')56! U 5 5 W 10 8
5ª iteração U 5 5 8 W 10
Figura 2.2: Ordenação com o Algoritmo Inserção
5. Seleção
M"L71!/!"O$%$56!"1$#"(!#!"8!.1!"2!'1$"!"2)1!"/$",-$"$%$"'$)%0Y)"8!--
cas operações de swap<"O$-"/$*$#8$.&!+"$#"1$'#!*")F*!%-1!*+"(!*1-#)"
*$'"*-8$'0!'")!"/!"L71!/!"Z!%&)+"#)*"0.2$'0!'")!"/!"L71!/!"E.*$'56!<"
>**0#"(!#!".!"L71!/!" E.*$'56!+".$**$"#71!/!"(!.*0/$')#!*",-$")"
%0*1)"$*14"/090/0/)"$#"8)'1$"$*,-$'/)+"34"!'/$.)/)+"$"8)'1$"/0'$01)+"$#"8!*-
*H9$%"/$*!'/$#<">%7#"/0**!+"!*"$%$#$.1!*"/)"8)'1$"$*,-$'/)"*6!"1!/!*"#$-
nores ou iguais aos elementos da parte direita.
[)/)"01$')56!"(!.*0*1$"$#"*$%$(0!.)'"!"#$.!'"$%$#$.1!"/)"8)'1$"/0-
'$01)"?809:@"$"1'!(4C%!"(!#"!"8'0#$0'!"$%$#$.1!"/)"8)'1$"/0'$01)<"[!#"0**!+")"
8)'1$"$*,-$'/)")-#$.1)+"8!0*"8)**)")"0.(%-0'"!"809:+"$")"8)'1$"/0'$01)"/0#0-
.-0<" !1$",-$"!"809:"7"#)0!'",-$"1!/!*"!*"/$#)0*"$%$#$.1!*"/)"8)'1$"$*,-$'-
/)+"8!'1).1!")"8)'1$"$*,-$'/)"(!.10.-)"!'/$.)/)<">%7#"/0**!+"!"809:"$')"!"
#$.!'"$%$#$.1!"/)"8)'1$"/0'$01)"$+"8!'1).1!+"(!.10.-)"*$./!"9$'/)/$",-$"
!*"$%$#$.1!*"/)"8)'1$"$*,-$'/)"*6!"1!/!*"#$.!'$*"!-"0;-)0*")!*"$%$#$.1!*"
/)"8)'1$"/0'$01)<"E.0(0)%#$.1$+")"8)'1$"$*,-$'/)"7"9)Y0)<"O$")"%0*1)"8!**-0"."
$%$#$.1!*+")8S*"."\"P"01$')5A$*"$%)"$*1)'4"!'/$.)/)<
ALGORITMO SELEÇÃO 
 ENTRADA: UM VETOR L COM N POSIÇÕES 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 PARA i = 0 ate n - 2 
 MIN = i 
 PARA j = i + 1 até n - 1 
 SE L[j] < L[MIN] 
 MIN= j 
 TROCA(L[i], L[MIN])
FIM {SELEÇÃO}
Algoritmo 2.4: Seleção
>").4%0*$"/!">%;!'01#!"O$%$56!"7"*$#$%&).1$"I").4%0*$"/!">%;!'01#!"
Z!%&)<"M*"/!0*")%;!'01#!*"*6!"(!.*101-H/!*"/$"/!0*" %)5!*"(!.1)/!*"$.()0-
=)/!*",-$"'$)%0Y)#")*"#$*#)*",-).10/)/$*"/$"01$')5A$*<"]$**)"2!'#)+"*$"
1!'.)"$90/$.1$",-$"!">%;!'01#!"O$%$56!"'$)%0Y)"?.B"C".@DB"(!#8)')5A$*"$"*-)"
(!#8%$=0/)/$"1$#8!')%"8$'1$.($")" (nB@<">**0#"(!#!".!"Z!%&)+".6!"2)Y"*$.-
10/!"2)%)'"$#"#$%&!'".$#"80!'"()*!<">#F!*"!*")%;!'01#!*"'$,-$'$#"1$#8!"
,-)/'410(!+",-)%,-$'",-$"*$3)")"%0*1)<"
M">%;!'01#!"O$%$56!".$($**01)"/$")8$.)*",-)1'!"9)'049$0*"$*()%)'$*"
8)')"2)Y$'"!"*$-"1')F)%&!"?-#)"9)'049$%")-=0%0)'"7"-*)/)".!"8'!($/0#$.1!"
1'!()@<"O$./!")**0#+")"(!#8%$=0/)/$"$*8)(0)%"/!"O$%$56!"7"O?P@<"
28 PESQUISA E ORDENAÇÃO DE DADOS
^=0F0#!*".)"_0;-')"B<T"!"(!.1$R/!"/$"-#"9$1!'")8S*"()/)"01$')56!"/!"
%)5!"#)0*"$=1$'.!"/!">%;!'01#!"O$%$56!<">"8)'1$"$*,-$'/)"/)"%0*1)")8)'$($"
*!#F'$)/)<"Q!'"$**$"$=$#8%!"8$'($F$#!*",-$"!"L71!/!"O$%$56!"7"não-estável. 
0 1 B T U 5
V0*1)"!'0;0.)% 10 U 5 T 10 B
1ª iteração B U 5 T 10 10
BX"01$')56! B T 5 U 10 10
TX"01$')56! B T U 5 10 10
UX"01$')56! B T U 5 10 10
5ª iteração B T U 5 10 10
Figura 2.3: Ordenação com o Algoritmo Seleção
6. Shellsort
M"L71!/!" O&$%%*!'1" 2!0" 8'!8!*1!" 8!'"]!.)%/" O&$%%" $#"PW`W" $" 7" -#"
$=$#8%!"/$"-#")%;!'01#!"24(0%"/$"/$*('$9$'"$" 0#8%$#$.1)'+"#)*"/02H(0%"/$"
).)%0*)'<"a#)" $=8%0()56!" 8'$(0*)" 8)')" *$-" *-'8'$$./$.1$" /$*$#8$.&!" 7"
-#"/!*"$.0;#)*",-$"/$*)K)#"!*"8$*,-0*)/!'$*"&4"/7()/)*<
Q)')"/$*('$9$'"!"O&$%%*!'1"(!#"#)0*"2)(0%0/)/$"7"(!.9$.0$.1$"/$K.0'"!"
termo h-lista<"])/)"-#)"%0*1)"V+"-#)"&CV0*1)"/$"V"7"-#)"*-F%0*1)"#)=0#)%"
/$"V".)",-)%"()/)"$%$#$.1!"$*14")"/0*1J.(0)"&"/$"*$-"*-($**!'<"Q!'"$=$#-
8%!+"8)')"&"b"T+")"%0*1)")"*$;-0'"(!.17#"1'N*"&C%0*1)*<">"8'0#$0')"&C%0*1)"7"
(!.*101-H/)"/!*"$%$#$.1!*".)*"8!*05A$*"c+"T"$"d"/!"9$1!'<">"*$;-./)"&C%0*1)"
(!.17#"!*"$%$#$.1!*".)*"8!*05A$*"P+"U"$"e<">"1$'($0')"&C%0*1)"7"(!.*101-H/)"
/!*"$%$#$.1!*".)*"8!*05A$*"B"$"`<
0 1 B T U 5 6 7
10 U 5 T 10 B 1 PB
 
Figura 2.4: Uma lista dividida em h-listas (h = 3)
 !"O&$%%*!'1+")"%0*1)"7"*-F/090/0/)"$#"&C%0*1)*+")*",-)0*"*6!"!'/$.)/)*"
(!#"-#"#71!/!"/$"!'/$.)56!",-)%,-$'<"^**$"8'!($/0#$.1!"7"'$8$10/!"8)')"
9)%!'$*"/$('$*($.1$*"/$"&+"*$./!",-$"!"R%10#!"9)%!'"/$"&"1$#",-$"*$'"P<">"
%0*1)"$*1)'4"$.16!"!'/$.)/)<"
MF*$'9$",-$"!"O&$%%*!'1"8$'#01$"/09$'*)*"0#8%$#$.1)5A$*"/02$'$.1$*<"
[)F$")!"8'!;')#)/!'"/$(0/0'",-)%"#71!/!"/$"!'/$.)56!"$%$"-*)'4"8)')"!'-
/$.)'")*"&C%0*1)*<"a#)"F!)"!856!"7"-10%0Y)'"!"#71!/!"E.*$'56!<
>%7#"/0**!+"!"8'!;')#)/!'"1)#F7#"1$'4"/$(0/0'",-)0*"9)%!'$*"/$"&"$%$"
-10%0Y)'4<"]!.)%/"O&$%%"*-;$'0-"-*)'"8!1N.(0)*"/$"B"(!#!"9)%!'$*"/$"&<"Q!'"
$=$#8%!+" 8)')" !'/$.)'"-#)" %0*1)"/$"Pcc" $%$#$.1!*+" *$'0)#"-10%0Y)/!*" !*"
.R#$'!*"dU+"TB+"Pd+"f+"U+"B"$"P"(!#!"9)%!'$*"/$"&<"
Q!*1$'0!'#$.1$+"!-1'!"8$*,-0*)/!'+"]!.)%/"g.-1&+"#!*1'!-",-$"!"/$-
*$#8$.&!"/!"O&$%%*!'1".6!"7"F!#"*$"!*"9)%!'$*",-$"&")**-#$")!"%!.;!"/)"
$=$(-56!"/!"#71!/!"*6!"#R%108%!*"-.*"/!*"!-1'!*<"^%$"$.16!"*-;$'0-"()%(--
%)'"!*"9)%!'$*"/$"&")1')97*"/)"*$;-0.1$"2S'#-%)"/$"'$(!''N.(0)h"&"b"T"i"&"j"P<" 
[!#!"!"R%10#!"9)%!'"/$"&"1$#",-$"*$'"P+"-*)./!"$**)"2S'#-%)+"!"9)%!'").-
1$'0!'"/$"&"*$'0)"U<">.1$*"/$"U+"!"9)%!'"/$"&"*$'0)"PT+"$")**0#"8!'"/0).1$<"
Q!'"$=$#8%!+"8)')"!'/$.)'"-#)"%0*1)"/$"Pcc"$%$#$.1!*+"*$'0)#"-10%0Y)/!*"
!*".R#$'!*"Uc+"PT+"U"$"P"(!#!"9)%!'$*"/$"&<"]!.)%/"g.-1&"#!*1'!-"$#80-
'0()#$.1$",-$"!"/$*$#8$.&!"/!"O&$%%*!'1"'09)%0Y)"(!#"!"/$*$#8$.&!"/!*"
29PESQUISA E ORDENAÇÃO DE DADOS
#$%&!'$*"#71!/!*"/$"!'/$.)56!")!"!'/$.)'"%0*1)*"/$"8$,-$.!"$"#7/0!"8!'1$"
,-)./!"7"-*)/)")"2S'#-%)"*-;$'0/)"8!'"$%e.
ALGORITMO SHELLSORT
 ENTRADA: UM VETOR L COM N POSIÇÕES
 SAÍDA: O VETOR L EM ORDEM CRESCENTE
 H = 1
 ENQUANTO H < n FAÇA H = 3 * H + 1
 FAÇA
 H = H / 3 // divisão inteira
 PARA i = H até n – 1 // Inserção adaptado para h-listas
 PIVO = L[i]
 j = i - H
 !"#$%"&' ( ) * + ,-(. / 012'
 L[j + H] = L[j]
 j= j - H
 L[j + H] = PIVO
 ENQUANTO H > 1
FIM {SHELLSORT}
Algoritmo 2.5: Shellsort
 !1$",-$"!*"9)%!'$*"/$"&"/$('$*($#"8')10()#$.1$".-#)"8'!;'$**6!"
;$!#71'0()" /$" ')Y6!" PDT<" E**!" 0#8%0()" ,-$" )" ,-).10/)/$" /$" 01$')5A$*" /!"
%)5!"#)0*"$=1$'.!"8$'1$.($")" ?%!;.@<" !"#$%&!'"()*!+",-$"!(!''$",-)./!"
)"%0*1)"2!'.$(0/)"34"$*14"!'/$.)/)+")"(!./056!"/!"%)5!"0.1$'.!".-.()"7"9$'C
/)/$0')<" $**$"()*!+"()/)"01$')56!"/!"%)5!"#)0*"$=1$'.!"7"2$01)"$#"1$#8!"
%0.$)'"$+"8!'1).1!+")"(!#8%$=0/)/$"1$#8!')%"/!">%;!'01#!"O&$%%*!'1"8$'1$.($"
a ?.%!;.@<" 6!"*$"(!.&$($")"$=)1)"(!#8%$=0/)/$"/!"O&$%%*!'1".!"80!'"()*!<"
O)F$C*$+".!"$.1).1!+",-$"1)%"(!#8%$=0/)/$"$*14"$.1'$" ?.%!;.@""$" (n1,5@<"
M"O&$%%*!'1"7"#)0*"-#"#71!/!"/$"!'/$.)56!"in situ, pois sua comple-
=0/)/$"$*8)(0)%"7"(!.*1).1$<"O!F'$")"$*1)F0%0/)/$+"!"$=$#8%!"/)"_0;-')"B<`"
/$0=)"(%)'!",-$")!"!'/$.)'")*"&C%0*1)*"!"O&$%%*!'1"8!/$" 0.9$'1$'")"!'/$#"
$=0*1$.1$"$.1'$"!*"$%$#$.1!*"'$8$10/!*+"#$*#!",-$"*$3)"-*)/!"-#"#71!/!"
/$" !'/$.)56!" $*149$%" ?(!#!" !" E.*$'56!@" 8)')" !'/$.)'" )*" &C%0*1)*<" [!.*$C
,-$.1$#$.1$+"!"O&$%%*!'1"7"não-estável.
0 1 B T U 5 6 7
1 U B T 10 5 10 PB
 
Figura 2.5: h-listas da Figura 2.4 em ordem crescente
7. Mergesort
^**$"#71!/!+"8'!8!*1!"8!'"k!&."l!." $-#).."$#"PWU`+"7"F)*$)/!"
.-#)"$*1')17;0)"/$"'$*!%-56!"/$"8'!F%$#)*"(!.&$(0/)"(!#!"divisão e con-
quista. Essa técnica consiste, basicamente, em decompor a instância a ser 
resolvida em instâncias menores do mesmo tipo de problema, resolver tais 
0.*1J.(0)*"?$#";$')%+"'$(-'*09)#$.1$@"$"8!'"K"#"-10%0Y)'")*"*!%-5A$*"8)'(0)0*"
para obter uma solução da instância original.
Naturalmente, nem todo problema pode ser resolvido através de divi-
*6!"$"(!.,-0*1)<"Q)')",-$"*$3)"9049$%")8%0()'"$**)"17(.0()")"-#"8'!F%$#)"$%$"
deve possuir duas propriedades estruturais. O problema deve ser decompo-
^#" BccP+" L)'(0." [0-C
')" #!*1'!-" ,-$" -10%0Y)'"
)" *$,-N.(0)"P+"U+"Pc+"BT+"
`e+"PTB+"TcP+"ecP"$"Pe`c""
(!#!"9)%!'$*"/$"&"8'!/-Y"
'$*-%1)/!*" )0./)" #$%&!C
'$*" ,-$" -10%0Y)'" )" 2S'#-C
%)" 8'!8!*1)" 8!'" g.-1&<"
>"*$,-N.(0)"/$"[0-')"7")"
#$%&!'" (!.&$(0/)" )1-)%C
mente.
30 PESQUISA E ORDENAÇÃO DE DADOS
nível+"!-"*$3)+"/$9$"*$'"8!**H9$%"/$(!#8!'",-)%,-$'"0.*1J.(0)".6!"1'090)%"/!"
problema em instâncias menores do mesmo tipo de problema. 
l)%$"*)%0$.1)'",-$")"17(.0()"/$"/090*6!"$"(!.,-0*1)"(!*1-#)")8'$*$.-
1)'"/$*$#8$.&!"#$%&!'",-)./!")*"0.*1J.(0)*"!F10/)*"(!#")"/$(!#8!*056!"
1N#")8'!=0#)/)#$.1$"!"#$*#!"1)#).&!<
Uma instância trivial"7"-#)"0.*1J.(0)",-$".6!"8!/$"*$'"/$(!#8!*1)+"
#)*"(-3)"*!%-56!"7"#-01!"*0#8%$*"/$"*$'"()%(-%)/)<"Q!'"$=$#8%!+"!'/$.)'"
-#)" %0*1)"(!.*101-H/)"/$")8$.)*"-#"$%$#$.1!"7"-#)" 0.*1J.(0)" 1'090)%"/!"
problema da ordenação.
>%7#"/0**!+"/$9$"*$'"*$#8'$"8!**H9$%"-10%0Y)'")*"*!%-5A$*"!F10/)*"(!#"
)"'$*!%-56!"/)*"0.*1J.(0)*"#$.!'$*"8)')"(&$;)'")"-#)"*!%-56!"/)"0.*1J.(0)"
!'0;0.)%<"[!#!"9$'$#!*"#)0*")/0).1$+"!"8'!F%$#)"/)"!'/$.)56!"1$#"$**)*"
duas propriedades estruturais e, portanto, pode ser resolvido por divisão e 
(!.,-0*1)<
No Mergesort dividimos a lista em duas metades. Essas metades são 
!'/$.)/)*"'$(-'*09)#$.1$"?-*)./!"!"8'S8'0!"L$';$*!'1@"$"/$8!0*"*6!"inter-
caladas<"^#F!')"*$3)"8!**H9$%"/$*('$9$'"!"L$';$*!'1"*$#"2)Y$'"-*!"/$"'$-
cursividade, a versão recursiva desse é algoritmo é elegante e sucinta, como 
vemos a seguir.
ALGORITMO MERGESORT 
 ENTRADA: UM VETOR L E AS POSIÇÕES INICIO E FIM 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE DA POSIÇÃO INICIO ATÉ
 A POSIÇÃO FIM 
 
 3! 454647 8 9: 
 :+47 ; <454647 = 9:>?@ ?? A4B4CD7 45E+4FG 
 SE inicio < meio 
 MERGESORT(L, inicio, meio) 
 3! :+47 = H 8 9: 
 I!JK!3'J&<,L :+47 = HL 9:> 
 I!JK!<,L 454647L :+47L 9:>
FIM {MERGESORT}
Algoritmo 2.6: Mergesort
MF*$'9$",-$")" 0.1$'()%)56!"/!" 0.1$'9)%!")" *$'"!'/$.)/!"7" 2$01)" (!#"
o Procedimento Merge descrito mais adiante. Tal procedimento é a parte 
principal do Mergesort e é nele onde os elementos são movimentados para 
)*"8!*05A$*")/$,-)/)*<"
 $**$"8'!($/0#$.1!"2)Y$#!*"-*!"/)*"9)'049$0*"0"$"3"8)')"8$'(!''$'")"
#$1)/$" $*,-$'/)" $" )"#$1)/$" /0'$01)+" '$*8$(109)#$.1$<" ^#" ()/)" 01$')56!"
(!#8)')#!*"!"$%$#$.1!".)"8!*056!"0"(!#"!"$%$#$.1!".)"8!*056!"3<"M"#$.!'"
/$%$*"7"(!80)/!"8)')"-#"9$1!'")-=0%0)'<"^**$"8'!($/0#$.1!"7"'$8$10/!")17"
,-$"-#)"/)*"/-)*"#$1)/$*"1$.&)"*0/!"1!1)%#$.1$"(!80)/)"8)')"!"9$1!'")--
=0%0)'<"O$")%;-.*"$%$#$.1!*"/)"#$1)/$"$*,-$'/)".6!"109$'$#"*0/!"(!80)/!*"
8)')"!"9$1!'")-=0%0)'+"$%$*"/$9$#"*$'"(!80)/!*"8)')"!"K.)%"/!"0.1$'9)%!<"_0-
.)%#$.1$+"(!80)#!*"!*"$%$#$.1!*"/!"9$1!'")-=0%0)'"/$"9!%1)"8)')"!"0.1$'9)%!<"
31PESQUISA E ORDENAÇÃO DE DADOS
PROCEDIMENTO MERGE 
 ENTRADA: UM VETOR L E AS POSIÇÕES INICIO, MEIO E FIM 
 (L TEM QUE ESTAR EM ORDEM CRESCENTE DA POSIÇÃO 
 INICIO ATÉ MEIO E DA POSIÇÃO MEIO + 1 ATÉ FIM) 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE DA POSIÇÃO INICIO ATÉ 
 A POSIÇÃO FIM 
 
i = inicio, j = meio + 1, k = 0 
!"#$%"&' 4 M :+47 + ( M 9: 
 3! ,-4. M ,-(. 
 AUX[k] = L[i], i = i + 1 
 SENAO 
 AUX[k] = L[j], j = j + 1 
 k = k + 1 
3! 4 M :+47 
 PARA j = meio até i(passo -1) 
 ,-9:N:+47=(. ; ,-(. 
PARA i=0 ate k-1 
 L[i+inicio] = AUX[i]
FIM {MERGE}
Algoritmo 2.7: Procedimento Merge
a#)").4%0*$"(-0/)/!*)"/$**$"8'!($/0#$.1!".!*" %$9)")"(!.(%-0'",-$"
$%$"'$,-$'"1$#8!"%0.$)'#$.1$"8'!8!'(0!.)%")!"1)#).&!"/!"0.1$'9)%!<"l)#!*"
(&)#)'"/$"."!"1)#).&!"/!"0.1$'9)%!+"!-"*$3)+"."b"K#"\"0.0(0!"j"P<"MF*$'9$"
,-$")"(!./056!"/!"8'0#$0'!"%)5!"*!#$.1$"7"9$'/)/$0')"*$"0"m"#$0!"$"3"m"K#<"
V!;!+"8)')",-$"!"%)5!"(!.10.-$"$"*$'"$=$(-1)/!"7"8'$(0*!"1$'#!*"0"j"3"m"#$0!"
j"K#<
MF*$'9$",-$"0.0(0)%#$.1$"0"j"3"b"0.0(0!"j"#$0!"j"P<"[!#!")"()/)"01$')56!"
/!"8'0#$0'!"%)5!"!-"0"!-"3"7"0.('$#$.1)/!+")8S*"."\"P"01$')5A$*"1$'$#!*h
0"j"3"b"0.0(0!"j"#$0!"j"P"j"."\"P"
0"j"3"b"0.0(0!"j"#$0!"j".
0"j"3"b"0.0(0!"j"#$0!"j"K#"\"0.0(0!"j"P"
0"j"3"b"#$0!"j"K#"j"P
]$**)"2!'#)+")8S*".!"#4=0#!"."\"P"01$')5A$*""")"(!./056!"/!"8'0#$0'!"
%)5!"*$'4"90!%)/)<"[%)')#$.1$+"!"*$;-./!"%)5!+"*$"$=$(-1)/!+"1$'4".!"#4-
=0#!".DB"01$')5A$*<" !1$",-$")"()/)"01$')56!"/!"8'0#$0'!"%)5!")"9)'049$%"n"
7"0.('$#$.1)/)<"]$**)"2!'#)+")",-).10/)/$"/$"01$')5A$*"/!"8'0#$0'!"%)5!"
*$'4"n<"[!#!"n"7".!"#4=0#!"."\"P"$"!"R%10#!"%)5!"1$'4"n"01$')5A$*+"(!.(%--
H#!*",-$"!"Q'!($/0#$.1!"L$';$"'$,-$'"1$#8!"%0.$)'<"MF*$'9$")0./)",-$"!"
Q'!($/0#$.1!"L$';$"2)Y"-*!"/!"9$1!'">ao"$+"8!'1).1!+"'$,-$'"$*8)5!"%0.$)'<
>%7#"/0**!+".!1$",-$".)"(!#8)')56!"(!.10/)".!"8'0#$0'!"%)5!+"*$"Vp0q"
$"Vp3q"2!'$#"0;-)0*+"7"(!80)/!"Vp0q"8)')"!"9$1!'")-=0%0)'"$"0**!")"8'$*$'9)")"
ordem relativa entre os elementos repetidos. Esse cuidado na implementa-
56!"2)Y"(!#",-$"!"Q'!($/0#$.1!"L$';$"2)5)"*$#8'$"0.1$'()%)5A$*"$*149$0*<"
[!#!"(!.*$,-N.(0)+"!"L$';$*!'1"1)#F7#"7"$*149$%<
>"K;-')")"*$;-0'"0%-*1')"!"2-.(0!.)#$.1!"/!"Q'!($/0#$.1!"L$';$<"MF-
*$'9$",-$"!"0.1$'9)%!"/$"V",-$"9)0"/)"8!*056!"E E[EM")17"L^EM"$"!"0.1$'9)%!"
,-$"9)0"/$"L^EM"j"P")17"_EL"34"$*16!"$#"!'/$#"('$*($.1$<
32 PESQUISA E ORDENAÇÃO DE DADOS
 10 11 12 13 14 15 16 17 
L ... 1 4 7 13 2 4 5 6 ... 
 INICIO MEIO FIM 
 0 1 2 3 4 5 6 
AUX 1 2 4 4 5 6 
 
 10 11 12 13 14 15 16 17 
L ... 1 2 4 4 5 6 7 13 ... 
 INICIO FIM 
Figura 2.6: Exemplo de intercalação
 !"!#!#$%&!'()"!#Mergesort foi descrito de maneira recursiva, pode-
"!*#+,-(%"./).#+,0.'#*1,#,/2%(*.#1)(%(0,/3!#+4'"1%,*#3.#'.-!''5/-(,6#7,',#
(**!8#9,"!*#3./!),'#:!'#;</=#!#).":!#'.>1.'(3!#:,',#!'3./,'#1"#(/).'9,%!#
3.#),",/?!#/6#@./3!#,**("#!#).":!#/.-.**2'(!#:,',#!'3./,'#1"#(/).'9,%!#
3.# ),",/?!# /AB# *.'2# ;</AB=6# !"!# !# 7'!-.3("./)!#C.'&.# '.>1.'# ).":!#
%(/.,'8#:!3."!*#*1:!'#>1.#.%.# '.>1.'# ).":!#-/# <!/3.#-#D#1",#-!/*),/).#
:!*()(9,=6#;."!*#./)E!#,#*.&1(/).#+4'"1%,#3.#'.-!''5/-(,#:,',#;F
;</=#G#B;</AB=#H#-/
;<I=#G#-
7!3."!*#'.*!%9.'#.**,#+4'"1%,#+,-(%"./).#1)(%(0,/3!#!#método da ite-
ração#*1:!/3!#/#G#Bk. A partir da recorrência original, podemos obter as 
*.&1(/).*#'.-!''5/-(,*F
;</=#G#B;</AB=#H#-/
B;</AB=#G#J;</AJ=#H#-/
J;</AJ=#G#K;</AK=#H#-/
...
Bk-1;</ABk-1=#G#Bk;</ABk=#H#-/
Bk;</=#G#Bkc
@!",/3!# ),(*# +4'"1%,*#-?.&,"!*#,#;</=#G#-/L#H#Bk-6#M."N'.O*.#3.#
>1.#*1:!"!*#/#G#Bk8#%!&!8#L#G#%!&
B
/6#@./3!#,**("8#;</=#G#-/%!&
B
/#H#-/6# !/O
-%1P"!*#>1.#,#-!":%.Q(3,3.# ).":!',%#3!#$%&!'()"!#C.'&.*!')#:.')./-.#,#
 </%!&/=6
R,"!*#,&!',#3./!),'#:!'#S</=#!#.*:,T!#.Q)',#3.#"."4'(,#'.>1.'(3!#
:,',#!'3./,'#1"#(/).'9,%!#3.#),",/?!#/6# !"!#!#7'!-.3("./)!#C.'&.#'.O
>1.'#.*:,T!# %(/.,'#.#,#"."4'(,#1)(%(0,3,#/1",#-?,",3,#'.-1'*(9,#:!3.#
Esse método é descrito e 
.Q.":%(U#-,3!#/!#.Q-.%./O
te livro Algoritmos – Teo-
'(,# .# 7'2)(-,8# 3.# !'"./#
et al.
33PESQUISA E ORDENAÇÃO DE DADOS
*.'#'.,:'!9.(),3,#/,#-?,",3,#'.-1'*(9,#*.&1(/).8#)."!*#./)E!#,#*.&1(/).#
+4'"1%,#3.#'.-!''5/-(,#:,',#SF
S</=#G#",Q<S</AB=8#-/=
S<I=#G#-
V!9,"./).#:!3."!*#'.*!%9.'#.**,#+4'"1%,#1)(%(0,/3!#!#"D)!3!#3,#().-
',TE!8#!N)./3!#S</=#G#-/6# !/-%1P"!*#>1.#,#-!":%.Q(3,3.#.*:,-(,%#3!#$%&!-
ritmo Mergesort pertence a </=6#W(+.'./).#3.#)!3!*#!*#"D)!3!*#>1.#.*)13,-
mos anteriormente, o Mergesort não é in situ.
8. Quicksort
S**.#"D)!3!8#3.*./9!%9(3!#."#IXYZ#:!'# 6#$6#[6#\!,'.#.#:1N%(-,3!#
."#IXYB8#D#),%9.0#!#",(*#1)(%(0,3!#3.#)!3!*#!*#"D)!3!*#3.#!'3./,TE!6#]**!#
!-!''.#:!'>1.#>1,*.#*.":'.#!#^1(-L*!')#D#*(&/(U-,)(9,"./).#",(*#'2:(3!#
3!#>1.#)!3!*#!*#3.",(*#"D)!3!*#3.#!'3./,TE!#N,*.,3!*#."#-!":,',TE!6#
$%D"#3(**!8#*1,*#-,',-).'P*)(-,*#+,0."#-!"#>1.#.%.8#,**("#-!"!#!#C.'&.-
*!')8#:!**,#*.'#+,-(%"./).#:,',%.%(0,3!6#S%.#),"ND"#:!3.#*.'#,3,:),3!#:,',#
'.,%(0,'#!'3./,TE!#.Q).'/,#<^1(-L*!')#SQ).'/!=6
_"#,*:.-)!#>1.#)!'/,#!#^1(-L*!')#"1()!#(/).'.**,/).#*!N#!#:!/)!#3.#
9(*)!#).4'(-!#D#!#+,)!#3.#>1.8#."N!',#."#&.',%#.%.#*.`,#.Q)'.","./).#'2:(3!8#
.Q(*)."#-,*!*#<"1()!#','!*8#D#9.'3,3.=#."#>1.#*.1#3.*.":./?!#D#N."#'1("8#
-?.&,/3!#,#*.'#:(!'#3!#>1.#!#3.#"D)!3!*#3.#!'3./,TE!#-!/*(3.',3!*#(/+.'(!-
'.*#-!"!#!*#"D)!3!*#a!%?,8#]/*.'TE!#.#@.%.TE!6
Assim como o Mergesort, o Quicksort também é baseado na estratégia 
3.#3(9(*E!#.#-!/>1(*),6#b-!''.#>1.8#./>1,/)!#/!#C.'&.*!')#,#+,*.#3.#3(9(*E!#
D#)'(9(,%#.#,#+,*.#3.#-!/>1(*),#D#)',N,%?!*,8#/!#^1(-L*!')8#-!"#9.'."!*#,#
*.&1('8#,-!/).-.#!#-!/)'2'(!8#,#+,*.#3.#3(9(*E!#D#)',N,%?!*,#.#,#+,*.#3.#-!/-
>1(*),#D#)'(9(,%6
V.**.#"D)!3!8#,#%(*),#D#3(9(3(3,#."#:,').#.*>1.'3,#.#:,').#3('.(),8#*./-
3!#>1.#!*#.%."./)!*#3,#:,').#.*>1.'3,#*E!#)!3!*#"./!'.*#>1.#!*#.%."./)!*#
3,#:,').#3('.(),6#S**,#+,*.#3!#"D)!3!#D#-?,",3,#3.#partição. 
Em seguida, as duas partes são ordenadas recursivamente (usando o 
:'4:'(!#^1(-L*!')=6#$#%(*),#.*),'2#./)E!#!'3./,3,6
_",#.*)',)D&(,#:,',#+,0.'#,#:,')(TE!#D#.*-!%?.'#1"#9,%!'#-!"!#pivô e 
./)E!#-!%!-,'#/,#:,').#.*>1.'3,#!*#.%."./)!*#"./!'.*#!1#(&1,(*#,!#:(9c#.#
/,#:,').#3('.(),#!*#.%."./)!*#",(!'.*#>1.#!#:(9c6#
S"N!',#.Q(*),"#3(9.'*,*#",/.(',*#3.#.*-!%?.'#!#:(9c8#,%&1",*#3,*#
>1,(*#*.'E!#,:'.*./),3,*#/.**,#*.TE!8#,3!),'."!*#,#:'(/-P:(!#1",#.*)',-
)D&(,#.Q)'.","./).#*(":%.*8#",*#>1.#-!*)1",#,:'.*./),'#'.*1%),3!*#:'2-
ticos muito bons. Além disso, tal estratégia facilita perceber os casos em 
>1.#!#:'!-.3("./)!#3.#:,')(TE!#/E!#3(9(3.#,#%(*),#3.#",/.(',#.>1(%(N',3,6#
W.**,#+!'",8#)!'/,O*.#",(*#+2-(%#-,',-).'(0,'#.#,/,%(*,'#!#:(!'#-,*!#3!#CD-
todo Quicksort.
_)(%(0,'."!*# -!"!#:(9c# !# :'(".('!# .%."./)!#3,# %(*),6#V.**.# -,*!8# !#
:(9c#3.9.#*.'#-!%!-,3!#./)'.#,*#31,*#:,').*6#b#7'!-.3("./)!#7,')(TE!8#>1.#
implementa tal estratégia, é descrito a seguir.
34 PESQUISA E ORDENAÇÃO DE DADOS
... !"#$ PIVÔ > PIVÔ ...
INICIO j FIM
Figura 2.7: Partição
PROCEDIMENTO PARTIÇÃO 
 ENTRADA: UM VETOR L E AS POSIÇÕES INICIO E FIM 
 !"#$"%&' ()* +,- ./010203455./&674 8 ./&4 - 
 L[j+1]..L[FIM] > L[j] 
 // j é a posição onde será colocado o pivô, como 
%%%%%&&%'()*+,-./%0-%12),-%-3-'4/
 PIVO = L[INICIO], i = INICIO + 1, j = FIM 
%%567896:;%'% %< 
%%%%567896:;%'% %<%=%>?'@% %!"#; 
 i = i + 1 
 ENQUANTO L[j] > PIVO 
 j = j - 1 
%%%%A5%'% %< 
 TROCA(L[i],L[j]) 
 i = i + 1, j = j - 1 
 TROCA(L[INICIO], L[j]) 
 DEVOLVA j
FIM {PARTIÇÃO}
Algoritmo 2.8: Procedimento Partição
V!#7'!-.3("./)!#7,')(TE!#,#9,'(29.%# (#,9,/T,#,)D#./-!/)','#1"#.%.-
"./)!#",(!'#3!#>1.#!#:(9c#.#,#9,'(29.%#`#'.-1,#,)D#./-!/)','#1"#.%."./)!#
"./!'#!1#(&1,%#,!#:(9c6#d#+.(),#./)E!#,#)'!-,#3!#.%."./)!#>1.#.*)2#/,#:!-
*(TE!#(#-!"#!#.%."./)!#>1.#.*)2#/,#:!*(TE!#`6#S**.#:'!-.**!#D#'.:.)(3!#,)D#
).'"!*#(#e#`6#7,',#U/,%(0,'8#!#:(9c#D#-!%!-,3!#./)'.#,*#31,*#:,').*#+,0./3!#
)'!-,<Mf]V] ]bg8#Mf`g=6#$#:!*(TE!#`#D#3.9!%9(3,#,!#-?,",3!'#3!#:'!-.3("./)!6
$#'.&(E!#-'P)(-,#3!#7'!-.3("./)!#7,')(TE!#D#-!/*)()1P3,#3!*#3!(*#%,T!*#
",(*#(/).'/!*6#@.`,#/#!#),",/?!#3!#(/).'9,%!6#bN*.'9.#>1.#(/(-(,%"./).#`#
h#(#G#/#h#B6#V!).#,(/3,#>1.#,#-,3,#().',TE!#3.#1"#3!*#%,T!*#(/).'/!*#!1#(#D#
(/-'."./),3!#!1#`#D#3.-'."./),3!6#]**!#*(&/(U-,#>1.#,#-,3,#().',TE!#3.#1"#
3.**.*#%,T!*#,#.Q:'.**E!#`#h#(#D#3.-'."./),3,#3.#1",#1/(3,3.6# !/*.>1./-
)."./).8#,:4*#/!#"2Q("!#/#h#I#().',Ti.*#3.**.*#%,T!*#).'."!*#` #h#(#G#OI#!#>1.#
(":%(-,#>1.#`#*.'2#"./!'#3!#>1.#(6#b#%,T!#*.'2#./)E!#U/,%(0,3!6# !/-%1P"!*#
>1.#!#7'!-.3("./)!#7,')(TE!#'.>1.'#).":!#%(/.,'6# %,',"./).8#.**.#:'!-.-
3("./)!#)."#-!":%.Q(3,3.#.*:,-(,%#-!/*),/).6
V,#U&1',#B6K#D#(%1*)',3,#,#:,')(TE!#3.#1",#%(*),6#bN*.'9.#>1.#/.**.#
.Q.":%!#>1.#,#:,')(TE!#U-!1#.>1(%(N',3,8#:!(*#>1,)'!#.%."./)!*#U-,',"#j#
.*>1.'3,#3!#:(9c#.#)'5*#.%."./)!*#U-,',"#j#3('.(),#3!#:(9c6
 10 11 12 13 14 15 16 17 
L ... 5 8 4 2 7 3 9 4 ... 
 INICIO FIM 
1ª troca 
2ª troca 
3ª troca 
35PESQUISA E ORDENAÇÃO DE DADOS
 10 11 12 13 14 15 16 17 
L ... 3 4 4 2 5 7 9 8 ... 
 j 
Figura 2.8: Exemplo de partição equilibrada
 !""!#!$!%&'()#&!*+!,!%("#-.!#(#/*(+!01%!23(#/4*3156(#&(0!#127!*-
3!*#4#(*0!%#!$1"3!23!#!23*!#("#!'!%!23("#*!&!310("8#9(2"!-.!23!%!23!)#(#
Quicksort é não-estável.
:!#(#!'!%!23(#!"+(';10(#+(%(#&17<#=(*#(#%41(*#!'!%!23(#0(#123!*74'()#
3!*!%("#.%4#&4*3156(#0!"!-.1'1,*404)#+(%(# 1'."3*40(#24#>?.*4#4#"!?.1*8#
 (3!#-.!#4&!24"#.%4#3*(+4#"!*@#!$!+.34048
 10 11 12 13 14 15 16 17 
L ... 8 7 6 5 4 3 2 1 ... 
 INICIO FIM 
 10 11 12 13 14 15 16 17 
L ... 1 7 6 5 4 3 2 8 ... 
 j 
Figura 2.9: Exemplo de partição desequilibrada
A# =@+1'#&!*+!,!*#-.!#"!#(#%!2(*#!'!%!23(#0(# 123!*74'(# =(*#!"+(';10(#
+(%(#&17<#2!2;.%4#3*(+4#"!*@#!=!3.4048#B!*!%("#(.3*4#&4*3156(#0!"!-.1-
'1,*4048#C%#4%,("#("#+4"("#.%4#04"#%!340!"#&*(0.D104"#+(%#4#&4*3156(#
>+4*@#74D14#!#4#(.3*4# 3!*@# 3(0("#("#!'!%!23("#0(# 123!*74'(#!$+!3(#(#&17<8#
C""!# =43(# 3!*@#.%#1%&4+3(# 1%&(*3423!#"(,*!#(#0!"!%&!2;(#0(#E.1+F"(*3#
como veremos mais adiante.
G!"+*!7!%("#4#"!?.1*#.%4#7!*"6(#*!+.*"174#0(#E.1+F"(*38
ALGORITMO QUICKSORT 
 ENTRADA: UM VETOR L E AS POSIÇÕES INICIO E FIM 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE DA POSIÇÃO INICIO ATÉ
 A POSIÇÃO FIM 
 
 SE INICIO < FIM 
 j = PARTICAO(L, INICIO, FIM) 
 SE INICIO < j - 1 
 QUICKSORT(L, INICIO, j - 1) 
 SE j + 1 < FIM 
 QUICKSORT(L, j + 1, FIM)
FIM {QUICKSORT}
Algoritmo 2.9: Quicksort
/4*4#424'1"4*#(#H'?(*13%(#E.1+F"(*3#74%("#0!2(34*#&(*#BI2J#(#3!%&(#
*!-.!*10(#&4*4#(*0!24*#.%#123!*74'(#0!#34%42;(#2#!#&(*#CI2J#(#!"&45(#!$-
3*4#*!-.!*10(#&4*4#(*0!24*#.%#123!*74'(#0!#34%42;(#28# (#&1(*#+4"()#-.!#
(+(**!#-.420(#3(04"#4"#!"+(';4"#0(#&17<#*!+4!%#"!%&*!#"(,*!#.%#!'!%!2-
3(#!$3*!%(#I(#%41(*#(.#(#%!2(*J#0(#123!*74'()#4#+(%&'!$1040!#3!%&(*4'#0(#
E.1+F"(*3#K#0404#&(*L
36 PESQUISA E ORDENAÇÃO DE DADOS
BI2J#M#BI2#N#OJ#P#+2
BIOJ#M#+
C""4#=Q*%.'4#&(0!#"!*#=4+1'%!23!#*!"('7104#*!".'3420(#!%#BI2J#M#I2R#S#2JTR8#
H#+(%&'!$1040!#!"&4+14'#0(#E.1+F"(*3#2(#&1(*#+4"(#K#0404#&(*L
CI2J#M#CI2#N#OJ#P#+
CIOJ#M#+
U!"('7!20(#!""4#=Q*%.'4#(,3!%("#CI2J#M#+28#9(2+'.V%("#-.!#2(#&1(*#
+4"(#(#H'?(*13%(#E.1+F"(*3#*!-.!*#3!%&(# (nRJ#!#!"&45(# I2J8#/4*4#2(""4#
".*&*!"4)#!""4#+(%&'!$1040!#3!%&(*4'#K#36(#*.1%#-.423(#4"#0("#%K3(0("#
W(';4)#X2"!*56(#!#:!'!56(#!#!""4#+(%&'!$1040!#!"&4+14'#K#36(#*.1%#-.423(#
4#0(#Y!*?!"(*38#:(%!S"!#4#1""(#(#=43(#0!#-.!#(#E.1+F"(*3#K#26(S!"3@7!'#!#
!236(#+(2+'.V%("#-.!#2(#&1(*#+4"(#(#E.1+F"(*3#K#.%#0("#&1(*!"#%K3(0("#0!#
ordenação.
A#=@+1'#&!*+!,!*#-.!#+(%#(#+*13K*1(#0!#!"+(';4#0(#&17<#-.!#40(34%(")#
"!#4# '1"34#!"317!*# 127!*"4%!23!#(*0!2404)# 3(0("#("#&17<"#!"+(';10("#"!*6(#
!'!%!23("#!$3*!%("#0!#"!."#123!*74'("#!)#&(*3423()#*!+41*!%("#2(#&1(*#+4"(#
0(#E.1+F"(*38#/4*4#2(""4#".*&*!"4)#"!#4#'1"34#Z@#!"317!*#(*0!2404)#3(0("#("#
&17<"#!"+(';10("#34%,K%#"!*6(#!'!%!23("#!$3*!%("#0!#"!."#123!*74'("#!#2(S
74%!23!#*!+41*!%("#2(#&1(*#+4"(#0(#E.1+F"(*38#[!'1D%!23!)#4#(+(**\2+14#0(#
&1(*#+4"(#K#!$3*!%4%!23!#*4*48
 (#%!';(*#+4"()#-.!#(+(**!#-.420(#4"#!"+(';4"#0(#&17<#*!+4!%#"!%S
pre sobre a mediana#0(#123!*74'()#4#+(%&'!$1040!#3!%&(*4'#0(#E.1+F"(*3#K#
0404#&(*L
BI2J#M#RBI2TRJ#P#+2
BIOJ#M#+
U!"('7!%("#!""4#=Q*%.'4#4(#01"+.31*#(#Y!*?!"(*3#!#"4,!%("#-.!#BI2J#! 
 I2'(?2J8#H#+(%&'!$1040!#!"&4+14'#0(#E.1+F"(*3#K#0404#&(*L
CI2J#M#CI2TRJ#P#+
CIOJ#M#+
U!"('7!20(#!""4#=Q*%.'4#+(2+'.V%("#-.!#CI2J#! I'(?2J8#:!20(#4""1%)#
2(#%!';(*#+4"(#4#+(%&'!$1040!#3!%&(*4'#0(#E.1+F"(*3#&!*3!2+!#4# I2'(?2J#
!#4#+(%&'!$1040!#!"&4+14'#&!*3!2+!#4# I'(?2J8#C""4"#34%,K%#"6(#4"#+(%&'!S
$1040!"#0(#E.1+F"(*3#2(#+4"(#%K01(8
/(0!%("#.31'1D4*# !"3*43K?14"#%41"# !'4,(*404"#&4*4# !"+(';4#0(#&17<)#
+(%#(#(,Z!317(#0!#&*(0.D1*#&4*315]!"#%41"#!-.1'1,*404"8#C1"#4'?.%4"#10!14"L
 ! ^31'1D4*#4#%K014#4*13%K31+4#0(#123!*74'(8
 ! ^31'1D4*#4#%!01424#0(#123!*74'(8
 ! C"+(';!*#4'!43(*14%!23!#.%#!'!%!23(#0(#123!*74'(8
Nos dois primeiros casos precisaremos de tempo linear para esco-
';!*#(#pivô)#%4"#1""(#26(#4=!34*@#4#+(%&'!$1040!#3!%&(*4'#4""123Q31+4#04#
No livro Algoritmos – Teo-
*14#!#/*@31+4#K#0!"+*13(#.%#
método para calcular a 
mediana em tempo linear.
37PESQUISA E ORDENAÇÃO DE DADOS
&4*3156(#-.!#K#'12!4*8# (#!23423()#!%#3!*%("#4,"('.3(")#(#3!%&(#*!-.!*10(#
&!'4#&4*3156(#4.%!234*@8#H'K%#01""()#(#&17<#&(0!*@#26(#"!*#.%#!'!%!23(#
0(#123!*74'(#!#1""(#!$1?1*@#4'?.%4"#4'3!*45]!"#401+1(241"#0(#/*(+!01%!23(#
Partição.
 (#_'31%(#+4"(#3!%("#4#7!*"6(#+(2;!+104#+(%(#Quicksort probabilísti-
co8#H#&*12+1&4'#74234?!%#0!""4#7!*"6(#K#(#=43(#0!#3(*24*#1%&(""V7!'#?4*4231*#
-.!#(#E.1+F"(*3#741#*!-.!*!*#3!%&(#-.40*@31+(#&4*4#.%4#0!3!*%12404#'1"348#
9(%(#71%("#423!*1(*%!23!)#4(#!"+(';!*#0!3!*%121"31+4%!23!#(#&17<)#K#&(""V-
7!'#-.!#4'?.K%#01"&("3(#4#0!"%(*4'1D4*#(#E.1+F"(*3#+(2"3*.4#'1"34"#&4*4#4"#
-.41"#"!.#0!"!%&!2;(#"!Z4#-.40*@31+(8#X""(#26(#K#%41"#&(""V7!'#24#7!*"6(#
&*(,4,1'V"31+4#0(#4'?(*13%(8#
9. Heaps Binários
Um heap#K#.%4#+('!56(#0!#040("#&4*+14'%!23!#(*0!240("8# .%#;!4&#
crescente#K#7@'104#4#"!?.123!#&*(&*1!040!L#`(#&41#K#%!2(*#(.#1?.4'#4("#"!."#
>';("a8# .%#;!4&#decrescente)#3!%("#4#&*(&*1!040!#42@'(?4L#`(#&41#K#%41(*#
(.#1?.4'#4("#"!."#>';("a8#C$1"3!%#017!*"("#31&("#0!#;!4&"L#,12@*1(")#,12(-
%141")#0!#[1,(24++1#!3+8#H,(*04*!%("#4&!24"#;!4&"#,12@*1("8
^%#;!4&#,12@*1(#"!#+4*4+3!*1D4#&!'(#=43(#0!#-.!#+404#!'!%!23(#&("".1#
2(#%@$1%(#0(1"#>';("8#/(0!%("#1%&'!%!234*#;!4&"#,12@*1("#."420(#.%4#
@*7(*!#,12@*148#B4'#@*7(*!#3!*@#3(0("#("#2V7!1"#+(%&'!3(")#+(%#!$+!56(#0(#
_'31%(#2V7!')#-.!#&(0!#!"34*#12+(%&'!3(8#H'K%#01""()#("#2V7!1"#"6(#&*!!2+;1-
0("#04#!"-.!*04#&4*4#4#01*!1348
 
3 
5 3 
10 7 
Figura 2.10: Exemplo de heap binário crescente armazenado numa árvore
^%#;!4&#,12@*1(#34%,K%#&(0!#"!*#1%&'!%!2340(#43*47K"#0!#.%#7!3(*8#
 !""!#+4"()#("#>';("#04#&("156(#1#"6(#4"#&("15]!"#R#b#1#!#R#b#1#P#O#IH#&("156(#
D!*(#0(#7!3(*#26(#K#.31'1D404J8#G1"+.31*!%("#!%#0!34';!"#+(%(#=4D!*#12"!*-
56(#!#+(%(#*!%(7!*#(#%!2(*#!'!%!23(#0!#.%#;!4&#,12@*1(#+*!"+!23!#1%&'!-
mentado num vetor.
1 R c d 5 6
c 5 c 7 10
Figura 2.11: Exemplo de heap binário crescente armazenado num vetor
e,"!*7!#-.!#2.%#;!4&#,12@*1(#+*!"+!23!#1%&'!%!2340(#2.%4#@*7(*!)#
(#%!2(*#74'(*#!"34*@#"!%&*!#24#*41D#04#@*7(*!8#:!#(#;!4&#,12@*1(#+*!"+!2-
3!# =(*# 1%&'!%!2340(#2.%#7!3(*)#(#%!2(*#74'(*#!"34*@#"!%&*!#24#&*1%!1*4#
&("156(#0(#7!3(*8#G!""4#=(*%4)#!2+(23*4*#(#%!2(*#74'(*#+(2310(#2.%#;!4&#
,12@*1(#+*!"+!23!#K#.%4#(&!*456(#-.!#&(0!#"!*#=!134#!%#3!%&(#+(2"3423!8#
H24'(?4%!23!)#(#%41(*#!'!%!23(#2.%#;!4&#,12@*1(#0!+*!"+!23!#!"34*@#"!%-
&*!#2(#"!.#12V+1(8
/4*4#1%&'!%!234*#.%#;!4&#,12@*1(#."420(#.%#7!3(*)#&(0!%("#."4*#
.%4#!"3*.3.*4#+(%#("#"!?.123!"#+4%&("L
38 PESQUISA E ORDENAÇÃO DE DADOS
 ! 7!3(*L#4*%4D!24#("#040("
 ! 34%42;(L#1201+4#(#34%42;(#0(#7!3(*
 ! .'31%4L#1201+4#4#_'31%4#&("156(#."404#0(#7!3(*
/4*4# 12"!*1*#.%#74'(*#$#2.%#;!4&#,12@*1(#0!7!%("# 12"!*1S'(#4&Q"#(#
_'31%(#!'!%!23(#!#0!&(1"#+(%&4*4*#+(%#"!.#&41)#3*(+420(S("#0!#&("156(#"!#
;(.7!*#2!+!""1040!8#B4'#&*(+!""(#K#*!&!310(#43K#-.!#$#"!Z4#%41(*#(.#1?.4'#
4(#"!.#&41#(.#43K#$#4312?1*#4#&("156(#O#0(#7!3(*8#e#4'?(*13%(#4#"!?.1*#1%&'!S
%!234#4#10!14#0!"+*134#2!""!#&4*@?*4=(8
ALGORITMO INSERE_HBC
 ENTRADA: UM HEAP BINÁRIO CRESCENTE H E UM VALOR X
 SAÍDA: SE HOUVER ESPAÇO DISPONIVEL, INSERE X EM H; 
 CASO CONTRÁRIO, DEVOLVE UM ERRO.
SE H.ultima = H.tamanho //HEAP OVERFLOW
 devolva ERRO 
H.ultima = H.ultima + 1
i = H.ultima
ENQUANTO i > 1 e H.vetor[i/2] > x // DIVISÃO INTEIRA
 H.vetor[i] = H.vetor[i/2]
 i = i/2
H.vetor[i] = x
FIM {INSERE_HBC}
Algoritmo 2.10: Insere_HBC
9'4*4%!23!)#4#*!?16(#+*V31+4#0(#H'?(*13%(#X2"!*!fgW9#K#(#'45(8#G!""4#
=(*%4)#(#3!%&(#*!-.!*10(#&!'(#4'?(*13%(#K#0!3!*%1240(#&!'4#-.4231040!#0!#
13!*45]!"#0(#'45(8#:!Z4#2#M#g8.'31%48# (3!#-.!#121+14'%!23!#1#M#2#!)#&(*3423()#
i possui "log
R
n##P#O#,13"#"#$%#&!'()#*os8#H#+404#13!*456(#0(#'45()#4#74*1@7!'#1#
&!*0!#.%#,13#"1?21>#+4317()#&(1"#(#74'(*#0!#1#K#43.4'1D40(#=4D!20(S"!#1#M#1TR8#
H&Q"#"log
R
n##13!*45]!")#1#3!*@#4&!24"#.%#,13#"1?21>#+4317(8#:!20(#4""1%)#3!*!S
%("#1#h#O#!#(#'45(#"!*@#>#24'1D40(8#H""1%)#4#-.4231040!#%@$1%4#0!#13!*45]!"#
do laço é "log
R
n#8#9(2+'.V%("#-.!#4#+(%&'!$1040!#3!%&(*4'#0(#H'?(*13%(#X2S
"!*!fgW9#&!*3!2+!#4#OI'(?2J8#
H#>#?.*4#4#"!?.1*#1'."3*4#4#12"!*56(#0(#74'(*#d#2.%#;!4&#,12@*1(#+*!"S
+!23!8#e,"!*7!#-.!#(#74'(*#i#!#0!&(1"#(#74'(*#j#&*!+1"4%#"!*#%(710("#&4*4#
-.!#(#74'(*#d#&(""4#"!*#+('(+40(#24#&("156(#R#0(#7!3(*8# (3!#41204#-.!#4#
inserção pode inverter a ordem entre os elementos repetidos.
1 2 3 4 5 6 7 8 9 10
3 5 3 7 10 8 3 7
 !"#$"%&!'$("$)%'!*+,-
1 2 3 4 5 6 7 8 9 10
3 4 3 5 10 8 3 7 7
 
1ª movimentação 
novo valor 
2ª movimentação 
Figura 2.12: Exemplo de inserção num heap binário crescente
./0-*"$'!1"$#-''23!4$*!/-3!*$5/$!4!/!%&-$65"465!*$(-$7!"#8$3"/-'$
()'95&)*$"#!%"'$"$*!/-+,-$(-$/!%-*$!4!/!%&-:$;-/-$3)/-'$"%&!*)-*/!%&!8$
-$/!%-*$!4!/!%&-$!'&"*<$'!/#*!$%"$#*)/!)*"$#-')+,-$(-$7!"#:
 =!$ >4?@'!$ A97,-$(!$=BC$D$-$
/")-*$$)%&!)*-$65!$D$/!%-*$
-5$$)E5"4$"$=:
39PESQUISA E ORDENAÇÃO DE DADOS
F"*"$*!/-3!*$-$/!%-*$!4!/!%&-$(!$5/$7!"#$0)%<*)-$9*!'9!%&!$)/#4!-
/!%&"(-$%5/$3!&-*8$/-3!/-'$-$G4&)/-$3"4-*$9-%&)(-$%-$7!"#$>#)3HC$#"*"$"$
#-')+,-$I$(-$3!&-*:$./$'!E5)("8$9-/#"*"/-'$-$#)3H$9-/$'!5'$J47-'8$&*-9"%-
(-@-$9-/$-$/!%-*$(!$'!5'$J47-'$'!$7-53!*$%!9!'')("(!:$.''!$#*-9!()/!%&-$
D$*!#!&)(-$"&D$65!$-$#)3H$'!1"$/!%-*$-5$)E5"4$"-'$'!5'$J47-'$-5$"&D$-$#)3H$
"&)%E)*$5/"$#-')+,-$65!$%,-$&!%7"$J47-':
ALGORITMO REMOVE_MENOR 
 ENTRADA: UM HEAP BINÁRIO CRESCENTE H 
 SAÍDA: SE H NÃO ESTIVER VAZIO, REMOVE E DEVOLVE O MENOR
 ELEMENTO DE H; CASO CONTRÁRIO; DEVOLVE UM ERRO 
 
 SE H.ultima = 0 //HEAP UNDERFLOW 
 devolva ERRO e PARE 
 valor= H.vetor[1] 
 H.vetor[1] = H.vetor[H.ultima] 
 H.ultima = H.ultima - 1 
 i = 1 
 !"#$%"&' ()*+ , -./01+23 4 -.541678+9 : -.541678)*+9; 6/
 (2*i < H.ultima e H.vetor[i] > H.vetor[2*i+1]) 
 menor = 2*i 
 <! )*+ = -./01+23 4 -.541678)*+>?9 , -.541678)*+9 
 menor= menor+1 
 TROCA(H.vetor[i], H.vetor[menor]) 
 i = menor 
DEVOLVA valor
FIM {REMOVE_MENOR}
Algoritmo
2.11: Remove_Menor
K$JE5*"$"$'!E5)*$/-'&*"$"$*!/-+,-$(-$/!%-*$!4!/!%&-$(!$5/$7!"#$
0)%<*)-$9*!'9!%&!:$L0'!*3!$65!$"#M'$/-3!*$-$3"4-*$IN$#"*"$"$#*)/!)*"$#-')-
+,-$(-$3!&-*8$#*!9)'"/-'$&*-9<@4-$9-/$-$3"4-*$O$!$(!#-)'$9-/$-$3"4-*$6 para 
*!'&"5*"*$"$-*(!%"+,-$#"*9)"4$(-$7!"#:$P-&!$")%("$65!$"$*!/-+,-$(-$/!%-*$
elemento pode inverter a ordem entre elementos repetidos.
1 2 3 4 5 6 7 8 9 10
2 4 3 5 6 8 6 9 10
 !"#$"%&!'$("$*!/-+,-
1 2 3 4 5 6 7 8 9 10
3 4 6 5 6 8 10 9
 
1ª movimentação 2ª troca 1ª troca 
Figura 2.13: Remoção do menor elemento num heap binário crescente
Q!1"$%$R$7:54&)/":$L0'!*3!$65!$7:54&)/"$S$T$#-''5)$ log
T
n!$0)&'$')E%)J-
9"&)3-':$U%)9)"4/!%&!8$"$3"*)<3!4$)$#-''5)$"#!%"'$5/$0)&$')E%)J9"&)3-:$K$9"("$
)&!*"+,-$(-$4"+-8$ )$E"%7"$5/$0)&$')E%)J9"&)3-:$K#M'$ log
T
n!$ )&!*"+V!'8$ )$&!*<$
 log
T
n!$W$I$0)&'$')E%)J9"&)3-'$!8$#-*&"%&-8$&!*!/-'$)$X$7:54&)/"ST:$;-%'!65!%-
&!/!%&!8$-$4"+-$'!*<$J%"4)Y"(-:$;-%9452/-'$65!$-$K4E-*)&/-$Z!/-3![\!%-*$
*!65!*$&!/#-$O>4-E%C:
40 PESQUISA E ORDENAÇÃO DE DADOS
10. Heapsort
F-(!/-'$5'"*$7!"#'$0)%<*)-'$#"*"$-*(!%"*$9-/$0"'&"%&!$!J$9)?%9)"$
!$!4!E]%9)":$L$\D&-(-$ !"#'-*&$D$0"'!"(-$%-$5'-$(!$7!"#$0)%<*)-:$U%)9)"4@
/!%&!8$)%'!*)/-'$-'$!4!/!%&-'$("$4)'&"$%5/$7!"#$0)%<*)-$9*!'9!%&!:$./$'!@
E5)("8$^"Y!/-'$'59!'')3"'$*!/-+V!'$(-$/!%-*$!4!/!%&-$(-$7!"#8$9-4-9"%(-$
-'$!4!/!%&-'$*!/-3)(-'$(-$7!"#$(!$3-4&"$%"$4)'&":$K$4)'&"$!'&"*<$!%&,-$!/$
ordem crescente.
ALGORITMO HEAP SORT
 ENTRADA: UM VETOR L COM N POSIÇÕES
 SAÍDA: O VETOR L EM ORDEM CRESCENTE
inicialize um HBC H com n posições
PARA i = 0 até n - 1
 INSERE_HBC(H, L[i])
PARA i = 0 até n - 1
 L[i] = REMOVE_MENOR(H)
FIM {HEAP SORT}
Algoritmo 2.12: Heapsort
P"$'!+,-$"%&!*)-*$/-'&*"/-'$65!$"$ )%'!*+,-$!$"$*!/-+,-$(-$/!%-*$
!4!/!%&-$*!65!*$ &!/#-$ 4-E"*2&/)9-$%-$ &"/"%7-$(-$7!"#:$Q!%(-$"'')/8$"$
9-/#4!=)("(!$&!/#-*"4$(-$ !"#'-*&$#!*&!%9!$"$">%4-E%C:$
;-/-$3)/-'$"%&!*)-*/!%&!8$"$)%'!*+,-$!$"$*!/-+,-$(-$/!%-*$!4!/!%&-$
(-$7!"#$%,-$#*!'!*3"/$"$-*(!/$*!4"&)3"$!=)'&!%&!$!%&*!$-'$!4!/!%&-'$*!#!@
&)(-':$;-/-$9-%'!65?%9)"$(!''!$^"&-8$-$ !"#'-*&$D$%,-@!'&<3!4:
_)%"4/!%&!8$"$9-/#4!=)("(!$!'#"9)"4$(-$K4E-*)&/-$ !"#'-*&$D$">%C:$P-$
!%&"%&-8$#-(!/-'$ ^"9)4/!%&!$"("#&"*$-$ !"#'-*&$#"*"$ ^"Y!*$-*(!%"+,-$ in 
situ:$F"*"$)''-8$(!3!/-'$5'"*$-$#*M#*)-$!'#"+-$(-$3!&-*$9-/-$7!"#:$P!''!$
9"'-$'5"$9-/#4!=)("(!$!'#"9)"4$(-$ !"#'-*&$'!*<$O>IC:
L$ '!&!$ /D&-(-'$ 65!$ (!'9*!3!/-'$ %!'&!$ 9"#2&54-$ "&D$ "E-*"$ 5&)4)Y"/$
9-/-$-#!*"+,-$^5%("/!%&"4$"$9-/#"*"+,-$(!$!4!/!%&-'$("$4)'&":$`$#-''23!4$
/-'&*"*$65!$&-(-$/D&-(-$(!$-*(!%"+,-$0"'!"(-$%"$-#!*"+,-$(!$9-/#"*"+,-$
*!65!*$&!/#-$ !"#$%n):$P-$!%&"%&-$!=)'&!/$/D&-(-'$(!$-*(!%"+,-$65!8$'-0$
certas condições, ordenam em tempo linear. Naturalmente, tais métodos não 
',-$0"'!"(-'$!/$9-/#"*"+,-:$a)'95&)*!/-'$"$'!E5)*$&*?'$(!''!'$/D&-(-':
 
 !"#$%&'"&()$*+
Esse método$^-)$#*-#-'&-$#-*$ "*-4($ :$Q!b"*($!/$Icde$!$^"Y$"$-*(!@
%"+,-$5'"%(-$"$)(!)"$(!$9-%&"E!/:$f/"$*!'&*)+,-$(!''!$/D&-(-$D$65!$!4!$
'-/!%&!$-*(!%"$4)'&"'$(!$%G/!*-'$%"&5*")':$
Essa não é uma restrição muito severa, pois podemos converter di-
3!*'-'$ &)#-'$ (!$ 4)'&"'$ !/$ 4)'&"'$ (!$ %G/!*-'$ %"&5*")':$ F-*$ !=!/#4-8$ 5/"$
4)'&"$(!$%G/!*-'$)%&!)*-'$-%(!$-$/!%-*$3"4-*$D$@=$#-(!$'!*$9-%3!*&)("$%5/"$
4)'&"$(!$%G/!*-'$%"&5*")'$'-/"%(-$=$"$9"("$!4!/!%&-$("$4)'&":$f/"$4)'&"$
(!$%G/!*-'$*"9)-%")'$#-(!$'!*$9-%3!*&)("$%5/"$4)'&"$(!$%G/!*-'$)%&!)*-'$
multiplicando-se os elementos da lista por uma constante apropriada. 
a!$^"&-8$'!/#*!$65!$!=)'&)*$5/"$0)1!+,-$!%&*!$-$&)#-$(-'$("(-'$("$4)'&"$
!$5/$'509-%15%&-$(-'$%"&5*")'$D$#-''23!4$9-%3!*&!*$"$4)'&"$!/$5/"$4)'&"$(!$
%G/!*-'$%"&5*")':$U%^!4)Y/!%&!8$"4E5/"'$(!''"'$9-%3!*'V!'$#-(!/$&!*$5/$
)/#"9&-$%!E"&)3-$'-0*!$-$(!'!/#!%7-$(-$/D&-(-:$
O leitor interessado pode-
*<$ !%9-%&*"*$ 5/"$ #*-3"$
desse fato no livro Algo-
*)&/-'$g$h!-*)"$ !$F*<&)9":$
>;-/!%$!&$"4:8$TNNTC:
#$(!%-&"$9-/#4!=)("(!$%-$
/!47-*$9"'-:
41PESQUISA E ORDENAÇÃO DE DADOS
Q!1"$%$-$&"/"%7-$("$4)'&"$!$i$-$/")-*$3"4-*$9-%&)(-$%"$4)'&":$_"Y!/-'$
5'-$(!$5/$3!&-*$;$9-/$i$W$I$#-')+V!':$P-$#*)/!)*-$4"+-$(-$K4E-*)&/-$;-5%-
&)%E'-*&8$(!'9*)&-$"$'!E5)*8$-$3!&-*$;$D$)%)9)"4)Y"(-$9-/$Y!*-':
P-$4"+-$'!E5)%&!8$9-%&"/-'$65"%&"'$3!Y!'$9"("$5/$(-'$!4!/!%&-'$(!$
N$"$i$"#"*!9!$%"$4)'&":$F"*"$^"Y!*$)''-8$#!*9-**!/-'$"$4)'&"$!$#"*"$9"("$3"4-*$
)$9-%&)(-$%"$4)'&"$)%9*!/!%&"/-'$(!$5/"$5%)("(!$"$#-')+,-$)$(-$3!&-*$;:$
a!''"$^-*/"8$"-$J%"4$(!''!$4"+-$9"("$#-')+,-$)$(!$;$)%()9"$65"%&"'$3!Y!'$-$
valor de i ocorre na lista.
./$'!E5)("8$^"Y!/-'$"$soma acumulada$(-$3!&-*$;:$F!*9-**!/-'$%--
3"/!%&!$-$3!&-*$;8$(!''"$3!Y$"$#"*&)*$("$'!E5%("$#-')+,-8$'-/"%(-$9"("$
posição i do vetor c com a posição anterior. O resultado da soma é guarda-
(-$%"$#*M#*)"$#-')+,-$):$K#M'$*!"4)Y"*$"$'-/"$"95/54"("8$9"("$#-')+,-$)$
(-$3!&-*$;$)%()9"*<$65"%&-'$!4!/!%&-'$("$4)'&"$',-$/!%-*!'$-5$)E5")'$"$):$
L03)"/!%&!8$'!$)$-9-**!$%"$4)'&"$!$;j)k$R$18$65"%(-$"$4)'&"$!'&)3!*$-*(!%"("$-$
3"4-*$)$(!3!*<$-95#"*$"$1@D')/"$#-')+,-$("$4)'&":
F!*9-**!/-'$/")'$5/"$3!Y$"$ 4)'&"8$(!''"$ 3!Y8$("$()*!)&"$#"*"$"$ !'-
65!*("$>#"*"$E"*"%&)*$65!$"$-*(!%"+,-$'!1"$!'&<3!4C$!$9-4-9"/-'$9"("$3"4-*$
)$9-%&)(-$%"$4)'&"$%"$#-')+,-$9j)k$g$I$(!$5/$3!&-*$"5=)4)"*:$F"*"$!3)&"*$65!$
/G4&)#4"'$9M#)"'$(!$5/$3"4-*$9-%&)(-$%"$4)'&"$'!1"/$9-4-9"("'$%5/"$/!'/"$
#-')+,-$(-$3!&-*$"5=)4)"*8$"#M'$9-4-9"*$5/$3"4-*$)$%-$3!&-*$"5=)4)"*8$(!9*!-
/!%&"/-'$(!$5/"$5%)("(!$"$#-')+,-$ )$(!$;:$P-$G4&)/-$ 4"+-8$9-#)"/-'$-$
3!&-*$"5=)4)"*$#"*"$"$4)'&":
ALGORITMO COUNTING SORT 
 ENTRADA: UM VETOR L CONTENDO N NÚMEROS NATURAIS NO
 INTERVALO DE 0 A K 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 PARA i = 0 até k // INICIALIZACAO DE C 
 c[i]=0 
 PARA i = 0 até n - 1 // CONTAGEM 
 c[L[i]]= c[L[i]] +1 
 PARA i = 1 até k // SOMA ACUMULADA 
 c[i]= c[i] + c[i-1] 
 PARA i= n - 1 até 0 (passo -1) // ORDENACAO 
 c[L[i]] = c[L[i]] - 1 
 aux[c[L[i]]]= L[i] 
 PARA i = 0 até n - 1 // COPIANDO AUX PARA L 
 L[i]= aux[i]
FIM {COUNTING SORT}
Algoritmo 2.13: Countingsort
L$K4E-*)&/-$;-5%&)%E'-*&$D$9-%'&)&52(-$(!$9)%9-$4"+-'$)%(!#!%(!%&!':$
Três desses laços gastam tempo ">%C$!$-'$-5&*-'$(-)'$E"'&"/$&!/#-$">iC:$
K4D/$()''-8$3!&-*$;$&!/$i$W$I$#-')+V!'$!$-$3!&-*$"5=$&!/$%$#-')+V!':$;-%-
9452/-'$65!$"$9-/#4!=)("(!$&!/#-*"4$!$"$9-/#4!=)("(!$!'#"9)"4$(-$;-5%-
tingsort pertencem a ">%$W$iC:$F"*"$"$94"''!$(!$4)'&"'$-%(!$i$%,-$D$/5)&-$
/")-*$(-$65!$%8$/")'$#*!9)'"/!%&!8$'!$i$% ">%C8$!%&,-$&")'$9-/#4!=)("(!'$
pertencem a ">%C:$$L$95)("(-$65!$&)3!/-'$"-$#!*9-**!*$"$4)'&"$(-$J%"4$#"*"$
-$)%29)-$%-$65"*&-$4"+-$E"*"%&!$"$!'&"0)4)("(!$(!$;-5%&)%E'-*&$:
P"$_)E5*"$T:Ie$!=)0)/-'$-$9-%&!G(-$(-$3!&-*$;$"-$J%"4$(!$9"("$4"+-$(-$
K4E-*)&/-$;-5%&)%E'-*&:$L$9-%&!G(-$(-$3!&-*$"5=$9-**!'#-%(!$l$4)'&"$-*)E)-
nal em ordem crescente.
42 PESQUISA E ORDENAÇÃO DE DADOS
0 1 T O e 5
m)'&"$-*)E)%"4 8 e 5 O 8 T
n!&-*$; 0 1 T O e 5 6 7 8
1º laço 0 0 0 0 0 0 0 0 0
0 1 T O e 5 6 7 8
To$4"+- 0 0 1 1 1 1 0 0 T
0 1 T O e 5 6 7 8
Oo$4"+- 0 0 1 T O e e e 6
0 1 T O e 5 6 7 8
eo$4"+- 0 0 0 1 T O e e e
0 1 T O e 5 6 7 8
5º laço 0 0 0 1 T O e e e
n!&-*$"5= 0 1 T O e 5
T O e 5 8 8
Figura 2.14: Ordenação com o Algoritmo Countingsort
12. Bucketsort
./0-*"$ !''!$/D&-(-$#!*/)&"$ -*(!%"*$ 4)'&"'$(!$%G/!*-'$65")'65!*8$
(!'9*!3!*!/-'$5/"$3!*',-$(!''!$/D&-(-$65!$-*(!%"$4)'&"'$(!$%G/!*-'$%,-$
negativos. 
Q!$"$ 4)'&"$"$'!*$-*(!%"("$&!/$%$!4!/!%&-'8$'!*<$5'"(-$5/$3!&-*$(!$
#-%&!)*-'$>059i!&C$9-/$%$#-')+V!':$Q!$-$/")-*$!4!/!%&-$("$4)'&"$D$i8$9"("$
#-')+,-$(-$059i!&$"#-%&"*<$#"*"$5/"$4)'&"$!%9"(!"("$%"$65"4$'!*,-$)%'!*)-
(-'$-'$!4!/!%&-'$("$4)'&"$65!$#!*&!%9!/$"-$)%&!*3"4-$j$$)$p$>i$W$IC$S$%$8$>)$W$IC$
p$>i$W$IC$S$%C:$L0'!*3!$65!$-$)%&!*3"4-$D$^ !97"(-$l$!'65!*("$!$"0!*&-$l$()*!)&":$
K$)(!)"$(-$/D&-(-$D$()3)()*$-$)%&!*3"4-$65!$3")$(!$N$"&D$i$!/$%$'50)%-
&!*3"4-'$
(!$/!'/-$ &"/"%7-:$;"("$ '50)%&!*3"4-$ !'&"*<$ "''-9)"(-$ "$5/"$
4)'&"$4)E"("$65!$)*<$9-%&!*$-'$!4!/!%&-'$("$4)'&"$65!$#!*&!%9!/$l65!4!$'5-
0)%&!*3"4-:$F-*$!=!/#4-8$'!$"$4)'&"$&!/$-)&-$!4!/!%&-'$D$-$/")-*$(!4!'$D$qI8$
&!*!/-'$-)&-$)%&!*3"4-'r$jN8$cC8$jc8$IsC8$:::8$jtO8$qTC:$K$#-')+,-$Y!*-$(-$059i!&$
"#-%&"*<$#"*"$5/"$4)'&"$!%9"(!"("$65!$)*<$9-%&!*$-'$!4!/!%&-'$("$4)'&"$65!$
',-$/")-*!'$-5$)E5")'$"$Y!*-$!$/!%-*!'$65!$c8$!$"'')/$#-*$()"%&!:
;7"/"*!/-'$-$059i!&$(!$3!&-*$u:$F"*"$9-%'&*5)*$"'$4)'&"'$!%9"(!"("'$
(!3!/-'$)%'!*)*$9"("$3"4-*$1$9-%&)(-$%"$4)'&"$"$'!*$-*(!%"("$%"$4)'&"$!%9"(!-
"("$"#-%&"("$#-*$uj$1$p$%$S$>i$W$ICk:$./$'!E5)("8$-*(!%"/-'$"'$4)'&"'$!%9"-
(!"("'$9-/$5/$/D&-(-$(!$-*(!%"+,-$65"465!*$>(!$#*!^!*?%9)"$!'&<3!4C:$K#M'$
)''-8$"$9-%9"&!%"+,-$("'$4)'&"'$!%9"(!"("'$#*-(5Y$"$4)'&"$-*)E)%"4$-*(!%"(":$
ALGORITMO BUCKET SORT 
 ENTRADA: UM VETOR L CONTENDO N NÚMEROS NO INTERVALO DE 
 0 ATÉ K 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
PARA i = 0 até n - 1 //INICIALIZACAO 
 B[i] = NULO 
//CONSTRUINDO AS LISTAS ENCADEADAS 
PARA i = n - 1 até 0 (PASSO -1)
 +@A+73 B8+9 @6 +@+C+6 D3 0+A13 0+E3D3 3F6@13D3 F67 
 B[L[i] * n / (K + 1)] // DIVISÃO INTEIRA 
//ORDENANDO E CONCATENANDO AS LISTAS ENCADEADAS
j = 0 
PARA i = 0 até n - 1 
43PESQUISA E ORDENAÇÃO DE DADOS
 coloque a lista apontada por B[i] em ordem crescente 
 p = B[i] 
 !"#$%"&' ( ) "$*' 
 L[j] = p.info 
 p = p.proximo 
 j = j + 1 
 remova a lista apontada por B[i]
FIM {BUCKET SORT}
Algoritmo 2.14: Bucketsort
 !"#"$%&'%()*(+#,$%,#)*(-),*(!".)*(+)-%$(*%#(%/%01'"-)*(%$('%$+)(
 2&34(5)'%(61%()('"$"&7)(médio(-%(0"-"(!,*'"(%&0"-%"-"(*%#8(94(:%(;"')<(*%(
)*(%!%$%&')*(-%(=(%*',>%#%$(1&,;)#$%$%&'%(-,*'#,?1@-)*(&)(,&'%#>"!)(AB<(C3<(
D(+)**@>%!($)*'#"#(61%()('"$"&7)(esperado(-%(0"-"(!,*'"(%&0"-%"-"(*%#8(
0)&*'"&'%4(5%**%(0"*)<( ,&-%+%&-%&'%(-)($D')-)(1',!,E"-)<("()#-%&".F)(-%(
0"-"(!,*'"(%&0"-%"-"(*%#8(;%,'"(%$('%$+)(%*+%#"-)(0)&*'"&'%4(
G(0H+,"(-)*(%!%$%&')*(-%(1$"(!,*'"(%&0"-%"-"(#%61%#('%$+)("$)#',E"-
do constante. A remoção de uma lista encadeada também é feita em tempo 
"$)#',E"-)(0)&*'"&'%4( )&*%61%&'%$%&'%<()('%#0%,#)(!".)(,#8(#%61%#%#('%$-
+)(%*+%#"-)(0)&*'"&'%<(%("(0)$+!%/,-"-%('%$+)#"!(esperada do Algoritmo 
I10C%'*)#'(*%#8( 2&34
5)'%(61%(&)(*%J1&-)(!".)(+%#0)##%$)*("(!,*'"(-"(-,#%,'"(+"#"("(%*61%#-
-"4( )$(,**)<(")(0)&*'#1,#("*(!,*'"*(%&0"-%"-"*(+#%*%#>"$)*("()#-%$(#%!"',>"(
%/,*'%&'%(%&'#%()*(%!%$%&')*(#%+%',-)*4(K%()($D')-)(1',!,E"-)(+"#"()#-%&"#("*(
!,*'"*(%&0"-%"-"*(;)#(%*'8>%!<()(G!J)#,'$)(I10C%'*)#'('"$?D$(*%#8(%*'8>%!4(
L(?10C%'('%#8(&(+)*,.M%*4(G(61"&',-"-%(-%(&H*(&"*(!,*'"*(%&0"-%"-"*(
*%#8(&4( )&0!1@$)*(61%("(0)$+!%/,-"-%(%*+"0,"!(-)(I10C%'*)#'(+%#'%&0%("(
 2&34(N,&"!$%&'%<()?*%#>%(61%(I10C%'*)#'(&F)(,#8(#%61%#%#(0)$+"#".M%*(*%(
o método usado como subrotina não for baseado em comparações.
G(OJ1#"("(*%J1,#(%/%$+!,O0"("*( !,*'"*(%&0"-%"-"*(0)&*'#1@-"*(+%!)(
I10C%'*)#'("+H*(*1"()#-%&".F)4( !"#"$%&'%<("(0)&0"'%&".F)(-"*(!,*'"*(%&-
0"-%"-"*(+#)-1E("(!,*'"()#,J,&"!(%$()#-%$4
0 1 P Q R 5 6 7
=,*'"()#,J,&"! PS TQ 9P 5 9P R 71 RB
0 U R U 5
1 U 9P U 9P
P
I10C%'( (Q U PS
R U RB
5 U TQ
6
7 U 71
Figura 2.15: Ordenação com o Algoritmo Bucketsort
13. Radixsort
V**%($D')-)(+%#$,'%()#-%&"#(!,*'"*(01W)*(%!%$%&')*(*%W"$(-),*("(-),*(
0)$+"#8>%,*4(X$"(>%#*F)(-%**%($D')-)(;),(1',!,E"-"(%$(9SSY(+)#(Z%#$"&(
Z)!!%#,'7<(;1&-"-)#(-%(1$"(%$+#%*"(61%($",*('"#-%(-%1()#,J%$([(\I]4
44 PESQUISA E ORDENAÇÃO DE DADOS
V$(0"-"(,'%#".F)(-)(^"-,/*)#'<()#-%&"$)*("(!,*'"(+)#(1$"(-%(*1"*(
+)*,.M%*<(0)$%."&-)(+%!"(+)*,.F)($%&)*(*,J&,O0"&'%<("'D(07%J"#([(+)*,.F)(
$",*(*,J&,O0"&'%(2)*(%!%$%&')*(-"(!,*'"(-%>%$(61%(*%#(#%+#%*%&'"-)*(0)$("(
$%*$"(61"&',-"-%(-%(+)*,.M%*34( "-"()#-%&".F)('%$(61%(*%#(;%,'"(0)$(1$(
$D')-)(%*'8>%!4
ALGORITMO RADIX SORT 
 ENTRADA: UM VETOR L COM N POSIÇÕES CUJOS ELEMENTOS
 POSSUEM D SÍMBOLOS 
 SAÍDA: O VETOR L EM ORDEM CRESCENTE 
 
 PARA i = 1 até d 
 Coloque L em ordem crescente pelo i-ésimo símbolo menos 
 +,-.,/01.23 4+1.56 47 782656 53 6953.1:;6 3+2<=3>
FIM {RADIX SORT}
Algoritmo 2.15: Radixsort
_)-%$)*("-"+'"#()( )1&',&J*)#'(%(1',!,E8`!)(0)$)(*1?#)',&"(&)(^"-
-,/*)#'4(L?*%#>%(61%()*(%!%$%&')*(-"(!,*'"(*F)(0)&*','1@-)*(-%(*@$?)!)*(-%(
"!J1$("!;"?%')4(_)#(%/%$+!)<(*%("(!,*'"(0)&'D$(&a$%#)*(-%0,$",*<()("!;"?%')(
D(;)#$"-)(+%!)*(-@J,')*(-)(*,*'%$"(&1$D#,0)(-%0,$"!4(5)'%(61%()($",)#(*@$-
?)!)(%&0)&'#"-)(&1$"(+)*,.F)(-%(1$(%!%$%&')(&F)(%/0%-%()($",)#(*@$?)!)(
-)("!;"?%')4( )$)()('"$"&7)(-)("!;"?%')(D(0)&*'"&'%<(+)-%$)*(J"#"&',#(61%(
"(0)$+!%/,-"-%('%$+)#"!(%("(0)$+!%/,-"-%(%*+"0,"!(-%**"(>%#*F)(-)( )1&-
tingsort pertencem a 2&34
L1'#"(+)**,?,!,-"-%(*%#,"("-"+'"#()(I10C%'*)#'(%(1',!,E8`!)(0)$)(*1-
?#)',&"4(_"#"(,**)<()(?10C%'(-%>%#8('%#(1$"(+)*,.F)(+"#"(0"-"(%!%$%&')(-)(
"!;"?%')4(5F)(7">%#8(&%0%**,-"-%(-%()#-%&"#("*(!,*'"*(%&0"-%"-"*(>,*')(61%(
0"-"(1$"(-%!"*(0)&'D$("+%&"*(%!%$%&')*(0)$()($%*$)(*@$?)!)(&"(+)*,.F)(
61%(%*'8(*%&-)()#-%&"-"4(_)-%$)*(%&'F)(J"#"&',#(61%("(0)$+!%/,-"-%('%$-
+)#"!(-%**"(>%#*F)(-)(I10C%'*)#'(*%#8( 2&34(
5)'%(61%('"&')()( )1&',&J*)#'(61"&')()(I10C%'*)#'(*F)(%*'8>%,*4(X',-
!,E"&-)(61"!61%#(1$(-%!%*(0)$)(*1?#)',&"<()(^"-,/*)#'('%#8(0)$+!%/,-"-%(
temporal 2-&3(%(0)$+!%/,-"-%(%*+"0,"!( 2&34(K%(-(;)#(0)&*'"&'%("(0)$+!%-
/,-"-%('%$+)#"!(*%#8( 2&34(5)'%(61%()(^"-,/*)#'(D(&%0%**"#,"$%&'%(%*'8>%!<(
61"!61%#(61%(*%W"()($D')-)(1*"-)(0)$)(*1?#)',&"4
QP 500 500 b
500 RQ9 b QP
RQ9 QP RQ9 QP
PRS U QP U QP U RS
b
Ordenando 
pela 
unidade
cQ
Ordenando 
pela 
-%E%&"
QP
ordenando 
pela 
centena
cQ
QP PRS PRS PRS
cQ RS RS RQ9
RS b cQ 500
Figura 2.16: Ordenação com o Algoritmo Radixsort
45PESQUISA E ORDENAÇÃO DE DADOS
1. )$+!%'%("('"?%!"("?",/)4
Método
 )$+!%/,-"-%('%$+)#"! )$+!%/,-"-%(
espacial
d(%*'8>%!e
]%!7)#(0"*) Pior caso "*)($D-,)
I)!7" (nP3 (nP3 (nP3 O293 K,$
I)!7"(0)$(f("J
Inserção
K%!%.F)
K7%!!*)#'
Mergesort
Quicksort
Z%"+*)#'
2.( "#"0'%#,E%()(+,)#(%()($%!7)#(0"*)<(%$('%#$)*("**,&'H',0)*<(-%(0"-"(1$(
-)*($D')-)*(61%("+"#%0%$(&"('"?%!"("0,$"4
3.(])*'#%(0)$)(O(0"#,"("(!,*'"(29S<(PQ<(QY<(PP<(PT<(9c<(Q<(Q9<(T<(PS<(c<(QR<(b<(
RT3("+H*(0"-"(,'%#".F)(-)(!".)($",*(%/'%#&)(-)*("!J)#,'$)*(?)!7"<(,&*%#`
.F)<(*%!%.F)<(*7%!!*)#'(%(#"-,/*)#'<(-%*0#,')*(&%*'%(0"+@'1!)4
4.(])*'#%(0)$)(O(0"#,"("(!,*'"(29S<(PQ<(QY<(PP<(PT<(9c<(Q<(Q9<(T<(PS<(c<(QR<(b<(
RT3("+H*(*%#(+"#',0,)&"-"(+%!)(_#)0%-,$%&')(_"#',.F)("+#%*%&'"-)(&%*'%(
0"+@'1!)4
5.(:%&'#%()*($D')-)*(?)!7"<(?)!7"(0)$(f("J<( ,&*%#.F)<(*%!%.F)<(*7%!!*)#'<(
$%#J%*)#'(%(61,0C*)#'<(61",*((*%#,"$()*($",*(%O(0,%&'%*<(%$('%#$)*(-%(
'%$+)<(+"#"(0)!)0"#(!,*'"*(-"(;)#$"(2&<(9<(P<(Q<((444<(n(g(93(%$()#-%$(0#%*`
0%&'%e(h1*',O(61%(*1"(#%*+)*'"4
6.( V*0#%>"( 1$( "!J)#,'$)( 61%( ,$+!%$%&'%( )($D')-)( ?)!7"( +"#"( )#-%&"#(
!,*'"*( %&0"-%"-"*( 0)&'%&-)(&a$%#)*4( )&*,-%#%( 61%( 0"-"(&H( -"( !,*'"(
possui os campos info, anterior e proximo.
7.(\&-,61%(61",*(',+)*(-%(!,*'"*(+)-%$(*%#()#-%&"-"*(+%!)*($D')-)*( )1&`
',&J*)#'<(I10C%'*)#'(%(^ "-,/*)#'(%(61%(0)&-,.M%*(+#%0,*"$(*%#(*"',*;%,'"*(
+"#"( 61%( %!%*( '%&7"$( 0)$+!%/,-"-%( -%( '%$+)( !,&%"#( &)( '"$"&7)( -"(
lista.
8.( i)0j( -%*%W"( )#-%&"#( %$( '%$+)( !,&%"#( !,*'"*( -%(n elementos contendo 
&a$%#)*(,&'%,#)*(%&'#%(9(%(9Bn4(k1"!($D')-)(>)0j(1',!,E"#,"(e(h1*',O(61%(
sua resposta.
9.(])*'#%(0)$)(O(0"#,"()(>%')#( (&)(O(&"!(-%(0"-"(1$(-)*(0,&0)(!".)*(-)(
G!J)#,'$)( )1&',&J*)#'(")()#-%&"#("(!,*'"(29S<(PQ<(9Y<(PP<(PT<(9c<(Q<(99<(
T<(S<(c<(R<(b<(9T34
46 PESQUISA E ORDENAÇÃO DE DADOS
10.(])*'#%(0)$)(O0"#,"$("*(!,*'"*(%&0"-%"-"*(J%#"-"*(&)($D')-)(?10C%'(
*)#'(")()#-%&"#("(!,*'"(29S<(PQ<(9Y<(PP<(PT<(9c<(Q<(R9<(T<(S<(c<(QR<(b<(9T34
11.(G+H*(0"-"(,'%#".F)(-)(!".)($",*(%/'%#&)(-%(1$("!J)#,'$)(-%()#-%&".F)<(
"(!,*'"(2QSP<(9RP<(RYR<(PcY3(O0)1(0)$)($)*'#"-)("?",/)4(k1"!(;),()("!-
J)#,'$)(1',!,E"-)(2?)!7"<(,&*%#.F)<(*%!%.F)()1(#"-,/*)#'3e(h1*',O61%(+)#(
61%(&%&71$(-)*()1'#)*("!J)#,'$)*(%*'1-"-)*(&%*'%(0"+@'1!)(+)-%#,"('%#(
+#)-1E,-)("*(!,*'"*("?",/)4
29RP<(QSP<(RYR<(PcY3(
29RP<(PcY<(RYR<(QSP3(
29RP<(PcY<(QSP<(RYR3
 12.(V*0#%>"(1$(+#)0%-,$%&')(61%(#%0%?"(1$(7%"+(?,&8#,)(0#%*0%&'%(2+"*-
*"-)(+)#(#%;%#j&0,"3(%(1$"(+)*,.F)(i(%(%&'F)(#%$)>"()(%!%$%&')(61%(%*',-
ver na posição i(-)(7%"+4
13.(V*0#%>"(1$(+#)0%-,$%&')(61%('#"&*;)#$%(1$(>%')#(&1$(7%"+(?,&8#,)(
crescente em tempo linear.
14. ])*'#%(0)$)(O0"#,"(1$(7%"+(?,&8#,)(0#%*0%&'%(&)(61"!(;)#"$(,&*%#,-)*(
os valores 9S<(PQ<(9Y<(PP<(PT<(9c<(Q<(R9<(T<(S<(c<(QR<(b<(9T, nesta ordem (seu 
7%"+(-%>%(*%#(,$+!%$%&'"-)(&1$(>%')#(-%(9T(+)*,.M%*34(V$(*%J1,-"<(#%-
$)>"()(%!%$%&')(61%(%*',>%#(&"(+)*,.F)(Q<(-%+),*()(%!%$%&')(61%(%*',>%#(
&"(+)*,.F)(P(%(+)#(O$()(%!%$%&')(61%(%*',>%#(&"(+)*,.F)(9(%(%&'F)($)*'#%(
0)$)(O0"#,"()(7%"+4