Quick Sort en Java / Python

1) Defina una sintaxis para expresar en pseudocódigo​ las siguientes operaciones:

-Asignación
La manera simple será con ->, por ejemplo:

x -> 1

En este caso se está asignando el valor entero 1 a la variable x.
La asignación múltiple se realizará de la siguiente forma:

x, y -> 1, 3

Finalmente se asigna 1 a la variable x y 3 a la variable y.

-Repetición mientras se cumple condición
Similar a C, de la siguiente manera:

while (condición de parada)
{
   sentencias del ciclo
}

Por ejemplo:

a -> 0                           // definimos el contador en 0          
while (a < 5)                    // la condición es hasta que a llegue a 5
{
   a++                           // aumenta el contador para que imprima desde 1
   print("conteo: %d \n", a)     // imprime el valor
}

-Iteración sobre una secuencia
Similar a C, de la siguiente manera:

for (expresión de inicio, condición de parada, incremento)
{
   sentencias del ciclo
}

Por ejemplo:

for (a -> 1, a < 5, a++)      // definimos el contador en 1, la condición es hasta que el
{                             // valor a llegue a 5 y aumenta el contador en cada iteración
   print("conteo: %d \n", a)  // imprime el valor
}

2) Para el siguiente problema escriba una solución utilizando lenguaje de alto nivel, diagrama de flujo, pseudocódigo​, Java y Python.

Problema: Se tienen 2 listas ordenadas ascendentemente y se desea crear una nueva lista que contenga todos los valores de ambas listas y que también este ordenada. Por ejemplo: lista1=[2,8,12,20], lista2=[10,11,12,15,30,35], resultado=[2,8,10,11,12,12,15,20,30,35]

Palabras

En breves instrucciones, lo primero en hacer sería unir lista1 y lista2 en una lista final para luego proceder a ordenarla.
Dado que ya tenemos una sola lista, lo que haremos es seguir el algoritmo Quick Sort en dónde tomaremos un pivote(en Java son 2, el primer elemento y el úlitmo mientras que en Python sólo el primero) para a partir de este iterar la lista e ir comparando. Si el elemento sobre el que se itera es menor que el pivote, entonces se ubica a la izquierda. En cambio, si el elemento es mayor, se ubica a la derecha. Si tienen el mismo valor no importa en que lado se ubique aunque depende de la implementación.
Finalmente lo que vuelve óptimo este algoritmo es que se usa recursividad para ordenar de vuelta y asi lograr el objetivo.

Diagrama de flujo

Pseudocódigo

lista1 = [2,8,12,20]
lista2 = [10,11,12,15,30,35]

listaFinal = []

funcion merge(list1 -> lista de enteros 1, list2 -> lista de enteros 2, 
tmp -> lista de enteros final) {
    while (list1 & list2 no esten vacías) {
        e1 -> extraer elemento de list1        //al extraer que sea con 
        e2 -> extraer elemento de list2        //pop, asi se limpian las listas
        if (e1 > e2) {
            agregar e2 a tmp
        } else if(e1 == e2) {
            agregar e1 a tmp
            agregar e2 a tmp
        } else {
            agregar e1 a tmp
        }
    }
}

funcion makeList(lista de enteros 1, lista de enteros 2, lista de enteros final) {
    for (i -> 0, i < tamaño de lista de enteros 1, i++) {
       agregar elemento de la lista de enteros 1 en la lista de enteros final
    }

    for (i -> 0, i < tamaño de lista de enteros 2, i++) {
       agregar elemento de la lista de enteros 2 en la lista de enteros final
    }

}

funcion quickSort(lista de enteros, indice inicial, indice final) {
   if (indice inicial < indice final) {

     pivot -> elemento del indice final de la lista de enteros
     index -> indice inicial - 1

     for (i -> indice inicial, i < indice final, i++) {

       if (elemento del indice inicial de la lista de enteros <= pivot) {
        tmp -> ++index,                     
        tmp1 -> elemento de list en indice i
        set en indice i de list el valor del indice tmp de list     
        set en indice tmp de list el valor tmp1          
      }

     }

    tmp -> ndex + 1,                     
    tmp1 -> elemento de list en indice last
    set en indice last de list el valor del indice tmp de list  
    set en indice tmp de list el valor tmp1          

    quickSort(list, first, index)
    quickSort(list, index + 1, last)

   }
}

makeList(lista1, lista2, listaFinal)

quickSort(listaFinal, 0, tamaño de listaFinal - 1)

Java

public static void merge(ArrayList<Integer> listA, ArrayList<Integer> listB, ArrayList<Integer> finalList){
  for (int i: listA) {
    finalList.add(i);
  }

  for (int i: listB) {
    finalList.add(i);
  }
}

public static void sortT(ArrayList<Integer> list, int first, int last) {
  if (first < last) {
    int pivot = list.get(last);
    int index = first - 1;
    for (int i = first; i < last; i++) {
      if (list.get(i) <= pivot) {
        int tmp = ++index;
        int tmp1 = list.get(i);
        list.set(i, list.get(tmp));
        list.set(tmp, tmp1);
      }
    }

    int tmp = index + 1;
    int tmp1 = list.get(last);
    list.set(last, list.get(tmp));
    list.set(tmp, tmp1);

    sortT(list, first, index);
    sortT(list, index + 1, last);
  }
}

public static void main(String[] args) {
  ArrayList<Integer> lista1 = new ArrayList<>();
  ArrayList<Integer> lista2 = new ArrayList<>();

  lista1.add(2);
  lista1.add(8);
  lista1.add(12);
  lista1.add(20);
  lista2.add(10);
  lista2.add(11);
  lista2.add(12);
  lista2.add(15);
  lista2.add(30);
  lista2.add(35);

  ArrayList<Integer> listaFinal = new ArrayList<>();

  merge(lista1, lista2, listaFinal)
  quickSort(listaFinal)
}

Python

def merge(listA, listB, list):
  for i in listA:
    list.append(i)
  for i in listB:
    list.append(i)

def quickSort(list):
  size = len(list)
  if size <= 1:
    return list
  else:
    pivot = list[0]

  lower = []
  equal = []
  greater = []
  for i in list:
    if i > pivot:
      greater.append(i)
    elif i == pivot:
      equal.append(i)
    else:
      lower.append(i)

  return quickSort(lower) + equal + quickSort(greater)

lista1 = [2,8,12,20]
lista2 = [10,11,12,15,30,35]

listaFinal = []

merge(lista1, lista2, listaFinal)
quickSort(listaFinal)

Comments

[JulioPino]

Hola mamá, soy el primer comentario :')