¡Hola! En este vídeo aprenderemos el método de ordenamiento de Quick Sort
QUICK SORT
En este caso vamos a utilizar una lista doblemente enlazada.
Nuestro Nodo está compuesto por:
Un dato (tipo a escoger)
Un dato entero que nos servirá como un booleno y nos indicará que el nodo está ordenado en la lista cuando sea 1 sino 0, llamado orden
Dos apuntadores Nodo que nos señalará uno al nodo anterior y el otro al nodo siguiente
Declaramos dos apuntadores de tipo Nodo que nos ayudarán a identificar el inicio y el final de nuestra lista
Nota: Cuando se cree un nodo nuevo en su función insertar no olvidar que el nuevo nodo en su parte de orden es igual a 0.
Función quickSort
Declaramos una función de tipo void y como parámetros dos apuntadores de tipo Nodo,llamados aux y aux2. En un principio desde la función main,cuando se llame a la función se debe mandar los apuntadores inicio y final, en ese orden.
Primero declaramos dos datos enteros:
temp - Nos servirá para el intercambio de datos
b - Variable que nos servirá como booleano, donde 1 significa que se hizo un intercambio de datos o los puntadores aux y aux2 apuntan al mismo nodo. Este variable en un inicio es igual a 0.
Dentro de un while con condición: aux y aux2 sean diferentes y es donde vamos a hacer todos los intercambios.
Nota: Hay que tener en cuenta que en quick sort podemos elegir cualquier dato como pivote, en este caso cuando se analize una lista el pivote siempre va a ser aux.
Posición de los apuntadores al inicializar la función
Vamos a inicializar un while con condición b==0, este while se va a romper cuando se haga un intercambio o, aux y aux2 sean iguales.Dentro de este while, con un if se hace la condición que aux y aux2 sea diferentes, en caso de ser falso b=1 sino abrimos otro if con la condición que aux en su parte de dato sea mayor igual que aux2 en su parte de dato, en caso de ser falso aux2 se recorre a su parte de anterior, sino se hace el intercambio de datos y punteros como muestra la imagen.
Manera gráfica del intercambio. En la primera lista se ve el intercambio de datos y en la segunda el intercambio de apuntadores
Cuando se hace un intercambio nuestro booleano “b” se convierte a 1 y ahora hacemos el mismo proceso solo que comparando que aux2 en su parte de datos sea mayor al pivote.
Parte de código donde se hace los intercambios, se haría la misma forma para cuando aux2 este del lado izquierdo del pivote solo que se compara que el dato de aux sea menor que el dato de aux2.
Cuando un elemento ya esté en su lugar, a su parte de orden se le asigna un 1.
Ahora para la partición del lado derecho e izquierdo del nodo ordenado vamos a declarar 4 apuntadores de tipo de Nodo:
in2 - Se iguala a aux, va a ser el inicio de las listas que están al lado izquierdo de elemento ordenado.
ant - Se iguala al aux en su parte de anterior,va a ser el final de las listas que están al lado izquierdo del elemento ordenado.
sig - Se iguala al aux en su parte de siguiente,va a ser el inicio de las listas que están al lado derecho del elemento ordenado.
fin2 - Se iguala al aux en su parte de anterior,va a ser el final de las listas que están al lado izquierdo del elemento ordenado.
Posición inicial de los apuntadores
Posición de los apuntadores al empezar a ordenar las listas de la derecha e izquierda
Tenemos que ir recorriendo los apuntadores in2 y fin2 hasta encontrar NULL o un elemento ordenado. De forma recursiva vamos a llamar otra vez la misma función (primero las listas de la izquierda), pasándole como parámetro cuando hablamos de las listas de la izquierda de nodo ordenado los apuntadores in2 y ant, y para las listas de la derecha sig y fin2.
Recorrimiento de los apuntadores in2 y fin2.
Ordenar listas de la izquierda y lista de la derecha
Comentários