4

#PlatziCodingChallenge Dia #26 y #27. Ordenando ando #2 y #3

#26. Ordenando ando #2
Ordena tu set de nombres con cualquier algoritmo de ordenamiento que quieras, asegúrate de imprimir cuánto tiempo se demoró tu equipo en ordenar.

#27. Ordenando ando #3
Prueba otro algoritmo de ordenamiento con el mismo data set y compara el tiempo, comparte en el foro cuál fue tu algoritmo con mejor rendimiento y por qué

Escribe tu comentario
+ 2
Ordenar por:
2
19943Puntos

Retos 26 y 27 en JavaScript:

//Ordenando Ando 3 con JavaScript//Algoritmo #1: método burbujafunctionBubbleSort(list) {
    for (let i = 0; i < list.length - 1; i++) {
        for (let j = 0; j < list.length; j++) {
            if (list[j] > list[j + 1]) {
                aux = list[j]
                list[j] = list[j + 1]
                list[j + 1] = aux
            }
            
        }
    }
    returnlist
}

//Algoritmo #2: ordenamiento por inserciónfunctionInsertionSort(list) {
    for (let i = 0; i < list.length; i++) {
        let pos = i
        let aux = list[i]
        while (pos > 0 && list[pos - 1] > aux) {
            list[pos] = list[pos - 1]
            pos--
        }
        list[pos] = aux
    }
    returnlist
}

//Leyendo archivoconst RUTA_CSV = 'PlatziCodingChallenge_Dia27/OrdenandoAndo3.csv'
fetch(RUTA_CSV)
    .then(res => res.text())
    .then(data => {
        let listaNombres = data.split('\n')
        //Ordenando los nombres//Método burbujaconsole.time('Método burbuja')
        let listaOrdenada1 = BubbleSort(listaNombres)
        console.timeEnd('Método burbuja') //Método burbuja: 16-20msconsole.log(listaOrdenada1)
        //Ordenamiento por inserciónconsole.time('Ordenamiento por inserción')
        let listaOrdenada2 = InsertionSort(listaNombres)
        console.timeEnd('Ordenamiento por inserción') //Ordenamiento por inserción: 5-8msconsole.log(listaOrdenada2)

    })
    .catch(error => {
        console.log(error)
    })
1
25067Puntos
7 meses

Buenas compañero, utilizando tu código para leer el csv me sale el siguiente error, ¿a ti no te ha aparecido? ¿cómo lo has solucionado?
orderNames.js:34 Fetch API cannot load… URL scheme must be “http” or “https” for CORS request.

1
7689Puntos

El reto 27 también lo hice con NodeJs, usando fs y csv-parse, pero en este caso en vez de usar el método default para ordenar arrays sort(), use un algoritmo burbuja (https://www.etnassoft.com/2017/03/24/algoritmos-de-ordenacion-en-javascript-revision-es6/)

const fs = require('fs') // filesystemconst csv = require('csv-parse')// Encargado de parsearlet array = []

const parseador = csv({
    delimiter: ',',// Delimitador, por defecto es la coma ,cast: true, // Intentar convertir las cadenas a tipos nativoscomment: '#'// El carácter con el que comienzan las líneas de los comentarios, en caso de existir
})

parseador.on('readable', function () {
    let fila
    while (fila = parseador.read()) {
        array.push(fila)
    }
})

parseador.on('error', function (err) {
    console.error("Error al leer CSV:", err.message)
})

console.time('tiempo')
fs.createReadStream("../25.OrdenandoAndo.csv") // Abrir archivo
    .pipe(parseador) // Pasarlo al parseador a través de una tubería
    .on("end", function () {// Y al finalizar, terminar lo necesario
        array = array.flat(1)
        array.shift()
        const bubbleSort = arr => {
          const l = arr.length;
          for (let i = 0; i < l; i++ ) {
            for (let j = 0; j < l - 1 - i; j++ ) {
              if ( arr[ j ] > arr[ j + 1 ] ) {
                [ arr[ j ], arr[ j + 1 ] ] = [ arr[ j + 1 ], arr[ j ] ];
              }
            }
          }
          return arr;
        };
        const result = bubbleSort(array)
        console.log(result)
        console.timeEnd('tiempo')
        parseador.end()
    })
1
7689Puntos
7 meses

En este caso, el tiempo podía variar entre 30ms, hasta 80ms que me apareció una vez, que es casi el doble que el método sort(). En esta foto se ve un proceso que duro hasta 68ms

Esto nos demuestra que el método sort tiene un mejor rendimiento que un algoritmo de ordenación básico como el algoritmo burbuja, ¿Por qué? La verdad no lo tengo muy claro, pero de lo que leí aquí (https://stackoverflow.com/questions/234683/javascript-array-sort-implementation) al parecer, el método sort() utiliza diferentes tipos de algoritmos, que en el caso de los no-numéricos, se les hace stringify (En nuestro caso ya estarían en string) y luego se les hace un mergeSort, algoritmo más avanzado que trata de : “El algoritmo de ordenamiento por mezcla trabaja también mediante el concepto de sub listas. De este modo, el conjunto inicial se divide en dos sub conjuntos de aproximadamente igual tamaño para proceder a su ordenamiento de forma independiente. Finalmente, se mezclan ambos conjuntos para obtener el ordenamiento final.”, entonces, podemos sacar la conclusión que realiza un sorteo más rápido al no tener que ir indice por indice como el algoritmo de la burbuja.

Si es que estoy equivocado en algo, me gustaría que alguien me lo comentara c:

1

En Python:

27 Insertion Sort:

""" Programa para ordenar un set de nombres mediante el ordenamiento de inserción e imprimir el tiempo utilizado en ello.
Program to sort a set of names using insertion sort and print the time used in it. """import csv
import time

defread_csv():with open('Names.csv', 'r') as file:
        names_list = []
        reader = csv.reader(file)
        for row in reader:
            names_list.append(row[0])
        return names_list

definsertion_sort(name_list):
    start = time.perf_counter()
    for index in range(1, len(name_list)):
        actual_value = name_list[index]
        position = index
        
        while (position > 0) and (name_list[position-1] > actual_value):
            name_list[position] = name_list[position-1]
            position = position - 1
        
        name_list[position] = actual_value
    
    stop = time.perf_counter()
    total_time = (stop - start)*1000
    print(name_list)
    print('Insertion Sort takes {} ms to order your list.' .format(total_time))

if __name__ == "__main__":
    name_list = read_csv()
    insertion_sort(name_list)
Captura3.JPG
1
7689Puntos

El reto 26 lo hice con NodeJs, usando el módulo de fs para poder crear un ReadStream, y también un módulo externo que me permite manejar los archivos csv llamado csv-parse. El código te lee el archivo, lo parsea, una vez parseado, hago un flat(1), para eliminar un nivel en el array, y luego se hace shift() para eliminar ‘Nombres’, de ahí ya solo se sortea y se imprime en consola el array con los nombres ordenados A - Z. Les dejo un link de donde saque el código del uso de csv-parse: https://parzibyte.me/blog/2018/12/26/parsear-csv-node-js-csv-parse/

const fs = require('fs') // filesystemconst csv = require('csv-parse')// Encargado de parsearlet array = []

const parseador = csv({
    delimiter: ',',// Delimitador, por defecto es la coma ,cast: true, // Intentar convertir las cadenas a tipos nativoscomment: '#'// El carácter con el que comienzan las líneas de los comentarios, en caso de existir
})

parseador.on('readable', function () {
    let fila
    while (fila = parseador.read()) {
        array.push(fila)
    }
})

parseador.on('error', function (err) {
    console.error("Error al leer CSV:", err.message)
})

console.time('tiempo')
fs.createReadStream("../25.OrdenandoAndo.csv") // Abrir archivo
    .pipe(parseador) // Pasarlo al parseador a través de una tubería
    .on("end", function () {// Y al finalizar, terminar lo necesario
        array = array.flat(1)
        array.shift()
        const arrayOrdenado = array.sort()
        console.log(arrayOrdenado)
        console.timeEnd('tiempo')
        parseador.end()
    })
1
7689Puntos
7 meses

El tiempo que demora son desde 23ms hasta a veces 37ms, en esta foto tomó 28.18ms:

1
8501Puntos

#PlatziCodingChallenge Días 26 y 27 - Solución al reto con JavaScript y la librería nativa de nodejs “fs” para leer el archivo .csv con el set de 300 nombres.

Los algoritmos utilizados para el ordenamiento fueron
BubbleSort: Ordena un arreglo intercambiando repetidamente los elementos adyacentes si están en orden incorrecto.

QuickSort: Basado en la técnica “Divide y venceras”, esto significa que toma el arreglo y empieza a dividirlos en secciones más pequeñas, para así poder empezar a ordenar esos arreglos.

Código
Day 26 27 - Sort.png

Implementación
Day 26 27 - Sort_Implementacion.png

Resultado
Day 26 27 - Sort_Resultado.png

1
  1. Bubble Sort
""" Programa para ordenar un set de nombres mediante el ordenamiento de la burbuja e imprimir el tiempo utilizado en ello.
Program to sort a set of names using bubble sort and print the time used in it. """import csv
import time

defread_csv():with open('Names.csv', 'r') as file:
        names_list = []
        reader = csv.reader(file)
        for row in reader:
            names_list.append(row[0])
        return names_list

defbubble_sort(name_list):
    start = time.perf_counter()
    for num in range(len(name_list)-1,0,-1):
        for i in range(num):
            if name_list[i]>name_list[i+1]:
                name_list[i], name_list[i+1] = name_list[i+1], name_list[i]
    stop = time.perf_counter()
    total_time = (stop - start)*1000
    print(name_list)
    print('Bubble Sort takes {} ms to order your list.' .format(total_time))

if __name__ == "__main__":
    name_list = read_csv()
    bubble_sort(name_list)
Captura2.JPG
1
6327Puntos

Retos 27 y 28 en Java ☕️ ☕️ 😃

public class OrdenandoAndo {
    public static void main(String[] args) {
        File archivo;
        FileReader fr = null;
        BufferedReader br;
        ArrayList<String> arrayNombres = new ArrayList<>();

        try {
            // Apertura del fichero y creacion de BufferedReader para poder// hacer una lectura comoda (disponer del metodo readLine()).//archivo = new File ("C:\\archivo.txt");
            archivo = new File("/home/pepivsky/Documentos/300NombresGenerados.csv");
            fr = new FileReader(archivo);
            br = new BufferedReader(fr);// Lectura del fichero
            String linea;while ((linea = br.readLine()) != null) {
                arrayNombres.add(linea); //Agregando los nombres al arrayList
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {

            System.out.println("Array Orginal: ");System.out.println(arrayNombres);System.out.println();//#1 Usando Collections.sortSystem.out.println("Usando Collections.sort");
            long startTime = System.nanoTime();
            Collections.sort(arrayNombres);
            long endTime = System.nanoTime() - startTime;System.out.println(arrayNombres.toString());System.out.println("Tarda: " + endTime + " nanosegundos");//Algoritmo #2 Usando el método burbuja:
            String[] arrayn = new String[arrayNombres.size()];
            arrayn = arrayNombres.toArray(arrayn);

            String aux;
            long startTime2 = System.nanoTime(); //Inicio del tiempofor (int i = 1; i <= arrayn.length; i++) {for (int j = 0; j < arrayn.length - i; j++) {if (arrayn[j].compareTo(arrayn[j + 1]) > 0) { //Si el elemento actual es mayor que el siguiente
                        aux = arrayn[j];
                        arrayn[j] = arrayn[j + 1];
                        arrayn[j + 1] = aux;
                    }
                }
            }
            long endTime2 = System.nanoTime() - startTime2; //fin del tiempoSystem.out.println();System.out.println("Ordenamiento burbuja");System.out.println(Arrays.toString(arrayn));System.out.println("Tarda: " + endTime2 + " nanosegundos");//Algoritmo #3 Usando el método de inserción directa
            String[] arrayI = new String[arrayNombres.size()];
            arrayI = arrayNombres.toArray(arrayI);int posicion;
            String elemento;

            long startTime3 = System.nanoTime();for (int i = 0; i < arrayI.length; i++) {
                posicion = i;
                elemento = arrayI[i];while ((posicion > 0) && (arrayI[posicion-1].compareTo(elemento) > 0)) {
                    arrayI[posicion] = arrayI[posicion-1];
                    posicion--;
                }
                arrayI[posicion] = elemento;
            }
            long endTime3 = System.nanoTime() - startTime3;System.out.println();System.out.println("Ordenamiento por inserción");System.out.println(Arrays.toString(arrayI));System.out.println("Tarda: " + endTime3 + " nanosegundos");


            try {
                if (null != fr) {
                    fr.close();
                }
            } catch (Exception e2) {
                e2.printStackTrace();
            }
        }
    }
}

**Resultado del programa: **

Los algoritmos usados para el ordenamiento fueron Colletions.sort(el que provee Java), Burbuja y ordenamiento por inserción
El más rápido fue el ordenamiento por inserción

1
26494Puntos

Ambos retos en un solo script. 🐍

import time
import csv

defread_csv():with open('datos.csv', mode='r') as csv_file:
        csv_reader = csv.reader(csv_file, delimiter = ',')  

        return list(csv_reader)


defordenamiento_burbuja(lista):
    n = len(lista)

    for i in range(n):
        for j in range(0, n - i - 1):

            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

    return lista
    

defordenamiento_insercion(lista):for indice in range(1, len(lista)):
        valor_actual = lista[indice]
        posicion_actual = indice

        while posicion_actual > 0and lista[posicion_actual - 1] > valor_actual:
            lista[posicion_actual] = lista[posicion_actual - 1]
            posicion_actual -= 1

        lista[posicion_actual] = valor_actual

    return lista


defrun():#Ordenamiento de burbuja
    comienzo = time.time()

    nombres = read_csv()
    print(f'Nombres: {nombres}')
    nombres_ordenados = ordenamiento_burbuja(nombres)
    print(f'\n\nNombres ordenados: {nombres_ordenados}')

    final = time.time()

    tiempo = final - comienzo
    print(f'\nDuración ordenamiento de burbuja: {tiempo} segundos')


    #Ordenamiento por inserción

    comienzo = time.time()

    nombres = read_csv()
    print(f'Nombres: {nombres}')
    nombres_ordenados = ordenamiento_insercion(nombres)
    print(f'\n\nNombres ordenados: {nombres_ordenados}')

    final = time.time()

    tiempo = final - comienzo
    print(f'\nDuración ordenamiento por inserción: {tiempo} segundos')

if __name__ == "__main__":
    run()
1
13595Puntos

Restos 26 y 27 en JS:

//Funcion que sera llamada por el boton submitfunctionorderNames(){
  if (document.getElementById("input-file").files.length === 0) {
    alert("There was no file selected");
    return;
  }

  //Se obtiene el archivo CVSlet file = document.getElementById("input-file").files[0];
  let fileReader = new FileReader();

  //Metodo asincrono que se llamara al leer el archivo
  fileReader.onload = (event) => {
    let textFile = event.target.result;
    let names = [...textFile.split("\n")];

    //Se ejecuta el quicksort
    console.time("InsertionSort")
    const sort2 = insertionSort(names);
    console.timeEnd("InsertionSort");
   
    console.time("QuickSort")
    quickSort(names, 0, names.length -1);
    console.timeEnd("QuickSort");

    console.log(sort2);
    console.log(names);
  };

  fileReader.readAsText(file);
}

functionquickSort(array, left, right){
    if(left < right){
        index = quickSortPartition(array, left, right);       
        quickSort(array, left, index-1);
        quickSort(array, index + 1, right);
    }
}

functionquickSortPartition(array, left, right){
    let pivot = array[right];
    let i = left;

    for (let j = left; j < array.length; j++) {
        if (array[j] < pivot) {
            swap(array, i, j);
            i++;
        }        
    }
    swap(array, i, right);

    return i;
}

functionswap(array, numA, numB){
    let aux = array[numA];
    array[numA] = array[numB];
    array[numB] = aux;
 }
 
 functioninsertionSort(unsortedArray){
   letarray = [...unsortedArray];
   for (let i = 0; i < array.length; i++) {
     let j = i;
     while (j > 0 && array[j-1] > array[j]) {
       swap(array, j, j-1);
       j--;
     }     
   }
   returnarray;
 }
1

En Python

import csv
import time

with open('nombres.csv', newline='') as File:
    nombre_lista=[]
    reader = csv.reader(File)
    for row in reader:
        nombre_lista.append(row[0])
        nombre_lista.append(row[1])
        nombre_lista.append(row[2])
    print(nombre_lista)
miLista = nombre_lista
#Por bublesort
print('La lista ordenada es: \n')
start = time.perf_counter()
for x in range(len(nombre_lista)-1,0,-1):
    for i in range(x):
        if nombre_lista[i]>nombre_lista[i+1]:
            nombre_lista[i], nombre_lista[i+1] = nombre_lista[i+1], nombre_lista[i]
stop = time.perf_counter()
total_time = (stop - start)*1000
print(nombre_lista)
print('Por bublesort se tartda {}.' .format(total_time))
#Por Quicksort
start = time.perf_counter()
defsort(lista):
    izquierda = []
    centro = []
    derecha = []
    if len(lista) > 1:
        pivote = lista[0]
        for i in lista:
            if i < pivote:
                izquierda.append(i)
            elif i == pivote:
                centro.append(i)
            elif i > pivote:
                derecha.append(i)
        #print(izquierda+["-"]+centro+["-"]+derecha)return sort(izquierda)+centro+sort(derecha)
    else:
      return lista
print(miLista)
print(sort(miLista))
stop = time.perf_counter()
total_time = (stop - start)*1000
print('Por Quicksort se tartda {}.' .format(total_time))

El metodo mas rapido es quicksort(7 ms) compara do a bublesort(33ms)

1
8870Puntos

en c#
para este reto primero tuve que ver el curso básico de algoritmos, es increíble que algo tan importante jamás me lo hayan dado en la universidad.
utilicé bubble sort e insertion sort, claramente insertion sort lo hizo en menos tiempo, el porque de esto lo explican muy bien en el curso que acabo de mencionar.

using System;
using System.IO;
using System.Collections;
using System.Diagnostics;

namespace Reto_26_27_28_Ordenando_ando
{
    class Program
    {
        static void Main(string[] args)
        {

            ArrayList nombres = new ArrayList();
            StreamReader leerArchivo = new StreamReader("nombres.csv");while (!leerArchivo.EndOfStream)
            {
                string nombre = leerArchivo.ReadLine();
                nombres.Add(nombre);
            }
            leerArchivo.Close();
            string linea = "";foreach (var i in nombres)
            {
                linea += i + ", ";
            }
            Console.WriteLine("Arreglo original: ");
            Console.WriteLine(linea);
            Console.WriteLine("\n\n\n\n");
            bubbleSort(nombres);
            Console.WriteLine("\n\n\n\n");
            InsertionSort(nombres);

        }

        public static void bubbleSort(ArrayList nombres)
        {
            Boolean cambio = false;
            Stopwatch tiempo = new Stopwatch();
            tiempo.Start();do
            {
                cambio = false;for (int i = 0; i < (nombres.Count-1); i++)
                {
                    string auxiliar1 = nombres[i].ToString();
                    string auxiliar2 = nombres[i + 1].ToString();if (auxiliar1.CompareTo(auxiliar2) == 1)
                    {
                        nombres[i] = auxiliar2;
                        nombres[i + 1] = auxiliar1;
                        cambio = true;
                    }
                }
            } while (cambio);
            tiempo.Stop();
            string linea = "";foreach (var i in nombres)
            {
                linea += i + ", ";
            }
            Console.WriteLine("Arreglo ordenado alfabeticamente con Bubble Sort: ");
            Console.WriteLine(linea);
            Console.WriteLine("tiempo transcurrido: "+tiempo.Elapsed.TotalMilliseconds+" ms");
            Console.WriteLine("\n\n\n\n");


        }

        public static void InsertionSort(ArrayList nombres)
        {
            Stopwatch tiempo = new Stopwatch();
            tiempo.Start();for (int i = 1; i < nombres.Count; i++)
            {
                string valorActual = nombres[i].ToString();int j = i - 1;while (j >= 0 && (nombres[j].ToString().CompareTo(valorActual) ==1))
                {
                    nombres[j + 1] = nombres[j];
                    j--;
                }
                nombres[j + 1] = valorActual;
            }
            tiempo.Stop();
            string linea = "";foreach (var i in nombres)
            {
                linea += i + ", ";
            }
            Console.WriteLine("Arreglo ordenado alfabeticamente con Insertion Sort: ");
            Console.WriteLine(linea);
            Console.WriteLine("tiempo transcurrido: " + tiempo.Elapsed.TotalMilliseconds + " ms");
            Console.WriteLine("\n\n\n\n");
        }
    }
}
0
12398Puntos

La 26 en Python

import csv
archivo_nombres = open('nombres.csv', 'r')

header = archivo_nombres.readline()

reader = csv.reader(archivo_nombres)
reader = sorted(reader)


for linea inreader:
  print(linea[0])

0
17607Puntos

Para este reto use los algoritmos de ordenamiento por burbuja y por mezcla:
Por burbuja (bubbleSort): Es un algoritmo muy fácil de implementar pero muy ineficiente por su lentitud, ya que realiza muchas iteraciones para ordenar, para este ejemplo 0.26 segundos más, este valor en si no dice mucho pero si comparamos el porcentaje que fue de 750% mas tiempo que el otro algoritmo nos damos cuenta de lo ineficiente que es este algoritmo, y se hace aun mas ineficiente cuando son transacciones mas largas, sin embargo este algoritmo es el mas usado por su fácil implementación. solo requirió 9 líneas de código. (Debo reconocer que es el que mas he usado) 😃.

Por mezcla (mergeSort): Es un algoritmo algo complejo de implementar desde mi punto de vista, pero sin duda es muy eficiente, su idea principal es disminuir la cantidad de iteraciones, ya que se basa en dividir el array en diferentes sub listas para luego ir ordenando y mezclando al mismo tiempo. Obtuvo un gran rendimiento. Divide y venceras! 😃

Les comparto mi implementación hecha con javascript:

Reto 25-26-27: Ordenando ando
Repositorio del reto: PlatziCodingChallengeRepo
GitHub pages: PlatziCodingChallengePages
reto24.png