Projeto e Análise de Algoritmos - Aula 08 - Algoritmos Heapsort e Quicksort

[Música] i [Música] hola pesos serían 22 años aula número 8 del proyecto y análisis de algoritmos de sao las veremos sus algoritmos heap short y quick sort vamos a analizar esos dos algoritmos vamos a presentar también cada uno de ellos nasales pasadas vimos summers short un mes o de ilustra una técnica de concepción de algoritmos eficiente que ha división y conquista técnica de división y conquista en esa ola veremos su hip short que ilustra uso de estructuras de dados de modo que bosé consiga también un algoritmo eficiente ccoo que ha ideado hit short no la

pasada vimos como que funciona estructura hit mesa o la vamos a usar las operaciones que presentamos la ola anterior para crear un algoritmo llamado heap short ayuda en todo para ordenar un vector usando un hit easy gym primero ha construido un heap máximo de boise tocada ahí es como elementos de última exposición de un vector después disminuimos su tamaño de hit en 1 y lanzamos un hit máximo casos sea necesario y finalmente repetimos estos tres últimos pasos varias veces vayamos en todo un ejemplo a quines arbolé temos un hit en un hit mismo no por

ejemplo udi soy del menor que 26 ó 14 menos que 26 y si alguien se verifica en un hit mismo tanto un primero que pasemos a construir un hit dado que tenemos un hit ahora pasemos su segundo paso que sería tocar un primer elemento la verdad yo elemento que está la raíz con un último elemento en este caso en nuestro carro 26 y como 16 una vez que tocamos su 26 y 16 ahora vamos a ver que colocaron 16 la posición se alta porque que importante tocar a raíz con un último elemento porque que alguien

si estás haciendo hizo porque sabemos que el elemento mayor está exactamente en ajá y su elemento mayor de un hippie está la raíz entonces ya sabemos cualquier proposición se harta de ese elemento 26 y debe ser un último elemento de un uso vector set por en ahora ya no tenemos más que sobre no hay más un hippie de un elemento que está en un lugar dejado y ya vimos no la anterior como omar hizo vamos a sumar hizo haciendo con 15 16 de esa hace un lugar cierto lo hacemos si son todo comparamos con sus

vídeos va a subir udis hoy te hacemos un mismo depois como 16 y se os fillos va a subir un mayor de ellis que se 16 y -sector ahí hacemos un mes muy conocidos fideos que sería 16 con 15 está en un lugar ser si no fuésemos más ok próximo paso hago ahora que sabemos que el distrito está en un lugar cierto qué vamos a hacer vamos tocar o disuelto con 15 cuando tocamos su distrito con 15 vamos al que facer a mismo peraza meza en esa partida árbol vamos a hacer que de ser un

15 hasta un lugar cierto haciendo operación de más hippie fai que ya vimos una ola pasada normalmente comparamos con sencillos que con mayor mayor deseo cilios eurídice si colocamos con él y hacemos un mismo como si los de 15 15 16 y 12 mayores 16 tocamos con un mayor acuerdo 16 fica encima ahora pasemos un mismo con un próximo que sería un 15 no tengo más si les porque nosotros dos agência china ha fumado ser de labor está un hit normal toda esa parte de aquí un hip normal un próximo paso en toda ahora vamos

a comparar a raíz la verdad si vamos a tocar a raíz con un último elemento que sería 16 y tocar con un 11 pasemos hizo y hago ahora vamos comparar el y vamos a hacer con que 11 de esa comparamos el consejo silió sub 16 de un mayor o 16 of y ahora comparamos su once con sencillos un mayor entre el liceo 15 15 y 11 de ese y pronto acabó ahora tenemos un hit si no vamos a hacer eso con todos sus elementos que están en blanco aquí ahora mostró carlos 16 como 13 pasemos

que el 16 de esa cierto y ahora pasemos con 13 de esa una verdad si comparamos con zeus consejos cilios 13 15 14 un mayor eu 15 el ivai subir ahora comparamos su 13 con sencillos 13 11 y 12 está en un lugar cierto ok y continuamos ahora pasemos su 15 vamos tocar o 15 como 12 o 15 como 12 tocamos su 15 con 12 o 15 ya está en un lugar set 112 pasemos con calidez a va a decir vamos a comparar con sus vidrios 12 13 14 un mayor de 14 ó 14 va

a subir y después lo hacemos con que verificamos si 2 está en un lugar cierto está en un lugar secreto no pasemos más nada vean que aunque que está aconteciendo toda vez que estamos haciendo eso en sí ya tengo mapas y su vector que está ordenada la verdad suma parte 12 elementos está en un lugar se está continuamos a 414 comparamos un 14 con un 11 tocamos celis tocamos a raíz con mucho elemento de alborea thiago ahora tocamos en todo un 14 basificar en vario un cif y que encima pasemos udc pasemos de 011 comparamos

el y consejos vidrios 11 13 y 12 un mayor el 13 vamos tocar 3 1 11 y pronto egipto es a partir del gp esta serie porque el próximo elemento que vamos intentar tocar va a ser así sino con un último elemento de ese evento mostró claro 13 como 12 que tocamos su 13 como 12 y ahora pasemos concluidos de esa vamos a ver si precisa de ser no precisa de ser está correcto continuamos con el próximo elemento que 111 y 112 vamos a tocar los 12 con 11 pronto tocamos 11 verificamos y 11 está

en un lugar sexto tenemos ahora apenas un elemento en esa árbol y él está en un lugar cierto por fin entonces uno se va a ser un primer elemento de acción que fue haciendo esas operaciones la gente consiguió ordenar vectores tratamos 11 12 13 14 15 16 28 26 aquí vemos a comentó un peso del código del hip hop lo que que elige serviles recibe un vector a la cantidad y elementos que tenga ese vector el primero paso va a construir un hippy dentro del rival montar uji pico con base en un vector desordenado esa

operación ya fue vista en aula anterior el siguiente paso va a ser para cada uno de los elementos desde a posición n hacia posición 2 agency vai facer a truck alemnán de raíz con último elemento de hippie pero aquí estamos haciendo exactamente esa troca estamos tocando la posición a primera posición a raíz con un último elemento de un hippie el próximo paso es disminuir la cantidad de elementos que tengo hippy en mi web pues se me agoté en el tamaño de un hippie y finalmente o que facemos janier un hippie fa siendo más hippie fai

llamando un maxi hai que la gente vio nada o la pasada el ibarra severo electoral a cantidades y elementos que en ese hippie que m&a posición que está dejada que en ese caso de la posición que el ifai tentar a fumar para hacer con que de esa hacia posición cierta veamos cuánto que consume de tiempo este algoritmo no la pasada ya vimos que wilt más que un método que construir un hippie él y con su meta de n aquí alineados y eta de un ok la línea 3 en un para desde nt2 el a la

orden en este adn la línea 4 más vez que la está dentro de ese para la línea 3 ela también consume con su mitad en la línea 5 también de también la línea 6 un más hippie file vimos nada la pasada que el consomé o de login y como el hasta dentro de la línea 3 de la base repetida n veces por tanto consumo de tiempo la línea 6 va a ser n o de login si fuésemos a suma de todos esos elementos vamos a usted n o del lobby de n 634 n marzo se

dice a dench y falsas con chinas eso es lo mismo que falta que o nn login así vemos que un consumo de tiempos de shorts o te lo piden ok entonces vimos cómo usar una estructura de dados para proyectar un algoritmo de ordenación eficiente ese algoritmo de ordenación eficiente egipto tele consume o de n login pensamos un segundo algoritmo will short short también un algoritmo de ordenación el y también utiliza estrategia de división y conquista igual que inversor que vimos en algunas notas aulas el líder muy rápido en la mecha más lento no peor caso

vamos a ver cualquier caso de él porque te importante en un click short leblanc que china y la estrategia de división y conquista tiene varios pasos y un mapa de ese espacio 0 paso de divisa ese paso de división la parte más importante del algoritmo quick sort ok ok que sepáis de ese paso de división el y un vector que nos ha dado que sería un vector a de esa posición p atrapa a posición eje el particionado devolviendo un índice que tal que a de esa posición para esta posición que menos un menor o igual

a una posición que y eso es menor que a una posición que maestro atea posición efe una verdad que estamos consciente estamos encontrando un elemento de que lo que todos sus elementos que estén en un lado izquierdo son son menores o iguales y todos los elementos que están en un lado directos son mayores a ese elemento que fija como solar así entre esas dos partes es llamado de pívot lento y si es que un elemento que está en la posición que directora el llamado de pívot la escola de su pib es súper importante para el

buen desempeño su algoritmo quick son existen varias opciones proceso encontrar los libros que algunos de ellos vamos a escoger como pib o un primero elemento del vector otros son mostrar que vos y también ser escogido último elemento del vector hoy y también ser escogido como vivo o elemento de un medio del vector o porque ser escogido también aleatoriamente a esas aulas que vamos a escoger en esas aulas se fue mostrar como que hacen si faith particionamiento usando un último elemento de vector tomamos precisar pero quick sort de un algoritmo que se llama partición ok que

le vais a hacer exactamente qué vale ya antes en el bay dividir vector aunque un vector de peaje aunque el líder ball de una posición que un índice que aunque un vector en esa posición en mayor o igual a todos sus elementos que están en un lado izquierdo y menor a todos los elementos que están un lado directo yo vivo que vamos a escoger como yo ley será último elemento del vector entonces vamos aquí un ejemplo supone que tenemos ese vector aquí bryant que es desea posición para la posición en el port de balés 5

5 6 7 y 8 no olvidéis nuestra posición 5 ante posiciones por ejemplo en ese vector tenemos un siguientes números 46 y 22 40 y 56 34 42 vamos a escoger con motivo último elemento que sería 42 el precisó de un algoritmo que fue a su siguiente que coloque todos los elementos que son menores iguales a 42 del lado izquierdo y es que son mayores de un lado directo en todos resultados va a ser lo siguiente en un lado izquierdo y tengo todos los menores que 42 entonces tengo 22 40 y 34 en un lado

directo yo tengo todos sus mayores que 42 que serían 46 y 56 y ahora vamos ver como que ese algoritmo cómo sería ese algoritmo paso a paso podemos crear dos variables y j y va a comenzar una posición antes de inicio del vector cuyo está va a comenzar en la primera posición del vector y vamos colocarla varias veces su valor 42 que ser yo vivo no existe mos último elemento del vector que en este caso 42 que vamos a hacer vamos comparar lo que está en la posición yo está con ese 6 y preguntamos 46

es mayor que 42 si en todo avanzamos suyo está ok y ahora preguntamos 22 es mayor que 42 en este caso no sé cuándo respuesta de no vamos tocar o elementos de posición y maíz o como elemento en la posición j osé llamamos tocar o 46 y con un 22 y verificar entonces 22 y 46 y avanzamos suyos set y ahí continuamos ahora vamos a comparar lo que está en la posición yo está como si preguntamos 40 mayor que 42 no nos vamos tocar la posición y my zoom con elementos que están a posición yo

tanto vamos tocar y agora un 46 y con 40 falsificar entonces 22 40 46 y avanzamos y jot continuamos haciendo la misma pregunta aunque está en la posición j es mayor que 42 ok avance avanzamos porque esta es la posición yo está en mayor que 42 no es lo que vamos a hacer vamos tocar con un elemento que está en la posición y más bien que un elemento que está en la posición y más húmedo 46 centavos tocar un 34 con 46 y five y calentó 22 40 34 56 46 42 y avanzamos un short

shelton leigh anne ese proceso ok ok que tenemos a thiago ahora si vos eso observa lo que estamos haciendo estamos dejando todos los elementos que son menores o iguales a 42 del lado izquierdo hacia posición y están todos sus menores la posición y mainz zoom para french y estamos mayor ser en este caso de ok entonces finalmente qué vamos a hacer como yo te llevo activo final del vector lo que vamos a hacer es tocar o elemento que está en la posición y máis un elemento que está la posición y mais unos 56 con el

elemento que está en la posición yo te lo vamos tocar 42 con 46 y conseguimos lo que queríamos hacer dividir un vector en dos partes dado que los elementos que están un lado izquierdo son menores iguales que el pib los elementos que están un lado directo son mayores y mayores que pipo ser luego de ser para vos es elaborar en ese algoritmo si vos es quisieran dar un moldeada en ese algoritmo pues sin encontrar ese link que aquí pues es el mostrado que es ese algoritmo que mostré aquí un funcionamiento del inah verdad si no

mostré ups eurocódigo porque si no para vos es elaborar el post-it ser mostrado que un consumo de tiempo de ese algoritmo que detallen si no se salieron el ipp visita cada elemento de un vector más beige o en total y de tarde y aquí tenemos en todo el quick short o cuixart eligiese de un vector a él ejerce la posición inicial p la posición final si p menor a efe sesión si existen elementos en ese sector aunque el vais a hacer lo primero que voy a hacer particionar un vector nos va a llamar ese método

partición a como rectora posición pedía pues la posición final efe y ese partición y va a devolver la posición que hoy y debería estar vivo se asentó si ejecutamos hizo de ahí después de ejecutar la línea 2 es que para mostrar ese resultado de aquí o 42 en un lugar cierto 22 40 y 34 en un lado izquierdo los mayores 46 56 mi lado directo a postizo cuando ejecutamos llamamos recursiva mente un quick short vamos a llamar a gurú quick short lo que hace que el 42 está en un lugar 71 precisó más llamar para

hacer nada con 42 ó 42 están la posición cierta aunque tengo que falsear tengo que sumar en esta partido vector ordenan a verdad y esa parte del vector y eso que está siendo feito en la línea 3 una línea 3 llamamos su quick short o 6 estamos hablando ordenó de héctor desde la posición p a esta posición que menos un sdk posición que sembrando y son esa sequía posición de donde hay a fumar desde exposición p alta posición que menos está una línea 4 que quizá se va a llamar también un quick shorts tomamos primero

pero qué acontece después ejecutar la línea a línea trace usa elementos como ser ordenados y ahora cuando llamemos quick short desde posición quema y zoom hasta posiciones geba y será una desaparición vector 40 56 es ordenado o para intentar original de nov y por fin entonces tenemos un uso vector ordenado completamente co que un consumo de tiempo de ese algoritmo a línea aún consume teta de un alineados el hacha falamos que la consume teta de en ágora que acontece con la línea 34 en las va a depender la posición de particionamiento que fue feito política

por ejemplo dos elementos del lado izquierdo y vinci elementos en un lado directo o cinco elementos del lado izquierdo y 16 elementos en un lado directa y todo depende de oye que le consiguió colocar o elemento vivo vamos a amar que el ítem como su porque el ítem cada elementos un lado izquierdo por tanto el ifai tenemos acá más un un lado directo por tanto a línea a línea 3 va a consumir té de acá pues existen cada elemento su lado izquierdo la línea 4 va a consumir de adn - caminos zoom pues existen en

el camino son elementos en un lado si fuésemos asoma de todo hizo como usted que hizo date de acá más de dn caminos un más de adn maison como vimos aquí entonces y si alguien se quiere resolver esa recurrencia así en chivay tener que resolver vamos a encontrar resultados diferentes dependiendo de la posición que que fue encontrada y ahí vamos tener un peor caso un mejor caso un caso más si pasamos todas esas cuentas vamos a ver que no vio el caso o algoritmo quick son escuadra a chico tal caso por ejemplo el y daisy

0 elementos no lado izquierdo y en el menos un elemento anulado directo está o un contrario el líder n menos uno en un lado izquierdo y cero elementos en un lado directo entonces el peor casos algoritmo cursor en la cuadra chico no mayor caso o cuixart de tvn lo viene ahí el consumo de tiempo me dio una media un cursor el 30 de enero viene la verdad su peor caso acontece pocas veces puede ser demostrado y es todo este algoritmo de aquí a un algoritmo considerado eficiente tengo un peor caso marcelo acontece pocas veces por

esa forma nos habla número 8 del proyecto y análisis de algoritmos espero que posees tenían gustado y otra prosa [Música] 2 [Música] [Música] [Música] ah