Created
August 12, 2020 11:39
-
-
Save Dellos7/5abc86094e88c92c3e3a3025cfb584de to your computer and use it in GitHub Desktop.
Algoritmo Quick Sort en C++, escogiendo como pivote el elemento central del array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <typename T> | |
class OrdenadorQuicksort: public Ordenador<T>{ | |
void ordenar( vector<T> &lista ){ | |
ordenar( lista, 0, lista.size()-1 ); | |
} | |
// Quicksort sin utilizar arrays adicionales y eligiendo el elemento central para el pivote | |
void ordenar( vector<T> &lista, int posIni, int posFin ){ | |
if( posIni < posFin ){ | |
int posPivote = (posIni+posFin)/2; // Cogemos el del medio | |
int i = posIni, j = posFin; | |
T pivote = lista[posPivote]; | |
// Si quedan elementos a la derecha que sean menores o iguales que el pivote, insertarlos antes del pivote | |
i = posPivote+1; | |
while( i <= posFin ){ | |
if( lista[i] <= pivote ){ | |
// Ponemos el elemento menor en la posición del pivote | |
lista[posPivote] = lista[i]; | |
// Ponemos el pivote 1 posición más a la derecha de la que tenía | |
lista[i] = lista[posPivote+1]; | |
lista[posPivote+1] = pivote; | |
posPivote++; | |
} | |
i++; | |
} | |
// Si quedan elementos a la izquierda que sean mayores que el pivote, insertarlos después del pivote | |
j = posPivote-1; | |
while( j >= posIni ){ | |
if( lista[j] > pivote ){ | |
// Ponemos el elemento mayor en la posición del pivote | |
lista[posPivote] = lista[j]; | |
// Ponemos el pivote 1 posición más a la izquierda de la que tenía | |
lista[j] = lista[posPivote-1]; | |
lista[posPivote-1] = pivote; | |
posPivote--; | |
} | |
j--; | |
} | |
// Ordenamos el array izquierdo del pivote | |
this->ordenar( lista, posIni, posPivote-1 ); | |
// Ordenamos el array derecho del pivote | |
this->ordenar( lista, posPivote+1, posFin ); | |
} | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Animación del algoritmo en vídeo: https://youtu.be/Y28K-lfhcWM