CAPÍTULO 5: ALGORITMOS DE SORTEO AVANZADOS

En el capítulo 4, introducimos algoritmos que sortean n números reales en una complejidad de tiempo entre Ω(n) y O(n2).

En este capítulo introduciremos 3 algoritmos avanzados, de los cuales uno de ellos, MergeSort no sortea in place [1], con un tiempo asintótico de Θ(n log n).

HeapSort hace uso de un Heap para sortear n números in place en Θ(n log n) y QuickSort, que igualmente actúa in place, pero para sortear n números tarda en worst case O(n2).

QuickSort

Pese a tener una complejidad de tiempo O(n2), QuickSort es un algoritmo muy popular y en varios casos la opción más practica puesto que es muy eficiente en su caso medio (Average Case) y los factores escondidos en esa complejidad son bastante pequeños, es por esto por lo que QuickSort tiene ventaja como algoritmo in place.

El principio de QuickSort lo resumimos de la siguiente manera:

1. Escoger un elemento como pivot. (el pivot será el elemento que se sorteara en cada llamado de la función preparePartition(…), en nuestra implementación escogemos el último elemento y recorremos el array desde atrás, pero también se puede escoger cualquiera, de hecho para que el algoritmo funcione óptimamente, debería escogerse un elemento aleatorio para cada llamado de la función preparePartition(…))  
2. Partir el array en 3 partes: Primera parte donde todos los elementos son menores que el pivot (sin importar el orden). Segunda parte donde se encuentra únicamente el pivot ya sorteado. Tercera parte donde todos los elementos aquí son más grandes o iguales al pivot.
   
3. Ahora aplicamos recursivamente Quicksort de nuevo para la primera y la tercera parte.
   

Entendiendo PreparePartition(...)

Esta función es la parte más importante del algoritmo y se llamara para cada parte del array recursivamente mediante la función quicksort(…):

• Escogemos el último elemento del array como pivot. (Línea 10)
• Nuestro pointer p de ayuda lo colocamos a una posición después del último elemento. (Línea 12)  
• Recorriendo de derecha a izquierda el array para cada elemento:
  Si este elemento es mayor o igual que nuestro pivot, corremos nuestro p de ayuda una posición a la izquierda e intercambiamos este elemento con el elemento a donde apunta nuestro p.
  
• Después de recorrer toda esa partición, intercambiamos el último elemento (nuestro pivot) con el elemento apuntado por p.
  

Implementación de QuickSort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

namespace QuickSort {
		void swap(int& a, int& b) {
			int h = b;
			b = a;
			a = h;
		}

		void preparePartition(int a[], int f, int l, int& p) {
			// Use the last element as Pivot-Element
			int pivot = a[l];
			//set the pointer to the next to the last element
			p = l + 1;
			//go throgh the array backwards
			for (int i = l; i >= f; i--) {
				if (a[i] >= pivot) {
					p--;
					swap(a[i], a[p]);
				}
			}
			// Pivot on the rigth Pos.
			swap(a[l], a[p]);
		}

		void quicksort(int a[], int f, int l) {
			int part;
			if (f < l) {
				preparePartition(a, f, l, part);
				quicksort(a, f, part - 1);
				quicksort(a, part + 1, l);
			}
		}
	}

Ejemplo: Animación sorteando con QuickSort

Análisis de la complejidad de QuickSort

El número de pasos que efectúa QuickSort está ligado a la elección del elemento pivot.

Continua en la parte 2 siguiendo este enlace:

https://thewhitecode.com/blog/3913

___________

[1] Un algoritmo sortea In place, cuando solo un numero constante de elementos del input array son sorteados fuera de este.

[2] El elemento con el índex más alto en el array entre los valores que aún no están sorteados.

[3] Al colocar un nuevo elemento en la raíz, tenemos que asegurarnos que el Heap siga siendo válido, bajando por el árbol recursivamente y acomodando este valor en una posición donde se cumplan las condiciones del Heap, en este caso MaxHeap.

[4] Largest permanece como índice intacto, pues la función swap cambia solo el elemento que está bajo este índice.  

El Manual de los algoritmos y las estructuras de datos.

Este capítulo ha sido solo uno de 9 capítulos en total del libro.

Descarga el manual directamente desde este enlace:

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatos

¿Te ha gustado?, quisieras acceder a más contenido?