Cursos Empresas Blog Live Conf Eventos Precios

0:0012:29

Recursos

Resumen

Para esta clase prepararemos las funciones que nos sirvan para hacer nuestro ordenamiento de burbuja diseñando también la función que cambie la posición de un elemento en el array.

Implementación de Bubble Sort en C paso a paso

Curso Práctico de Estructuras de Datos y Algoritmos

Clase 22 de 42

Clase 22 / 42

Daniel Santiago Perez Ducuara

Hace 6 años

Lo hice antes de ver el video, y con un menú. Me quedó así: bubblesort.c

#include <stdio.h>
#include "bubblesort-func.h"

void menu(){
	int option=0;
    do{
        printf("\n-------------------------------\n");
        printf("            BUBBLE SORT :D\n");
        printf("1. Llenar o sobreescribir el array\n");
        printf("2. Imprimir el contenido del array\n");
        printf("3. Organizar el array\n");
        printf("4. Salir\n");
        printf("-------------------------------\n");
        printf("Digite su opción:");
        scanf("%i", &option);
		printf("\n");
		
        switch(option){
            case 1:
                getArray();
            break;
            case 2:
                printArray();
            break;
            case 3:
                bubbleSort();
            break;
            case 4:
                printf("Gracias por usar :D");
            break;
            default:
                printf("Opción inválida");
        }
		if((option != 1) && (option != 2)){
			printf("\n");
		}
    }while(option != 4);
}

int main(){
    menu();

    return 0;
}

bubblesort-func.h

int array[0];
int sizeArray=0;

void printArray(){
	if(sizeArray == 0){
		printf("Array vacío, no se puede imprimir :c\n");
	}else{
		for(int i=0; i<sizeArray; i++){
			printf("Array[%i] = %i\n", i, array[i]);
		}
	}
}

void getArray(){
    printf("Digite el tamaño de su array: ");
    scanf("%i", &sizeArray);
    
    for(int i=0; i<sizeArray; i++){
        printf("Digite el valor de la posición %i en su array: ", i);
        scanf("%i", &array[i]);
    }
}

void mayorMenor(){
    int casos=1;
    while(casos != 0){
        casos=0;
    	for(int i=0; i<sizeArray-1; i++){     //Se recorre hasta sizeArray-1 porque si llega hasta sizeArray se compara con sizeArray+1 (que sería un espacio vacío, un 0)
    	    if(array[i+1] < array[i]){
    	        int temp = array[i];
    	        array[i] = array[i+1];
    	        array[i+1] = temp;
    	        casos++;
    	    }
    	}
    }
}

void menorMayor(){
	int casos=1;
    while(casos != 0){
        casos=0;
    	for(int i=0; i<sizeArray-1; i++){
    	    if(array[i+1] > array[i]){
    	        int temp = array[i];
    	        array[i] = array[i+1];
    	        array[i+1] = temp;
    	        casos++;
    	    }
    	}
    }
}

void bubbleSort(){
	if(sizeArray == 0){
		printf("Array vacío, no se puede organizar :c");
	}else{
		int option=0;
		printf("1. De mayor a menor\n");
		printf("2. De menor a mayor\n");
		printf("Opción:");
		scanf("%i", &option);
		
		switch(option){
			case 1:
				mayorMenor();
			break;
			case 2:
				menorMayor();
			break;
			default:
				printf("Opción inválida");
		}
	}
}

Comentarios (85)85 comentarios

Daniel Ramírez Castaño

Hace 7 años

Acá una prueba de escritorio de la implementación del doble for en la función bubbleSort(): Lo que hace esta implementación es ubicar los elementos de mayor valor al extremo del arreglo en cada iteración del for anidado.

Aldo Said Salas Rodríguez

Tengo una duda. ¿Por que en la segunda iteración i vale 0?

Después de analizar y buscar por internet para que servia i me di cuenta que son el número de recorridos que hace en todo el array. Como quiera muchas gracias por mostrar los valores de i en cada iteración, me fue más fácil comprender para que servia i y j. :)

Danelia Sanchez Sanchez

Hace 8 años

La condición del segundo for j < n - i - 1 reduce el número de comparaciones en cada iteración. Con esto ya no se comparan los elementos ya ordenados a la derecha del arreglo, es decir, los elementos mayores. En cada iteración, el elemento mayor de la parte del arreglo que aún no está ordenada se coloca en su posición.

David Barreto

Fue util haber hecho el curso de Introducción a Lenguaje C antes de venir aquí.

Miqueas Gamero

Si, de hecho, hay un sección en la que programamos linked lists

Bernardo Aguayo Ortega

sin duda alguna, digo yo no lo hice pero en la uni nos enseñaron a programar con c

David Behar

IMPORTANTE AL HABLAR DE BURBUJA recuerden que para el ordenamiento de la burbuja vamos a tener que guardar el valor cada que hagamos una iteración en una variable temporal porque necesitamos poder guardarlo mientras hacemos el cambio.

Ricardo Celis

Profesor

así es, esto es importantísimo

Daniel Alberto Esquinazi

En bubble sort cuando estamos ordenando de forma asc, despues de cada recorrido completo del array tendremos al menos el ultimo valor de la lista ordenado. Es por esto que en el segundo ciclo no se debe recorrer hasta el final sino hast final-numeroDeIteracionesAnteriores.

function bubbleSort(sortedList = []) {
    const length = sortedList.length;
    
    for (let i = 0; i< length - 1; i++) {
        for (let j=1; j<length-i; j++) {
            if (sortedList[j-1] > sortedList[j]) {
                const swap = sortedList[j-1];
                sortedList[j-1] = sortedList[j];
                sortedList[j] = swap;
            }
        }
    }

    return sortedList;
}

function sort() {
    let list = [4,2,6,8,1,5];
    console.log(`Unsorted List: ${list}`);
    // Desordered List: 4,2,6,8,1,5
    console.log(`Sorted List: ${bubbleSort([...list])}`);
    // Sorted List: 1,2,4,5,6,8
}

sort();

Samar Jaffal

Gracias por explicar ese detalle, estaba haciendo el recorrido en frio para entender la función y si me di cuenta que con cada recorrido de i se le resta uno a los recorridos en j. Por lo que si es cierto, el algoritmo va ordenando desde el final hasta el inicio.

Hernán Giraldo

Ejemplo realizado con Angular, que muestra en pantalla el proceso que se llevó a cabo para ordenar el array.

Jonathan Gonzalez Botero

Muy buen trabajo, quedo genial

Zalo Testa

Ayuda mucho viéndolo! Gracias!

Joel Vicente Nieto Gómez

porque al ejecutar la función:

cambiar_pos(&vector_entrada[j], &vector_entrada[j+1])```

Se utiliza el simbolo&?

Saúl Alejandro Tapia Loya

Gracias por tu excelente explicación, me sirvió mejor para entender.

Eduardo Osorio

Bien pobre la explicacion del profesor sobre como funciona la logica del j < n - i - 1 en el for anidado. 👎

Franco Losardo

El mejor porfesor para explicar es Freddy, por lejos!

Gibrán Pelayo Miranda

For comparison purposes in an array, two adjacent cells are needed; in an array of 6 elements, only 5 comparisons take place; in an array of 10 elements, 9 comparisons, and so on.

So for 7 elements, just 6 comparisons are done, hence the general rule of n-1 in the outer for loop

About the n-1-i expression, remember that the highest (or lowest, depending on the ordering criterion) value in the bubble sort goes to the last position in the array after the first cycle, so there is no need to compare that value with anything else, therefore the array has to be "shortened" 1 cell at a time, and the value of i in the outer loop is the counter responsible for that in the inner loop:

5 | 3 | 9 | 20 | elements (n) = 4

after first cycle (i = 0), 20 has reached its correct position within the array (using an ascending order), leaving us with an array of 3 elements; in next cycle, i will be equal to 1, and as n-1 remains the same, we need to substract 1 in that expression to "shorten" the array: n-1-i = 4-1-1 = 2, which is the index of the last element in that new array as well as the quantity of comparisons needed.

This is very good explanation! +1

Aaron Gabriel Jaimes Santofimio

Mi implementación en Java

class Main {
  public static void main(String[] args) {
    int[] array = {5,8,9,2,1};
    for(int i=0; i<array.length; i++)
      for(int j=0; j<array.length; j++)
        if(j+1<array.length)
          if(array[j]>array[j+1]){
            int temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
          }
    
    for(int x=0; x<array.length; x++)
      System.out.println(array[x]);
  }
}

Jose Antonio Rojas Ollarves

Les comparto un video de bubble sort, muy practico y entendible tambien para reforzar la clase: https://www.youtube.com/watch?v=P_xNb8nFgmA&ab_channel=Programaci%C3%B3nATS

Eduardo Kiriakos Piazza

Aquí mi código en python:

def bubbleSort(messy_list):
  print("Ordenando..")
  for _ in range(len(messy_list)):
    for i in range(len(messy_list)-1):
        left = messy_list[i]
        right = messy_list[i+1]
        if left > right:
          messy_list[i] = right
          messy_list[i+1] = left

  return messy_list


if __name__ == '__main__':
  messy_list = [5,9,2,6,1,3,7,8]
  print(messy_list)
  ordered_list = bubbleSort(messy_list)
  print(ordered_list)

Alejandro P

Johann Moreno

¿Que pasaría si usamos paréntesis en el for de j para separar la operación matemática (la resta)?.

Ignacio Saccomano

Funcionaría bien, aunque lo podés probar

Eduardo García

La parte que no logré entender bien es la del for anidado, n-i-1; dice que para comenzar en la posición anterior. Sé que es para saber que nos estamos poniendo en la celda correcta, pero no entiendo como

CRISTIAN BARBERO PÉREZ

El n-i-1 es porque en cada vuelta el número más grande queda al final del array, entonces no es necesario llegar hasta el final.

Es decir, si tu array tiene una longitud de 10 por ejemplo:

Para i=0 tendrás que ir hasta j=8 (hasta el final) Para i=1 solo tendrás que ir hasta j=8, ya que el último número está en la posición correcta Para i=2 habrá que ir hasta j=7, ya que las dos últimas posiciones son las correctas Y así sucesivamente.

Espero que se entienda, te dejo un ejemplo del algoritmo realizado paso a paso. En él se ve que cuando termina la primera vuelta (i=0) el número 21 ya está en la posición adecuada, por lo que en la siguiente iteración te puedes "olvidar" de él.

Para i=0 tendrás que ir hasta j=8 (hasta el final) Para i=1 solo tendrás que ir hasta j=7, ya que el último número está en la posición correcta Para i=2 habrá que ir hasta j=6, ya que las dos últimas posiciones son las correctas Y así sucesivamente.

Mauricio Rodriguez Romero

Hola Amigos, no entiendo cual es la función de los asteriscos( * ) en las variables *n1 y *n2. Pero les digo que si no pongo esos asteriscos, el programa no me funciona, no ordena.

void cambiarPosition(int *valor1, int *valor2) { int temporal = *valor1; *valor1 = *valor2; *valor2 = temporal; }

Luis Lira

Tengo entendido que en C sirve para apuntadores, así los valores modificados serán almacenados en el mismo espacio de memoria. Para que te quede más claro te recomiendo investigar un poco más sobre lo que son paso por valor y paso por referencia :D

Ivan E. Batista-Ochoa

Sí, tal como dice Luis, en C sirve para apuntar a direcciones en memoria. Este tema lo pueden encontrar como apuntadores o punteros en C o pointers. Te recomiendo revisar este enlace en el cual se habla de pasar variables por valor y por referencia.

Por acá te dejo una lectura sobre punteros en C.

Adicionalmente, te recomiendo tomar el curso Introducción a C. o por lo menos mirar las clases de punteros. Te va a ayudar mucho a entenderlo.

Luis Angel Pasos Montalvo

Por que le puso el "&" antes del array? y los * antes de n1 y n2?

Alex Camacho

Aquí hay una explicación paso a paso del Bubble sort, espero que con esto puedas clarificar mejor.

Hola, Luis. En C sirve para apuntar a direcciones en memoria. Este tema lo pueden encontrar como apuntadores o punteros en C o pointers. También es importante entender como se pasan variables. Para esto te recomiendo revisar este enlace en el cual se habla de pasar variables por valor y por referencia.

La explicación del bubblesort se me hizo muy enredada por lo que ayudándome con este video y probando pude entenderlo a la perfección. Si alguien quiere que lo ayude con gusto estoy ;)

https://www.youtube.com/watch?v=Jdtq5uKz-w4&t=430s

Recursos

Resumen

Implementación de Bubble Sort en C paso a paso

Progreso del curso

Bienvenido al Curso

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

¿Qué sigue?