Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Clase 9 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cómo abordar la complejidad espacial y temporal al ordenar listas?

En el mundo de la programación, lidiar con la eficiencia de tiempo y espacio es crucial. Al enfrentarnos a problemas de ordenamiento de listas, es importante elegir un enfoque que optimice ambos factores. En este contexto, exploraremos diferentes estrategias y sus implicaciones de complejidad.

¿Cuáles son las preguntas clave a considerar?

Antes de implementar cualquier solución, surgen algunas preguntas esenciales que debemos considerar:

¿Existen números duplicados en las listas? En la ilustración se demuestra que puede haber duplicados, como el número 2.
¿Qué tipos de números pueden aparecer? Considerando que pueden existir números negativos, enteros, y ceros, es fundamental preparar el algoritmo para manejar estos casos.
¿Cómo optimizar el espacio al ordenar las listas? La pregunta es crucial cuando encontramos ceros al final de una de las listas, lo que sugiere posibles optimizaciones.

¿Cómo optimizar el ordenamiento in-place?

Para ordenar listas de manera in-place y optimizar el uso del espacio, podemos usar un enfoque estratégico con apuntadores. Este método no solo mejora la eficiencia en términos de espacio (O(1)), sino también temporal (O(N+M)).

Pasos para implementar el método in-place:

Inicializar apuntadores:
- Un tercer apuntador al final de la lista prolongada, justo en los ceros, que rastrea las posiciones llenas.
- Dos apuntadores al final de cada lista para comparar elementos y decidir qué número colocar en la posición indicada por el apuntador central.
Proceso de comparación y ubicación:
- Comparar los elementos en las posiciones actuales de ambos apuntadores.
- Colocar el mayor de los dos en la posición designada por el tercer apuntador.
- Mover el apuntador correspondiente al elemento seleccionado para no volver a considerar el mismo número.
- Repetir hasta que todo esté ordenado y el tercer apuntador llegue al inicio de las listas combinadas.
Manejo de longitudes desiguales:
- Si una lista se agota antes que la otra, rellenar las posiciones restantes con los elementos del apuntador no agotado.

Este enfoque garantiza que se aproveche al máximo el espacio disponible en la lista principal, evitando la necesidad de estructuras adicionales y reduciendo la complejidad de tiempo en comparación con métodos como n log n.

¿En qué pensar al implementar el algoritmo?

Eficiencia temporal y espacial: Con el método in-place, se logra un balance perfecto entre las dos complejidades, algo valioso al enfrentar restricciones de recursos.
Punteros bien gestionados: El uso correcto de los punteros es crucial, pues cualquier error podría conducir a resultados incorrectos.
Flexibilidad del algoritmo: Permite adaptarse a diversos escenarios de listas, incluyendo aquellas con números mixtos, negativos, o duplicados.

Al implementar estos principios, no solo se resuelve el problema actual, sino que también se prepara al programador para abordar de manera eficiente problemas de ordenamiento similares en el futuro.

Diego Antonio Gomez Diaz

student•

Como feedback del curso, he notado que algunos de los problemas que hemos visto se pueden encontrar en LeetCode. Sería bueno que agregaran esos enlaces en los recursos para que los estudiantes puedan validar sus soluciones comparándolas con las del problema en LeetCode. De esta manera, todos podemos saber si nuestras soluciones son eficientes.

Ricardo Rito Anguiano

student•

En js

const mergeTwoSortedLists = (nums1, nums2, m, n) => {
    const lastIndex = m + n - 1;
    const n1Copy = [...nums1]
    let n1Pointer = m - 1;
    let n2Pointer = n - 1;
    for (let i = lastIndex; i >= 0; i--) {
        const n1Higher = n1Copy[n1Pointer] ?? Number.MIN_SAFE_INTEGER;
        const n2Higher = nums2[n2Pointer] ?? Number.MIN_SAFE_INTEGER;
        
        if (n1Higher > n2Higher) {
            n1Copy[i] = n1Higher
            n1Pointer--
        } else {
            n1Copy[i] = n2Higher
            n2Pointer--
        }
    }
    return n1Copy;
}

Armando Bueno

student•

Para usar la longitud adecuada solo intercambié los valores en caso necesario, y para poder tener 0s le asigné valor nulo a los indices extra del primer arreglo

Incluyo caso de prueba que considera estos dos casos

def mergeLists(list1, list2, m, n):
    if m > n:
        n,m = m,n
        list1,list2 = list2,list1
    p1 = m-1
    p2 = n-1
    for mp in range(m+n-1, -1, -1):
        if p1 < 0 or list2[p2] > list1[p1] or list1[p1] == None:
            list1[mp] = list2[p2]
            p2 -= 1
        else:
            list1[mp] = list1[p1]
            p1 -= 1
    return list1
    
list2 = [0,2,3,None,None,None,None]
n = 3
list1 = [-4,2,3,9]
m = 4
print(mergeLists(list1, list2,m,n))

Milton Velazquez

student••

def merge_sorted_lists(list1:list, list2:list):
    
    finished = False
    new_list = []
    while not finished:
        if list1[0] <= list2[0]:
            new_list.append(list1.pop(0))
        else:
            new_list.append(list2.pop(0))
        
        if not list1: 
            new_list = new_list + list2
            finished = True
        if not list2: 
            new_list = new_list + list1
            finished = True
    
    return new_list

Angel Agustín Hernandez Soledad

student•

Mi solucion sucia:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(m == 0){
            for(int x = 0; x < nums2.length; x++) {
                nums1[x] = nums2[x];
            }
            return;
        }
        if(n == 0) {
            return;
        }
        
        int p1 = m -1;
        int p2 = n -1;
        int x = nums1.length - 1;
        boolean p1LessZero = false;

        while(p2 > -1) {
            if(p1 < 0) {
                p1LessZero = true;
            }
            int c1 = -1;
            if(!p1LessZero) {
                c1 = nums1[p1];
            } 
            int c2 = nums2[p2];

            if(c1 > c2 && !p1LessZero) {
                nums1[x] = c1;
                p1--;
                x--;
            } else {
                nums1[x] = c2;
                p2--;
                x--;
            }

        }

    }
}
```Mi solucion mas limpia:

```java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;          
        int p2 = n - 1;          
        int p = m + n - 1;       

        while (p2 >= 0) {
            
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
    }
}

Edwin Garcés Saucedo

student•

Yo había hecho esta solución antes de comenzar la clase, pero viendo lo explicado intentaré esa otra implementación:

const joiningLists = (nums1 = [], nums2 = [], m = 1, n = 1) => {
  const filledArray = []
  const fullLength = m + n
  let pointer1 = 0
  let pointer2 = 0
  while (filledArray.length < fullLength) {
    if (nums1[pointer1] < nums2[pointer2] && pointer1 < m) {
      filledArray.push(nums1[pointer1])
      pointer1++
    } else if (nums1[pointer1] > nums2[pointer2] && pointer1 < m) {
      filledArray.push(nums2[pointer2])
      pointer2++
    } else if (pointer1 < m) {
      filledArray.push(nums1[pointer1])
      pointer1++
      filledArray.push(nums2[pointer2])
      pointer2++
    } else {
      filledArray.push(nums2[pointer2])
      pointer2++
    }
  }
  console.log(filledArray)
}

Albert Johanson

student•

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode dummy = new ListNode();
        ListNode current = dummy;

        while(list1 != null && list2 != null){

            int value = 0;
             if(list1.val <= list2.val) {
               value = list1.val;
               list1 = list1.next;
             } else {
               value = list2.val;
               list2 = list2.next;
             }
             
            ListNode tmp = new ListNode(value);
            current.next = tmp;
            current = current.next;
        }


        if(list1 == null) current.next = list2;
        else if(list2 == null) current.next = list1;

        return dummy.next;
    }
}
```/\*\* \* Definition for singly-linked list. \* public class ListNode { \*     public int val; \*     public ListNode next; \*     public ListNode(int val=0, ListNode next=null) { \*         this.val = val; \*         this.next = next; \*     } \* } \*/public class Solution {    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {        if(list1 == null) return list2;        if(list2 == null) return list1;
&#x20;       ListNode dummy = new ListNode();        ListNode current = dummy;
&#x20;       while(list1 != null && list2 != null){
&#x20;           int value = 0;             if(list1.val <= list2.val) {               value = list1.val;               list1 = list1.next;             } else {               value = list2.val;               list2 = list2.next;             }                         ListNode tmp = new ListNode(value);            current.next = tmp;            current = current.next;        }

&#x20;       if(list1 == null) current.next = list2;        else if(list2 == null) current.next = list1;
&#x20;       return dummy.next;    }}

Miguel Angel Reyes Moreno

student•

Yo pensé en esta lógica: 1- eliminar los 0 del primer array 2- mezclar ambos arrays 3- ordenar de menor a mayor sus números

const mergeTwoSortedLists = (nums1: number[], nums2: number[]): number[] => { nums1 = nums1.filter(n => n !== 0) return (nums1.concat(nums2)).sort((nums1, nums2) => nums1 - nums2)}

Marcos Mesias

student•

Pude resolver el problema con las indicaciones que nos dio la profesora, lo que le entendí, lo hice sin usar una función de ordenamiento ni usar una nueva lista. Hice otro codigo mas facil resolviendo el problema y lo publique en la clase anterior, pero ese codigo ocupaba mucha memoria, con mi nuevo codigo reduje significativamente el uso de memoria, una cuarta parte, pero el tiempo de ejecución parece ser la similar. Igual hubo una mejora.

Marcos Mesias

student•

Pude resolver el problema con las indicaciones que nos dio la profesora, lo que le entendí, lo hice si usar una función de ordenamiento ni usar una nueva lista. Hice otro codigo mas facil resolviendo el problema y lo publique en la clase anterior, pero ese codigo ocupaba mucha memoria, con mi nuevo codigo reduje significativamente el uso de memoria, una cuarta parte, pero el tiempo de ejecución parece ser la misma. Igual hubo una mejora.

Arley Santiago

student•

def sort_sort_two_lists(A: list, B: list) -> list:
    lengthA = len(A)
    lengthB = len(B)
    X = [0 for _ in range(lengthA + lengthB)]

    if lengthA == 0 or lengthB == 0:
        return A + B
    i = 0
    j = 0
    k = 0
    while i < lengthA and j < lengthB:
        if A[i] < B[j]:
            X[k] = A[i]
            i += 1
        else:
            X[k] = B[j]
            j += 1
        k += 1

    while i < lengthA:
        X[k] = A[i]
        i += 1
        k += 1

    while j < lengthB:
        X[k] = B[j]
        j += 1
        k += 1

    return X
```This a simmilar solution that merge sort.

Arley Santiago

student•

This one is my solution i used a simmilar strategy than merge_sort. def sort_sort_two_lists(A: list, B: list) -> list: lengthA = len(A) lengthB = len(B) X = [0 for _ in range(lengthA + lengthB)]

if lengthA == 0 or lengthB == 0: return A + B i = 0 j = 0 k = 0 while i < lengthA and j < lengthB: if A[i] < B[j]: X[k] = A[i] i += 1 else: X[k] = B[j] j += 1 k += 1 while i < lengthA: X[k] = A[i] i += 1 k += 1 while j < lengthB: X[k] = B[j] j += 1 k += 1 return X```js def sort_sort_two_lists(A: list, B: list) -> list: lengthA = len(A) lengthB = len(B) X = [0 for _ in range(lengthA + lengthB)]

if lengthA == 0 or lengthB == 0:
    return A + B
i = 0
j = 0
k = 0
while i < lengthA and j < lengthB:
    if A[i] < B[j]:
        X[k] = A[i]
        i += 1
    else:
        X[k] = B[j]
        j += 1
    k += 1

while i < lengthA:
    X[k] = A[i]
    i += 1
    k += 1

while j < lengthB:
    X[k] = B[j]
    j += 1
    k += 1

return X

Maryam del Mar Correa

student•

Mi solución en Python. Es más general y es indiferente a los tamaños de ambas listas. Quise hacerla lo más sencilla posible, sin hacer desplazamientos o asignaciones con slicing. Creo que resulta en complejidad O(n log(n)).

def ordenamiento_de_listas(nums1, nums2):
    
    m = len(nums1)
    n = len(nums2)
    
    for i in range(n):
        nums1.append(0)
        
    idx2 = m # Apuntador hacia las ubicaciones a llenar
    idx1 = 0 # Apuntador a la posición donde hay que cambiar el número
    # El desplazamiento de los números ocurre entre idx1 e idx2
    
    
    for j in range(n):
        num = nums2[j]
        
        # Hallar idx1
        for i in range(idx2):
            a = nums1[i]
            b = nums1[i+1]
            
            if num<=a and num<b:  # n<=a<b
                idx1 = i
                break
            elif num>a and num<=b:  # a<n<=b
                idx1 = i+1
                break
            else:  # a<b<n
                pass

        # Desplazamientos y asignación de valor a posición  
        if num<=b:
            idx2 += 1
            
            if idx2 < n+m:
                i = 0
                while i<(idx2-idx1):
                    nums1[idx2-i] = nums1[idx2-1-i]
                    i += 1
            else:
                i = 0
                while i<(idx2-idx1):
                    nums1[idx2-1-i] = nums1[idx2-2-i]
                    i += 1
                    
            nums1[idx1] = num
            idx1 += 1
            
        else:
            nums1[idx2] = num
            idx2 += 1
            idx1 += 1
  
    print(nums1)
    print('\n')

Frandel Corporan Rodríguez

student•


function mergeList(nums1,nums2){    *let* n = nums2.length, m;      nums2.forEach(element => {        nums1.push(0);    });    m = nums1.length-n;
    for(*let* i = 0; i\<nums1.length-1; i++) {
        if(nums1\[i] === 0){            nums1.splice(i,n,...nums2);        }    }    *return* nums1.sort();}
console.log(mergeList(\[1,2,2,4],\[2,5,6,7,3]))

Frandel Corporan Rodríguez

student•

Xavier Flores

student•

hpta que solución mas linda la de la profe jjj, yo hice la mía pero no estan eficiente porque recorre los arreglos muchas veces.

const nums1 = [1, 2, 3, 0, 0, 0, 0];
const m = 3;
const nums2 = [-4, 2, 3, 9];
const n = 4;

const min_value = (nums1, nums2) => {
  if (nums1[0] < nums2[0]) {
    return nums1[0];
  } else {
    return nums2[0];
  }
};

const max_value = (nums1, nums2) => {
  max_leng_value1 = nums1.length - nums2.length - 1;
  max_leng_value2 = nums2.length - 1;

  if (nums1[max_leng_value1] > nums2[max_leng_value2]) {
    return nums1[max_leng_value1];
  } else {
    return nums2[max_leng_value2];
  }
};

function addMerge(array, value, merge) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value && value != 0) {
      merge.push(value);
    }
  }
  return merge;
}

function mergeTwoSorted(nums1, nums2) {
  const min = min_value(nums1, nums2);
  const max = max_value(nums1, nums2);

  let array_merged = [];

  for (let value = min; value <= max; value++) {
    addMerge(nums1, value, array_merged);
    addMerge(nums2, value, array_merged);
  }
  return array_merged;
}

console.log(mergeTwoSorted(nums1, nums2));

Yojan Antonio Pardo Zabala

student•

esta fue mi solución en java, olvidé lo de los numeros m y n xd pero tambien funciona

public class MergeTwoSortedLists {
    public static void main(String[] args) {
        int[] list1 = {1,2,3,4,7,9};
        int[] list2 = {2,5,6,8,10,11,12};
        int[] mergedList = mergeTwoSortedLists(list1, list2);
        for (int j : mergedList) {
            System.out.println(j);
        }
    }

    private static int[] mergeTwoSortedLists(int[] list1, int[] list2) {
        int[] mergedList = new int[list1.length + list2.length];
        int index1 = 0;
        int index2 = 0;
        for(int i = 0; i < mergedList.length; i++) {
            int insertValue;
            if(index1 == list1.length) {
                insertValue = list2[index2];
                index2++;
                mergedList[i] = insertValue;
                continue;
            }
            if(index2 == list2.length) {
                insertValue = list1[index1];
                index1++;
                mergedList[i] = insertValue;
                continue;
            }
            if(list1[index1] <= list2[index2]){
                insertValue = list1[index1];
                index1++;
            } else {
                insertValue = list2[index2];
                index2++;
            }
            mergedList[i] = insertValue;
        }
        return mergedList;
    }
}

franklin yancoba

student•

comparto mi solucion en c#

public List<int> MergeTwoList(List<int> list1, List<int> list2, int m, int n)
        {
            List<int> result = new List<int>();
            int pointerList2 = 0;
            int pinterList1 = 0;
            for (int i = 0; i < m; i++)
            {
                if (isNullSearchIndexInList(list2, pointerList2))
                {
                    result.Add(list1[pinterList1]);
                    pinterList1++;
                }
                else if (isNullSearchIndexInList(list1, pinterList1))
                {
                    result.Add(list2[pointerList2]);
                    pointerList2++;
                }
                else {
                    if (list1[pinterList1] <= list2[pointerList2])
                    {
                        result.Add(list1[pinterList1]);
                        pinterList1++;
                    }
                    else
                    {
                        result.Add(list2[pointerList2]);
                        pointerList2++;
                    }
                }

            }
            return result;
        }
        public bool isNullSearchIndexInList(List<int> List, int indexSearch) {
            if (List.Count>=indexSearch) {
                return true;
            }
            return false;
        }
```public List\<int> MergeTwoList(List\<int> list1, List\<int> list2, int m, int n)

&#x20;       {

&#x20;           List\<int> result = new List\<int>();

&#x20;           int pointerList2 = 0;

&#x20;           int pinterList1 = 0;

&#x20;           for (int i = 0; i < m; i++)

&#x20;           {

&#x20;               if (isNullSearchIndexInList(list2, pointerList2))

&#x20;               {

&#x20;                   result.Add(list1\[pinterList1]);

&#x20;                   pinterList1++;

&#x20;               }

&#x20;               else if (isNullSearchIndexInList(list1, pinterList1))

&#x20;               {

&#x20;                   result.Add(list2\[pointerList2]);

&#x20;                   pointerList2++;

&#x20;               }

&#x20;               else {

&#x20;                   if (list1\[pinterList1] <= list2\[pointerList2])

&#x20;                   {

&#x20;                       result.Add(list1\[pinterList1]);

&#x20;                       pinterList1++;

&#x20;                   }

&#x20;                   else

&#x20;                   {

&#x20;                       result.Add(list2\[pointerList2]);

&#x20;                       pointerList2++;

&#x20;                   }

&#x20;               }



&#x20;           }

&#x20;           return result;

&#x20;       }

&#x20;       public bool isNullSearchIndexInList(List\<int> List, int indexSearch) {

&#x20;           if (List.Count>=indexSearch) {

&#x20;               return true;

&#x20;           }

&#x20;           return false;

&#x20;       }

Victor Hugo Vázquez Gómez

student•

Yo llegue a este O(n+m) tambien pero si utilice un array aux:

export const mergedTwoSortedLists = (nums1: number[], nums2: number[], m: number, n: number): number[] | false => {
  const joinArray: number[] = [];
  let i = 0; // index for nums1
  let j = 0; // index for nums2

  // Validations
  if (nums1.length !== (m + n)) return false;
  if (nums2.length !== n) return false;
  if (nums1.slice(n).every(num => num === 0) === false) return false;

  while (true) {
    // This means we don't have more numbers to check, so push all
    // the rest of numbers of nums2 to joinArray.
    if (nums1[i] === 0) {
      joinArray.push(...nums2.slice(j));
      break;
    }

    // nums1[i] is less than nums2 of current index,
    // push nums1[i] to join array.
    if (nums1[i] > nums2[j] === false) {
      joinArray.push(nums1[i]);
      i = i + 1;
    } else { // nums2 of current index is less than 
      joinArray.push(nums2[j]);
      j = j + 1;
    }
  }

  return joinArray;
};

Nabil Aparicio

student•

yo utilice una variable vacia para crear un nuevo array filtrando el orden y los elementos a ser pusheados no se si eso se permitia

function mergeTwoSortedList (list_1, size_1, list_2, size_2){

const longestList = Math.max(list_1.length, list_2.length)

let newSortedList = []

for(let i = 0; i <= longestList - 1; i++){

if(list_1[i] !== 0 && list_2[i] !== 0){

if(list_1[i] > list_2[i]){

newSortedList.push( list_2[i], list_1[i])

}else{

newSortedList.push( list_1[i], list_2[i])

}

return newSortedList

}