Transparencias del Método de Clasificación Quicksort

  • Published on
    13-Jun-2015

  • View
    1.284

  • Download
    2

Transcript

<p>ALGORITMOS DE CLASIFICACIN INTERNA 1) nsercin directa. Mejoras: I 1) nsercin Binaria I 2) eleccin directa S 2) ntercambio directo (Burbuja) I 3) nsercin con incrementos decrecientes (Shell) I 4) todo del montculo (Heapsort) M 5) todo rpido (Quicksort) M</p> <p>QUICKSORT = METODO DE ORDENAMIENTO RPIDOEl ordenamiento rpido (quicksort en ingles) es un algoritmo basado en la tcnica de divide y vencers, que permite, en promedio, ordenar n elementos en una complejidad de n log n. Es la tcnica de ordenamiento ms rpida conocida.</p> <p>Fue Charles Antony Richard Hoare un cientfico Britnico en computacin, quien en 1960 invento el mtodo de ordenacin mas rpido, Quicksort,. Tambin se le conoce por el desarrollo de la Lgica de Hoare, y el lenguaje formal CSP.</p> <p>El algoritmo fundamental es el siguiente :1 Elegimos un elemento del vector, puede ser cualquiera. Lo llamaremos elemento de divisin o pivote.</p> <p>Pivote o elemento de divisin</p> <p>La forma ms efectiva es coger como pivote el elemento intermedio</p> <p>2 Buscamos la posicin que le corresponde en el vector al pivote y ordenamos los elementos de la lista de manera que a lado queden los menores y a otro los mayores.</p> <p>Menores PIVOTE</p> <p>Mayores</p> <p>3 Realizamos esto de forma recursiva para que cada subvector mientras este tengan un largo mayor que 1</p> <p>EJEMPLO.QUICKSORTITERATIVO</p> <p>8cima=0izq=1 inf=1</p> <p>1</p> <p>4</p> <p>9</p> <p>6Pivote=6</p> <p>3</p> <p>5</p> <p>2</p> <p>7</p> <p>0der=10 sup=10</p> <p>0izq=1</p> <p>1inf=2</p> <p>4</p> <p>9</p> <p>6Pivote=6</p> <p>3</p> <p>5</p> <p>2</p> <p>7sup=9</p> <p>8der=10</p> <p>0izq=1</p> <p>1</p> <p>4inf=3</p> <p>9</p> <p>6Pivote=6</p> <p>3</p> <p>5</p> <p>2</p> <p>7sup=9</p> <p>8der=10</p> <p>0izq=1</p> <p>1</p> <p>4</p> <p>9inf=4</p> <p>6Pivote=6</p> <p>3</p> <p>5</p> <p>2</p> <p>7sup=9</p> <p>8der=10</p> <p>EJEMPLO.QUICKSORTITERATIVO</p> <p>0izq=1</p> <p>1</p> <p>4</p> <p>9inf=4</p> <p>6Pivote=6</p> <p>3</p> <p>5</p> <p>2sup=8</p> <p>7</p> <p>0der=10</p> <p>0izq=1</p> <p>1</p> <p>4</p> <p>2</p> <p>6Pivote=6 inf=5</p> <p>3</p> <p>5sup=7</p> <p>9</p> <p>7</p> <p>8der=10</p> <p>0izq=1</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3inf=6 sup=6</p> <p>6Pivote=6</p> <p>9</p> <p>7</p> <p>8der=10</p> <p>0izq=1</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3sup=6</p> <p>6Pivote=6 inf=7</p> <p>9</p> <p>7</p> <p>8der=10</p> <p>EJEMPLO.QUICKSORTITERATIVO</p> <p>0cima=1 Lim_izq=1 Lim_der=6</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3</p> <p>6izq=7 inf=7</p> <p>9Pivote=9</p> <p>7</p> <p>8der=10 sup=10</p> <p>0</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3</p> <p>6izq=7</p> <p>9Pivote=9 inf=8</p> <p>7</p> <p>8der=10 sup=10</p> <p>0</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3</p> <p>6izq=7</p> <p>8</p> <p>7sup=9 Inf=9</p> <p>9der=10 Pivote=9</p> <p>0cima=2 Lim_izq=7 Lim_der=9</p> <p>1</p> <p>4</p> <p>2</p> <p>5</p> <p>3</p> <p>6izq=7</p> <p>8</p> <p>7sup=9</p> <p>9der=10 Inf=10 Pivote=9</p> <p>Algoritmo Quicksort recursivoPROCEDIMIENTO quicksort (a: tipo_vector (E/S), izq: entero (E), der: entero (E))</p> <p>VAR i,j: entero x,w: tipo_elemento INICIO iizq jder xa [(izq+der)/2] Mientras (i</p>