Algoritmos de Ordenamiento

Clase 35 de 39 • Curso de Algoritmos con C 2017

Agro Sinergia

student•

Merge Sort es un algoritmo Divide y Conquista . Divide la matriz de entrada en dos mitades, se llama a sí misma para las dos mitades y luego fusiona las dos mitades ordenadas. La función merge () se usa para unir dos mitades. La fusión (arr, l, m, r) es un proceso clave que asume que arr [l…m] y arr [m + 1…r] están ordenados y fusiona las dos sub-matrices ordenadas en una. Vea la siguiente implementación C para más detalles.
Ventajas de la clase de inserción:

Es muy simple.
Es muy eficiente para pequeños conjuntos de datos.
Es estable; es decir, no cambia el orden relativo de los elementos con las mismas claves.
en el lugar; es decir, solo requiere una cantidad constante O (1) de espacio de memoria adicional.

Insertion Sort itera por la lista al consumir un elemento de entrada en cada repetición y hacer crecer una lista de salida ordenada. En una repetición, la ordenación de inserción elimina un elemento de los datos de entrada, encuentra la ubicación a la que pertenece dentro de la lista ordenada y la inserta allí. Se repite hasta que no quedan elementos de entrada.

Bubble Sort Compara cada par de elementos adyacentes desde el comienzo de una matriz y, si están en orden inverso, cámbialos.
Si se ha realizado al menos un intercambio, repita el paso 1.

Quick Sort Hay dos índices i y j y al principio del algoritmo de partición apunta al primer elemento en el conjunto y j apunta al último. Luego, el algoritmo se mueve hacia delante, hasta que se encuentra un elemento con un valor mayor o igual al pivote. El índice j se mueve hacia atrás, hasta que se encuentra un elemento con un valor menor o igual al pivote. Si i ≤ j, entonces se intercambian y yo paso a la siguiente posición ( i + 1 ), j pasos a la anterior (j - 1) . El algoritmo se detiene, cuando soy mayor que j .

Después de la partición, todos los valores anteriores al elemento i-ésimo son menores o iguales que el pivote y todos los valores posteriores al elemento j-ésimo son mayores o iguales al pivote.

Ricardo Celis

teacher•

Muy buen aporte AgroSinergía! no olvides compartirnos tu código =)

Antonio Madrid

student•

Bubble Sort (código de la clase)

#include <stdio.h>

void cambiar_pos(int *n1, int *n2){
	int temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}

void bubbleSort(int vector_entrada[], int n){
	int i, j;
	for(i=0; i < n-1; i++){
		for(j=0; j < n-i-1; j++){
			if(vector_entrada[j] < vector_entrada[j+1])
				cambiar_pos(&vector_entrada[j], &vector_entrada[j+1]);
		}
	}
}

void printArray(int vector_entrada[], int size){
	int i;
	for(i = 0; i < size; i++){
		printf("%d ", vector_entrada[i]);
	}
	printf("\nFin del ordenamiento, saludos. \n");
}

int main(){
	int vector_entrada[] = {98, 87, 75, 12, 1, 5, 2};
	int n = sizeof(vector_entrada)/sizeof(vector_entrada[0]);
	bubbleSort(vector_entrada, n);
	printf("Array ordenado = ");
	printArray(vector_entrada, n);
	printf("\n");
	
	return 0;
}

Pablo Cesar Cardozo Chile

student•

que significa el * en las entradas n1 y n2?

Diego Forero

Team Platzi•

Significa que vas a usar un apuntador.

Cuando se declara una variable en c el lenguaje reserva un espacio en memoria, cuando usas un apuntador estas apuntando a ese espacio en memoria así que si modificas el apuntador también modificas la variable y no una copia, esto permite mejorar el consumo de memoria por ejemplo.

Pablo Cesar Cardozo Chile

student•

Gracias

Tatiana Uintaco

student•

El sizeof en C devuelve el tamaño del array pero en bytes, es decir el tamaño que ocupa en memoria. En este caso cada elemento ocupa 4 bytes por lo que el resultado de sizeof(vector_entrada) = 28, es por esto que se divide entre el tamaño que ocupa un solo elemento del array
sizeof(vector_entrada[0]) = 4. Así finalmente se obtiene la cantidad de elementos en el array (28/4 = 7).

Fue algo que no me quedó muy claro e el vídeo, y lo busque en internet, por si alguien mas tenía la duda.

Mariana Valencia Gallego

student•

Gracias, me suelo frustrar cuando no entiendo este tipo de cosas. Buen aporte!

Luis Manuel Maya Castrejón

student•

Gracias, igual tenía la misma duda.

Danelia Sanchez Sanchez

student•

Esta es mi versión del código, ordenando de menor a mayor:

#include <stdio.h>

#define TAM 10

void Burbuja(int array[])
{
  int i, j, temp;
  for(i = 0; i < TAM - 1; i++)
  {
    for(j = 0; j < TAM - 1; j++)
      if(array[j] > array[j+1])
      {
        temp = array[j];
        array[j] = array[j+1];
        array[j+1] = temp;
      }
  }
}

void EntradaArreglo(int array[])
{
  int i;
  for(i = 0; i < TAM; i++)
  {
    printf("Elemento %d: ", i+1);
    scanf("%d",&array[i]);
  }
}

void ImprimeArreglo(int array[])
{
  int i;
  for (i = 0; i < TAM; i++)
    printf("%d ", array[i]);
  printf("\n");
}

int main()
{
  int arreglo[TAM];
  printf("Introduce los elementos a ordenar: \n");
  EntradaArreglo(arreglo);
  printf("Arreglo Original:\n");
  ImprimeArreglo(arreglo);
  Burbuja(arreglo);
  printf("Arreglo Ordenado:\n");
  ImprimeArreglo(arreglo);
  return 0;
}

Y la ejecución:

Introduce los elementos a ordenar:
Elemento 1: 88
Elemento 2: 25
Elemento 3: 73
Elemento 4: 45
Elemento 5: 12
Elemento 6: 30
Elemento 7: 1
Elemento 8: 126
Elemento 9: 98
Elemento 10: 47
Arreglo Original:
88 25 73 45 12 30 1 126 98 47
Arreglo Ordenado:
1 12 25 30 45 47 73 88 98 126

Ricardo Celis

teacher•

Excelente trabajo Dane!!

Mariana Valencia Gallego

student•

Qué bonita versión

Jecsham Castillo

student•

Vuelvo a compartir un gif que un compañero anteriormente había publicado en clases anteriores:

David Auza

student•

Screenshot del diagrama de flujo del algoritmo:

José Granado

student•

A mi me enseñaron en la universidad que un void es un procedimiento y la diferencia entre una funcion y este, es que la funcion tiene que retornar un tipo de dato y en el procedimiento no es necesario

Exequiel Gómez

student•

En este caso no entendía por qué usaba n = sizeof(arreglo) / sizeof(arreglo[0]);
según lo que leí por ahí, sizeof(x) te da el tamaño que x ocupa en memoria, por lo que en este caso:
sizeof(arreglo)> espacio de memoria que ocupa el arreglo
sizeof(arreglo[0])> espacio que ocupa el elemento cargado en la posición 0 del arreglo
Dividiendo el tamaño total en memoria por el espacio que ocupa cada elemento del array te da la cantidad de elementos que guarda

Yury D. Morales

student•

¡Gracias! Buscaba esta duda y respuesta

Carlos Esteban Freire Yánez

student•

Para hacerlo ascendente basta con cambiar el < dentro del if, por > y listo.

void bubbleSort(int vector_entrada[], int n){
	int i, j;
	for(i=0; i<n-1; i++){
		for(j=0; j<n-i-1; j++){
			if(vector_entrada[j] > vector_entrada[j+1])
				cambiar_pos(&vector_entrada[j], &vector_entrada[j+1]);		
		}
	}
}

Diego Adrián Sánchez Gutiérrez

student•

el verdadero reto de este vídeo es entender la explicación sin que se explicara los arreglos, funciones, paso por valor, por parámetro, que es una referencia y que es un puntero, así como la función ziseof ya que esto no se vio en el curso, pero si nos explicaron dos veces las estructuras selectivas y repetitivas =)

Mariana Valencia Gallego

student•

Para el algoritmo BubbleSort, hice modificaciones para que el usuario pueda ingresar la cantidad de números que quiere que se ordenen, se vayan mostrando uno a uno y al final de la solución:

#include <stdio.h>

 int num;

void cambiar_pos(int *n1, int *n2)
{
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

void bubbleSort(int vector_entrada[], int n)
{
    int i, j;
    for (i=0; i<n-1; i++)
    {
        for (j=0; j<n-i-1; j++)
        {
            if(vector_entrada[j] > vector_entrada[j+1])
            {
                cambiar_pos(&vector_entrada[j], &vector_entrada[j+1]);
            }
        }
    }
}

void printArray(int vector_entrada[], int size)
{
    int i;
    for (i=0; i<size; i++)
    {
        printf("%d ", vector_entrada[i]);
    }
    printf("\nFin del ordenamiento, saludos\n");

}

void introdArray(int array[])
{
  int i = 0;
  int o;
  int cont = 1;
  int arr = 0;
  while (i < num)
  {
      printf("Introduzca un numero\n");
      scanf("%d", &array[arr]);
      printf("%d. %d\n", cont, array[arr]);
      cont++;
      arr++;
      i++;

  }
  printf("Los numeros sin ordenar son:\n");
  for (o = 0; o < arr; o++)
  {
      printf("%d ", array[o]);

  }
  printf("\n");

}

int main()
{

    printf("Introduzca la cantidad de numeros que desea ordenar\n");
    scanf("%d", &num);
    int arrayed[num];
    introdArray(arrayed);
    int n = sizeof(arrayed)/sizeof(arrayed[0]);
    bubbleSort(arrayed, n);
    printf("Arreglo ordenado con BubbleSort: \n");
    printArray(arrayed, n);
    printf("\n");



}

Por mi parte, hice mi propio algoritmo para InsertionSort, donde se ingresan los números o array por código, y se muestra paso a paso de cómo se van ordenando estos números:

#include <stdio.h>

void cambiar_pos(int *n1, int *n2)
{
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

void printArray(int vector_entrada[], int size)
{
    int i;
    for (i=0; i<size; i++)
    {
        printf("%d ", vector_entrada[i]);
    }
    printf("\nFin del ordenamiento, saludos\n");

}

int main()
{
    int pos, i, j;

    int vector_entrada[] = {345, 3, 75, 12, 1, 5, -22, 54, 17, 400, -4564, 34, 94, 45, 4};
    int leng = sizeof(vector_entrada)/sizeof(vector_entrada[0]);

    for(pos=1; pos<=leng-1; pos++)
    {
        for(j=1; j<=pos; j++)
        {
            if (vector_entrada[pos-j+1] < vector_entrada[pos-j])
            {
                cambiar_pos(&vector_entrada[pos-j+1], &vector_entrada[pos-j]);


            }
                printf("El número semi ordenado es:\n");
                printArray(vector_entrada, leng);

        }

    }




}

Jeronimo Torres

student•

No entendi porque entes de cada variable utilizas el ** * **

Carlos David Ramirez Muñoz

student•

Según entendí el * indica que es un puntero

José Ricardo Romo Gutiérrez

student•

Esta seria mi solucion para el algorimo que ordena de menor a mayor, este depende de la cantidad de numeros que ingrese el usuario.

#include <stdio.h>

void cambiarP(int *n1,int *n2)
{
	int temp = *n2;
	*n2=*n1;
	*n1=temp;
}

void bubbleSort(int vector_entrada[],int n)
{
	int i,j;
	for(i=0;i<n-1;i++){
		for (j=0;j<n-i-1;j++){
			if(vector_entrada[j]>vector_entrada[j+1])
			{
				cambiarP(&vector_entrada[j],&vector_entrada[j+1]);
			}
		}
	}	
}

void printArray(int vector_entrada[],int size)
{
	int i;
	for (i=0;i<size;i++){
		printf(" [%d] ",vector_entrada[i]);
	}
	printf("\n\n");	
	printf("\n\n");	
}

int main()
{
	int n;
	
	printf("Bienvenido al ordenador de numeros, ingrese la cantidad de numeros a ordenar:\n");
	scanf("%d",&n);
	printf("Ahora vamos a ingresar todos los numeros:\n");
	
	int arrayB[n];
	
	for(int i=0;i<n;i++){
		printf("-");
		scanf("%d",&arrayB[i]);
	}
	
	printf("\n");
	printf("Felicidades, este es su vector original:\n");
	printArray(arrayB,n);
	printf("Aqui tiene los numeros ordenados de menor a mayor:\n");
	bubbleSort(arrayB,n);
	printArray(arrayB,n);
	
	return 0;	
}

Y esta seria la ejecucion :

Bienvenido al ordenador de numeros, ingrese la cantidad de numeros a ordenar:
8
Ahora vamos a ingresar todos los numeros:
-14
-43
-8
-123
-3
-21
-856
-12

Felicidades, este es su vector original:
 [14]  [43]  [8]  [123]  [3]  [21]  [856]  [12]



Aqui tiene los numeros ordenados de menor a mayor:
 [3]  [8]  [12]  [14]  [21]  [43]  [123]  [856]```

Danelia Sanchez Sanchez

student•

Valores a tener en cuenta al implementar el algoritmo de ordenamiento BubbleSort.

Danelia Sanchez Sanchez

student•

Diagrama de flujo del algoritmo BubbleSort

Alejandro Gallardo

student•

Merge Sort: algoritmo de ordenamiento basado en comparaciones.

Willker Rafaele Romero Ciccone

student•

Código en python:

import random

def bubbleSort(numbers):
    higher = len(numbers)-1
    iterations = 0

    while iterations < higher-1:
        for idx in range(higher):
            if numbers[idx] > numbers[idx+1]:
                temp = numbers[idx+1]
                numbers[idx+1] = numbers[idx]
                numbers[idx] = temp
        iterations = iterations + 1
    return numbers                

if __name__ == '__main__':
    #Crear un array de números aleatorios
    numbers = []
    iterations = random.randint(1,10)

    while iterations > 1:
        aNumber = random.randint(1,100)
        if numbers.count(aNumber) == 0:
            numbers.append(aNumber)
        
        iterations -= 1
    print("The previous array of numbers is ",format(numbers))
    #Llamada de la función de ordenamiento
    result = bubbleSort(numbers)
    print("The sorted array of numbers is ",format(result))

Tatiana Uintaco

student•

#include <stdio.h>

void cambiarPos(int *n1, int *n2)
{
	int temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}

void bubbleSort(int vectorEntrada[], int n)
{
	int i, j;
	
	for(i = 0; i < n-1; i++)
	{
		for(j = 0; j < n-i-1; j++ )
		{
			if(vectorEntrada[j] > vectorEntrada[j+1])
			{
				cambiarPos(&vectorEntrada[j], &vectorEntrada[j+1]);
			}
		}
	}
}

void printArray(int vectorEntrada[], int size)
{
	int i;
	
	for(i = 0; i < size; i++)
	{
		printf("%d ", vectorEntrada[i] );
	} 
	
	printf("fin del ordenameinto \n");
}


int main()
{
	int vectorEntrada[] = {98, 87, 14, 104, 5, 8, 1, 30, 77};
	int n = sizeof(vectorEntrada)/sizeof(vectorEntrada[0]);
	bubbleSort(vectorEntrada, n);
	printf("Arreglo ordenado = \n");
	printArray(vectorEntrada, n);
	printf("\n");

	return 0;
}

Juan José Rivera

student•

Les comparto mi intento de Insertion Sort. No se si es esta la mejor manera, sin embargo, functionó XD.

Espero sus Comentarios.

#include <stdio.h>

int insert (int arr[], int val, int indx);

int main ()
{
    int lista[] = { 2, 4, 1, 5, 3, 8 };
    int sorted = 1;
    int len = sizeof (lista) / sizeof (int);
    
    while(sorted == 1)
    {
        sorted = 0;
        for(int a = 1; a < len; a++)
        {
            int val = lista[a];
            int isGrater = val < lista[a - 1];
            if(isGrater == 1)
            {
                int val = lista[a];
                lista[a] = lista[a - 1];
                lista[a-1] = val;
                sorted = 1;
            }
        }
    }
    //Imprimir lista ordenada en la consola
    for(int e = 0; e < len; e++)
    {
        printf("%d\n", lista[e]);    
    }
}

Ludian Quiñones Solano

student•

el asterisco para que se usa profesor que lo veo antes de n1 y n2?

Diego Forero

Team Platzi•

Es para indicar que es un puntero.

Algoritmos de Ordenamiento

Introducción al Lenguaje C

¿Dónde aprender C?

Introducción al Lenguaje C

Estructura general de un programa en C y un hola mundo

Tipos de errores y datos en C

Variables en C

Operadores y expresiones en C

Ejemplo de operadores en C y reto

Entrada y salida de datos

Estructura secuencial

Estructura secuencial (if y if else)

Estructura selectiva (if, if else, else)

Estructura selectiva (switch)

Estructuras selectivas anidadas

Más Estructuras Selectivas Anidadas

Estructuras Repetitivas: While

Estructuras repetitivas: Do While

Estructuras Repetitivas: For

Platzi Terminal: Llevando a la Práctica lo Aprendido

Crear una tienda de Platzi dentro de la terminal

Crear una tienda de Platzi dentro de la terminal 2

Introducción a Algoritmos

El mundo de los algoritmos

Introducción al Curso de Algoritmos con C

¿Qué es un algoritmo?

Lenguajes de programación

Elementos de un algoritmo

User defined data types: Estructuras de datos y custom data types

Entrada y salida de información

Metodología para la solución de un algoritmo

Resolución del problema

El porqué del análisis de algoritmos

Cómo comparar algoritmos y ritmo de crecimiento

Estructuras de control y estructuras de control secuenciales

Estructuras de control selectivas

Estructuras de control repetitivas

Algoritmos más Utilizados

Sesiones en vivo del Curso de Algoritmos con C

Algoritmos de Ordenamiento

Algoritmo PID

Divide y Vencerás

Algoritmo de Dijkstra: Introducción a los Grafos

Algoritmos de búsqueda