Ordenação Externa Com Quicksort - Ciência Da Computação - Ufpb

8/19/2019 Ordenação Externa Com Quicksort - Ciência Da Computação - Ufpb

1/33

ORDENAÇÃO EXTERNACOM QUICKSORT.

ORDENAÇÃO EXTERNA


2/33

O que é?

Ordenação E!erna é um termo para uma classe dealgoritmos de ordenação que podem trabalar sobregrandes !olumes de dados" A Ordenação E#terna é

necess$ria quando os dados que de!em ser ordenadosnão cabem completamente na mem%ria principal docomputador e est$ contida em uma mem%ria e#ternamais lenta &e#"' (D)" A Ordenação E#terna tipicamenteusa uma estratégia ibrida de &sort*merge)" Na +ase

de ordenação, blocos de dados pequenos o bastantepara caber na mem%ria principal são lidos, ordenados,e escritos em um arqui!o tempor$rio" Na +ase domerge, os sub*arqui!os pré*ordenados sãocombinados em um -nico arqui!o"


3/33


4/33

Onde é u#ado?

9asicamente, a Ordenação E#terna éusada em sistemas de bancos de

dados robustos, sistema depaginação de arqui!os nos modernos:O, em so+t;ares que tratam da 9igData, so+t;ares de mapeamento deDNA e do 6enoma, sistemas que+a0em o processamento de grandesarqui!os de dados coletados no

espaço, etc"


5/33

A%&un# ee'(%o# de u#o.

Os bancos de dados' 8? 8ariaD9? OracleD9? 8ongoD9?

6eralmente +a0em uso de métodos deordenação e#terna em arqui!os muito grandes,ordenando as ca!es de suas tabelas, paraassim agili0ar na posterior busca desses dados?


6/33

Qu)*+Sor!.@n+ormaçes importantes sobre o =uicB:ort


7/33

Qu)*+Sor!

O algoritmo =uicBsort é um método de ordenaçãomuito r$pido e e2ciente, in!entado por ."A"R(oare em 7C5, quando !isitou a 3ni!ersidade de

8oscou como estudante" Naquela época, (oaretrabalou em um pro1eto de tradução de m$quinapara o National aborator


8/33

Qu)*+Sor!

=uicBsort é o algoritmo de ordenação baseado em comparaçes maisr$pido que se conece" Ele requer O,n log n- etapas na 'éd)atrabalando G@n*laceH o que signi2ca que seus requerimentos sãomInimos em uso de mem%ria e#tra" =uicBsort geralmente é escrito de+orma recursi!a, mas $ meios de se escre!er de +orma não recursi!a"

O algoritmo de =uicBsort emprega uma estratégia de di!idir paraconquistar, di!idindo a listaJ!etor em duas sub*listas"

asso a passo'

o Escole um elemento, camado ()$/, na lista de entrada"

o Reordena a lista para que todos os elementos com !alores menores doque o pi!K 2quem do lado esquerdo do pi!K, enquanto que todos os

!alores maiores 2quem ap%s o pi!K &!alores iguais podem 2car a direita

ou esquerda, dependendo da implementação)" Ao 2m do processo o

pi!K estar$ em sua posição 2nal e a!er$ duas sub*listas não

ordenadas, este processo é camado de artição"

o Recursi!amente ordena a sub*lista dos elementos menores e a sub*lista


9/33

Qu)*+Sor! ,Ee'(%o&r01*o-


10/33

Qu)*+Sor! ,Ee'(%o&r01*o-


11/33

Qu)*+Sor! ,A%&or)!'o-


12/33

Qu)*+Sor! ,Qu)2-

7" =ual é o custo de tempo de um quicBsort emum arra< de tamano n que 1$ se encontraordenadoL Obs"' O pi!K escolido nesse caso é o

Indice 5 &0ero)"

4" :e n%s escolermos o elemento médio do!etor para cada camada recursi!a de quicBsort,

qual ser$ o custo de tempo de e#ecuçãoLM" =uicBsort é e#tremamente dependente da

escola do pi!K" Então, como escoler o pi!KL


13/33

Qu)*+Sor! ,Re#(o#!a# 3Qu)2- 7" O,n45-

@sso ocorre porque na +ase da partição de!er$percorrer todo o arra< de elementos em cada

nI!el de recursão' n, n*7, n*4,""" 7O que nos d$ um tempo de e#ecução de' n6,n78-6,n75-6...68 9 O,n45- Este é o pior caso

4" O,n%o&,n--" E este é o melor caso quepodemos ter com o =uicB:ort"

M" De!eremos pre+erencialmente escoler de+orma rando')*a o pi!K para cada camada

recursi!a"


14/33

Qu)*+Sor!=uicB:ort usado na Ordenação E#terna


15/33

Qu)*+Sor! E!erno ,)n "%a*e-: "ar!)*)onador ;

O =uicB:ort E#terno &@n lace), +a0 aordenação dos dados contidos em um arqui!o,sem a utili0ação de mem%ria au#iliar, mas

internamente, usa uma estratégia de GandarHpelos b


16/33

Qu)*+Sor! E!erno ,)n"%a*e-


17/33

Qu)*+Sor! E!erno ,)n "%a*e-: "ar!)*)onador ;


18/33


19/33


20/33

Qu)*+Sor! 6 OrdenaçãoE!erna

O =uicB:ort quando usado naordenação e#terna é

ma1oritariamente implementadonuma estratégia ibrida de=uicB:ortS8erge, nãonecessariamente o 8erge:ortpadrão, usa*se uma !ariante do8erge:ort onde o +oco é 1untar aspartes que !ão sendo ordenadas

internamente pelo =uicB:ort"


21/33

Qu)*+Sor! 3 Ordenação E!erna:


22/33

Qu)*+Sor! 3 Ordenação E!erna

O arqui!o com os dados de entrada éparticionado em N partes, sendo N umm-ltiplo de 4, encontrado pelo algoritmo

le!ando em consideração a quantidade demem%ria RA8 disponI!el no momento daOrdenação dos Dados e o tamano total doarqui!o" Assim teremos N arqui!os de

tamanos semelantes" Tomaremos comoe#emplo N sendo , assim !amos trabalarcom o arqui!o principal particionado em partes"

:


23/33


7" rimeiro o arqui!o é particionado ao meio,gerando 4 arqui!os : Q>.=)n Q8.=)n Q5.=)n eQ.=)n ;?

4" Em seguida cada um desses arqui!os é passadopelo =uicB:ort &algoritmo padrão, pois o tamanode cada arqui!o GcabeH na mem%ria RA8 principal)e serão particionados em : @>>.=)n 6 >.=)n@>8.=)n 6 8.=)n @>5.=)n 6 5.=)n e

@>.=)n 6 .=)n ; onde arqui!os G>H sãoarqui!os contendo a parte dos dados com osmenores !alores, e G(H conterão os de maior !alor,assim teremos U arqui!os pré*ordenados"

:


24/33


M" Agora pegaremos o lado G>H dos arqui!os, oalgoritmo ir$ abrir : @>>.=)n 6 @>8.=)n ; emum !etor, passar$ o !etor numa camada do

=uicB:ort, e sal!ar$ em @8>.=)n e @88.=)n,+aremos o mesmo com o restante dos arqui!os G>H? " Na quarta etapa, abrir$ os arqui!os : @8>.=)n

6 @85.=)n ; e sal!ar$ como @>>.=)n e @>8.=)n Gsobrescre!endo os arqui!os antigos de mesmo

nome, desta +orma diminuImos o uso de espaçoe#tra no (DH, +a0emos isso com o restante dosarqui!os G>H?

:


25/33


P" Na quinta etapa, o algoritmo ir$ abrir os arqui!os: @>>.=)n 6 @>8.=)n ;, passar no!amente na camada de=uicB:ort, e sal!ar nos arqui!os @8>.=)n e @88.=)n?

" Nessa etapa, cegaremos ao ponto em que precisamos

camar o método 8erge para os arqui!os G>H, o que ir$passar gerar um s% arqui!o camado GSor!ed@.=)nH, o qualconter$ a parte contendo os menores !alores do arqui!ooriginal"

Q" Agora repetimos as mesmas etapas a partir do ponto M, s%que agora com o lado dos arqui!os G(H?

U" Ao 2nal destes dois processos, 2nalmente camaremosno!amente a +unção 8erge, s% que agora iremos mesclar osarqui!os GSor!ed@.=)n 6 Sor!ed


26/33


27/33

Qu)*+Sor! 3 Ordenação E!erna: A%&or)!'o 3 "ar!e 8 ;


28/33


29/33

Qu)*+Sor! 3 Ordenação E!erna: A%&or)!'o 3 "ar!e 5 ;


30/33


31/33

Ban!a&en# eDe#$an!a&en#Vantagens' ossibilidade de poder ordenar arqui!os maiores do que a

mem%ria RA8 disponI!el" ode*se +a0er ordenação de arqui!os muito grandes usando uma

pequena +ração de mem%ria" E#"' 456b de arqui!o em umam$quina com 76b de RA8 ou menos

Des!antagens' 8uito lento se comparada a Ordenação @nterna, pelo +ato de ter

o custo das operaçes de @JO no disco lento"

Fa0 uso de espaço e#tra no (D, mesmo que de +ormatempor$ria, o que pode em (Ds com pouca capacidade,ocasionar em disco ceio"

=uanto mais pedaços de arqui!os, mais lento ser$ a ordenaçãodos dados, de!ido ao custo de @JO e trabalos para mesclagemdos arqui!os"


32/33

A%!erna!)$a#

A alternati!a mais comum ao uso do =uicB:ort paraordenação e#terna é 1ustamente o 8erge:ort, o maisdi+undido é o 8erge:ort W*a


33/33

Qu)*+Sor! E!erno 7Con*%u#ão

odemos assim concluir que o uso do=uicB:ort e#terno, assim como

outros métodos de ordenaçãoe#terna são de e#trema importZnciano mundo da computação eprocessamento de dados" odemosa2rmar que em alguns casos é a-nica alternati!a para se cegar aessa 2nalidade"

Documents

Ordenação Externa Com Quicksort - Ciência Da Computação - Ufpb