Quicksort

50 %
50 %
Information about Quicksort
Education

Published on March 21, 2014

Author: juanpaulchavez

Source: slideshare.net

Description

Presentacion sobre el ordenamiento Quicksort para la clase de Estructura de datos con el maestro Galves

Integrantes del Equipo: Chávez Sierra Juan Paúl. Cristín Esperano Luis Enrique. Leyva Bujons Ivan Alberto. López Alva Luis Antonio. Materia: Estructura de Datos. Maestro: M.C. Gerardo Gálvez Gámez.

Su autor es el científico británico en computación Charles Antony Richard Hoare. Basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. El método de ordenamiento Quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna. También conocido con el nombre del método rápido y de ordenamiento por partición.

Lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote (o comodin) que nos permitira segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izquierda. Al finalizar el algoritmo, nuestros elementos estan ordenados.

Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja. Este método es una mejora sustancial del método de intercambio directo.

 http://www.youtube.com/watch?v=mRhy4wTlg0s&list=LLU8Ow0Ep3wZO9XkVj8ih _tA&feature=mh_lolz

pasada #1 5 2 7 3 1 8 2 6 9 pivote=5 5>9 no 5>6 no 5>2 si intercambio 2 2 7 3 1 8 5 6 9 5<2 no 5<7 si intercambio 2 2 5 3 1 8 7 6 9 5>8 no 5>1 si intercambio 2 2 1 3 5 8 7 6 9 5<3 no 2 2 1 3 5 8 7 6 9 fin pasada #1

pasada 4 1 2 2 3 5 8 7 6 9 pivote grupo 2 = 8 8>9 no 8>6 si intercambio 1 2 2 3 5 6 7 8 9 8<7 no fin pasada #4 grupo 4 1 2 2 3 5 6 7 8 9 pasada #5 pivote grupo 6>7 no 4 = 6 fin pasada #5 fin metodo Arreglo 1 2 2 3 5 6 7 8 9 Ordenado

public void Quicksort(int[] Arreglo, int PrimerElemento, int UltimoElemento) { int Aux, Pivote; this.Arreglo=new int[Arreglo.length]; int Izquierda=PrimerElemento; int Derecha=UltimoElemento; do { Pivote=Izquierda; while(Arreglo[Pivote] < Arreglo[Derecha]) { Derecha--; } Aux = Arreglo[Pivote]; Arreglo[Pivote] = Arreglo[Derecha]; Arreglo[Derecha] = Aux; Izquierda++; while(Arreglo[Pivote] > Arreglo[Izquierda]) { Izquierda++; } Aux = Arreglo[Pivote]; Arreglo[Pivote] = Arreglo[Izquierda]; Arreglo[Izquierda] = Aux; Derecha--; }while(PrimerElemento <= UltimoElemento); if(PrimerElemento < Derecha) { Quicksort(Arreglo, PrimerElemento, Derecha); } if(Izquierda < UltimoElemento) { Quicksort(Arreglo, Izquierda, UltimoElemento); } this.Arreglo = Arreglo; } NUESTRA PROPUESTA DE CODIGO.

 El método de ordenamiento Quicksort es un método muy rápido ya que divide al arreglo en pequeños subgrupos y los va comparando hasta reducir los subgrupos a la mínima cantidad evitando hacer comparaciones innecesarias y pasadas de más.

 http://www.angelfire.com/wy2/est_info/quicksort.html  http://www.estructuradedatos.galeon.com/metodoquicksort.htm  Algoritmos se Ordenamiento, Fernando A. Lagos (Ensayo,2007).  Estructura de Datos, Osvaldo Cairo, Ed. Mc Graw Hill, tercera edición.

 Espacio para preguntas y respuestas.

Add a comment

Related presentations

Related pages

Quicksort – Wikipedia

Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip ...
Read more

Quicksort - Studiengang Angewandte Informatik

Der Quicksort-Algorithmus [Hoa 62] ist eines der schnellsten und zugleich einfachsten Sortier­verfahren. Das Verfahren arbeitet rekursiv nach dem Divide ...
Read more

Quicksort

Wir empfehlen: Quicksort "Grundlagen der Programmierung" Folie 1 1. Geschichte und Hintergründe des Sortierproblems - erste Entwicklungen in Amerika ...
Read more

Informatik » Sortieren durch Zerlegen / Quicksort

Sortieren durch Zerlegen / Quicksort Ein Sortierspiel. Anton, Britta, Carlo, ... wollen sich der Größe nach in einer Reihe aufstellen. Zuerst werden alle ...
Read more

QuickSort |

QuickSort. Die folgende Prozedur sortiert ein Integer-Array, das der Routine als Parameter übergeben wird, mit dem QuickSort-Verfahren:
Read more

Algorithmensammlung: Sortierverfahren: Quicksort ...

Quicksort . Quicksort wird gemeinhin als das beste Sortierverfahren in der Praxis betrachtet. Während seine Laufzeit im schlechtesten Fall beträgt ...
Read more

Quicksort - Allgemeine und spezielle Sortieralgorithmen ...

Quicksort; Quicksort gehört zur Gruppe der asymptodisch optimalen Sortieralgorithmen. Obwohl er im schlechtesten Fall keine besonders gute Laufzeit ...
Read more

Quicksort - Wikipedia, the free encyclopedia

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array ...
Read more

QUICKSORT (Java, C++) | Algorithms and Data Structures

Illustrated quicksort explanation. How to choose a pivot value? Partition algorithm description. Complexity analysis. Java and C++ implementations.
Read more

Algorithmen und Datenstrukturen in C/ Quicksort ...

Vorstellung . Quicksort ist ein rekursiver Sortieralgorithmus, der die zu sortierende Liste in zwei Teillisten unterteilt und alle Elemente, die kleiner ...
Read more