ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
Laboratorio de Estructura de Datos ISWR453
Grupo GR3
Práctica No.: 4 (Semana 4)
Integrantes: Danny Cabrera, Marcela Montalvo, Kevin Rivadeneira
Tema: Métodos de Ordenamiento Interno
Fecha: 29/06/2020
1. OBJETIVOS
➢ Implementar el método de ordenamiento Quicksort y por inserción en el lenguaje de
programación java.
➢ Entender cómo funciona cada método.
2. MARCO TEORICO
Ordenamiento Por Inserción
El método de ordenación por inserción directa
consiste en recorrer todo el array comenzando
desde el segundo elemento hasta el final. Para cada
elemento, se trata de colocarlo en el lugar correcto
entre todos los elementos anteriores a él o sea entre
los elementos a su izquierda en el array.
El algoritmo para este método de ordenación es el
siguiente: inicialmente, se ordenan los dos
primeros elementos de una matriz, luego se inserta
el tercer elemento en la posición correcta respecto
a los dos primeros. A continuación, se inserta el
cuarto elemento en la posición correcta respecto a
los tres primeros elementos ya ordenados, y así
sucesivamente hasta llegar al último elemento de
la matriz. [1]
Figura 1 Diagrama de Flujo O. Inserción
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
Método Quick Sort
El método Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación
interna. Es también conocido con el nombre del método rápido y de ordenamiento por
partición.
Está 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. [2]
El funcionamiento del algoritmo sigue los pasos:
1. Elegir un elemento de la lista de elementos a ordenar, al
que llamaremos pivote.
2. Resituar los demás elementos de la lista a cada lado del
pivote, de manera que a un lado queden todos los menores
que él, y al otro los mayores. En este momento, el pivote
ocupa exactamente el lugar que le corresponderá en la lista
ordenada.
3. La lista queda separada en dos sublistas, una formada por
los elementos a la izquierda del pivote, y otra por los
elementos a su derecha.
4. Repetir este proceso de forma recursiva para cada sublista
mientras éstas contengan más de un elemento. Una vez Fígura 2 Fígura de Quiksort
terminado este proceso todos los elementos estarán
ordenados.
Es importante destacar que la eficiencia del algoritmo depende de la posición en la que termine
el pivote elegido.
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
3. PROCEDIMIENTO
Ejercicio 1. Ordenamiento por Inserción
Implementar un programa que permita ordenar un arreglo a través del ordenamiento por
inserción. Implementar los siguientes métodos: 1) imprimirLista, 2) OrdenarInsercion e 3)
Intercambiar.
CÓDIGO
package ordenamiento;
public class Ordenamiento {
public static int [] Ordenamiento(int A[]){
int p, j;
int aux;
for (p = 1; p < A.length; p++){
aux = A[p];
j = p - 1;
while ((j >= 0) && (aux < A[j])){
A[j + 1] = A[j];
j--;
}
A[j + 1] = aux;
}
return A;
}
public static void imprimirLista(int[] arreglo) {
for (int i = 0; i < arreglo.length; i++) {
System.out.print(arreglo[i] + " ");
System.out.println();
}
public static int [] Intercambiar(int[] arreglo, int i, int j) {
int temp;
temp = arreglo[i];
arreglo[i] = arreglo[j];
arreglo[j] = temp;
return arreglo;
}
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
public static void main(String[] args) {
int [] arreglo = {10,4,8,6,12,58,40,36,48,20};
System.out.println("Arreglo Ordenado \n");
imprimirLista(arreglo);
System.out.println(" \n");
System.out.println("Arreglo Ordenado por Insercion \n");
Ordenamiento(arreglo);
imprimirLista(arreglo);
System.out.println(" \n");
System.out.println("Arreglo Intercambiado \n");
Intercambiar(arreglo, 1, 6);
imprimirLista(arreglo); }
}
Resultado:
Ejercicio 2. Ordenamiento Quicksort Pivote central
Implementar un programa que permita ordenar un arreglo a través del ordenamiento QuickSort
(Pivote central). Implementar los siguientes métodos: 1) imprimirLista, 2) OrdenarQuickSort e
3) Intercambiar.
CÓDIGO
package Ejercicio2;
public class TestQuickCentral {
public static void main(String[] args) {
int arreglo[] = {10, 9, 3, 7, 2, 1, 4, 8, 0};
int primero = 0;
int ultimo = 8;
System.out.print("Lista Inicial: ");
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
imprimirLista(arreglo);
OrdenarQuickSort(arreglo, primero, ultimo);
System.out.print("Lista Ordenada Quicksort: ");
imprimirLista(arreglo);
public static void imprimirLista(int[] arreglo) {
for (int i = 0; i < arreglo.length; i++) {
System.out.print(arreglo[i] + " ");
}
System.out.println();
}
public static void OrdenarQuickSort(int arreglo[], int primero, int ultimo) {
int central, i, j;
int pivote;
central = (primero + ultimo) / 2;
pivote = arreglo[central];
i = primero;
j = ultimo;
do {
while (arreglo[i] < pivote) {
i++;
}
while (arreglo[j] > pivote) {
j--;
}
if (i <= j) {
Intercambiar(arreglo, i, j);
i++;
j--;
}
} while (i <= j);
if (primero < j) {
OrdenarQuickSort(arreglo, primero, j);
}
if (i < ultimo) {
OrdenarQuickSort(arreglo, i, ultimo);
}
public static void Intercambiar(int[] arreglo, int i, int j) {
int temp;
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
temp = arreglo[i];
arreglo[i] = arreglo[j];
arreglo[j] = temp;
}
}
Resultado
Ejercicio 3. Ordenamiento Quicksort Pivote inicial
Implementar un programa que permita ordenar un arreglo a través del ordenamiento QuickSort
(Pivote inicial).
CÓDIGO
public class Main3PivoteInicial {
public static void main(String[] args) {
int arreglo[] = {15, 7, 8, 2, 5, 0, 14, 1, 4, 9};
int primero = 0;
int ultimo = 9;
System.out.print("Lista Inicial: ");
imprimirLista(arreglo);
OrdenarQuickSort(arreglo, primero, ultimo);
System.out.print("Lista Ordenada Quicksort: ");
imprimirLista(arreglo);
}
public static void imprimirLista(int[] arreglo) {
for (int i = 0; i < arreglo.length; i++) {
System.out.print(arreglo[i] + " | ");
}
System.out.println();
}
public static void OrdenarQuickSort(int arreglo[], int primero, int ultimo) {
int i, j;
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
int pivote = arreglo[primero];
i = primero;
j = ultimo;
do {
while (arreglo[i] <= pivote && i < j) {
i++;
}
while (arreglo[j] > pivote) {
j--;
}
if (i < j) {
Intercambiar(arreglo, i, j);
}
} while (i < j);
arreglo[primero] = arreglo[j];
arreglo[j] = pivote;
imprimirLista(arreglo);
if (primero < j - 1) {
OrdenarQuickSort(arreglo, primero, j - 1);
}
if (j + 1 < ultimo) {
OrdenarQuickSort(arreglo, j + 1, ultimo);
}
}
public static void Intercambiar(int[] arreglo, int i, int j) {
int temp;
temp = arreglo[i];
arreglo[i] = arreglo[j];
arreglo[j] = temp;
}
}
Resultado
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
Ejercicio 4. Ordenamiento Quicksort
Implementar un programa que permita ordenar un arreglo a través del ordenamiento QuickSort
a través de cualquier otro método diferente a los vistos en clase.
Utilizando como pivote el ultimo valor.
TestQuickUltimo.java
package Ejercicio4;
public class TestQuickUltimo {
public static void main(String[] args) {
int arreglo[] = {10, 9, 3, 7, 2, 1, 4, 8, 0};
int primero = 0;
int ultimo = 8;
System.out.print("Lista Inicial: ");
imprimirLista(arreglo);
OrdenarQuickSort(arreglo, primero, ultimo);
System.out.print("Lista Ordenada Quicksort: ");
imprimirLista(arreglo);
public static void imprimirLista(int[] arreglo) {
for (int i = 0; i < arreglo.length; i++) {
System.out.print(arreglo[i] + " ");
}
System.out.println();
}
public static void OrdenarQuickSort(int arreglo[], int primero, int ultimo) {
int central, i, j;
int pivote;
pivote = arreglo[ultimo];
i = primero;
j = ultimo;
do {
while (arreglo[i] < pivote) {
i++;
}
while (arreglo[j] > pivote) {
j--;
}
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
if (i <= j) {
Intercambiar(arreglo, i, j);
i++;
j--;
imprimirLista(arreglo);
}
} while (i <= j);
if (primero < j) {
OrdenarQuickSort(arreglo, primero, j);
}
if (i < ultimo) {
OrdenarQuickSort(arreglo, i, ultimo);
}
public static void Intercambiar(int[] arreglo, int i, int j) {
int temp;
temp = arreglo[i];
arreglo[i] = arreglo[j];
arreglo[j] = temp;
}
Resultado
4. CONCLUSIONES Y RECOMENDACIONES
Quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna como
el de intercambio.
A pesar que el algoritmo minimiza las operaciones, este puede ser optimizado solo con la
elección del pivote. En el caso del pivote inicial o final, no siempre es una buena elección ya
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA DE SISTEMAS
INGENIERÍA DE SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN
que los elementos de la lista no se encuentran uniformemente distribuidos.
La elección del pivote es la parte crítica que determina la velocidad de ejecución del algoritmo,
donde la mejor opción es realizarlo con números aleatorios.
Es importante considerar los casos de elección del pivote, pues una mala elección puede
interferir en la velocidad y tiempo de ejecución, delimitando la eficiencia del algoritmo.
Bibliografía
[1] unknow, «Open Source source,» 2019. [En línea]. Available:
https://javaparajavatos.wordpress.com/2017/04/29/metodo-de-insercion/. [Último acceso: 28 06 2021].
[2] cidecami.edu, 2020. [En línea]. Available:
http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro9/mtodo_quick_sort.html. [Último acceso: 28 06
2021].
