Skip to content

Instantly share code, notes, and snippets.

@tiagox
Created April 21, 2017 15:34
Show Gist options
  • Save tiagox/5918dd6583e2529cdb076672700fecd9 to your computer and use it in GitHub Desktop.
Save tiagox/5918dd6583e2529cdb076672700fecd9 to your computer and use it in GitHub Desktop.
Implementación de QuickSort en Java
public class Ordenador {
public static void quickSort(int[] lista) {
quickSort(lista, 0, lista.length - 1);
}
private static void quickSort(int[] lista, int izquierda, int derecha) {
int pivote = lista[izquierda];
int i = izquierda;
int j = derecha;
while (i < j) {
while (lista[i] <= pivote && i < j) {
i++;
}
while (lista[j] > pivote) {
j--;
}
if (i < j) {
intercambiar(lista, i, j);
}
}
lista[izquierda] = lista[j];
lista[j] = pivote;
if (izquierda < (j - 1)) {
quickSort(lista, izquierda, j - 1);
}
if (j + 1 < derecha) {
quickSort(lista, j + 1, derecha);
}
}
private static void intercambiar(int[] lista, int a, int b) {
int aux = lista[a];
lista[a] = lista[b];
lista[b] = aux;
}
}
import org.junit.Assert;
import org.junit.Test;
public class OrdenadorTest {
private boolean estaOrdenado(int[] lista) {
boolean estaOrdenado = true;
for (int i = 1; i < lista.length; i++) {
estaOrdenado = estaOrdenado && (lista[i - 1] <= lista[i]);
}
return estaOrdenado;
}
@Test
public void probarUnaListaOrdenada() {
int[] lista = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Ordenador.quickSort(lista);
Assert.assertTrue(estaOrdenado(lista));
}
@Test
public void probarUnaListaInvertido() {
int[] lista = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
Ordenador.quickSort(lista);
Assert.assertTrue(estaOrdenado(lista));
}
@Test
public void probarUnaListaZaraza() {
int[] lista = { 3, 2, 1, 5, 4, 24, 76, 8, 34, 5234, 356, 467, 234, 234, 3567, 467, 2345, 234, 235, 357, 245,
234, 234, 234, 567, 347, 23, 2134, 245, 357, 457, 234, 234, 245, 356, 457, 2435, 51234, 2345, 346, 457,
346, 234, 234, 246, 3457, 24, 5234, 234, 234 };
Ordenador.quickSort(lista);
Assert.assertTrue(estaOrdenado(lista));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment