Implementación de Bubble Sort en C paso a paso

Curso Práctico de Estructuras de Datos y Algoritmos

Contenido del curso

Bienvenido al Curso

1
Algoritmos y Estructuras de Datos: Curso Básico
02:17 min

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?

41
Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento
11:14 min

¿Qué sigue?

42
Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos
02:26 min

Tomar examen

Implementación de Bubble Sort en C paso a paso

Todos los cursos GRATIS

Se acaba en:

00díasd:00hrsh:00minm:00segs

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.

Daniel Santiago Perez Ducuara

Estudiante

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");
		}
	}
}

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

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

Hace 8 años

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

Creo que esto no se explicó en el curso, pero en la función "cambiarpos" los valores que recibe tienen que ser apuntadores a enteros, un apuntador es simplemente una variable que, como su nombre lo dice "apunta" a una dirección de memoria de un dato específico, en este caso, le estamos enviando las direcciones de memoria de vector_entrada[j] y vector_entrada[ j + 1 ]. Entonces

Utilizamos & para decir que queremos la dirección de memoria de una variable

En la función cambiar_pos están los símbolos *, eso es para indicar que vas a acceder al valor que guarda ese pedazo de la memoria, no la dirección en sí, pero te preguntarás ¿Y para qué estamos utilizando apuntadores aquí? ¿Por qué no utilizamos variables normales y ya?

La respuesta es que, cuando le pasas un parámetro a una función, esta crea un "clon" de él, si modificas la variable como parámetro dentro de la función, estás cambiando el clon que tiene la función, pero la variable original sigue intacta, al utilizar apuntadores puedes evadir esto, ya que la posición en memoria es la misma no importa donde estés, así que se envía la dirección como parámetro y luego se accede a sus valores.

Imagina un archivo de un equipo, cada quien lo puede descargar y trabajarlo por su cuenta, o pueden utilizar alguna técnica para poder trabajar todos en la versión original al mismo tiempo, como un editor grupal en línea.

Ojalá te ayude, saludos!

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

aquí esta mi solucion en python

# Definicion de variables
numbers_array = [4, 2, 3, 6, 1, 5]
esta_ordenado = False


def ordenar_array(list):
    global esta_ordenado
    # imprime el arreglo original
    print("Arreglo original\n")
    for x in list:
        print(x, end=' ')
    print("\n")

    # algoritmo de ordenamiento
    while not esta_ordenado:
        # ciclo de ordenamiento
        for x in range(0, 5):
            if list[x] > list[x + 1]:
                temp = list[x]
                list[x] = list[x + 1]
                list[x + 1] = temp
        # ciclo de verificacion
        for x in range(0, 5):
            if list[x] > list[x + 1]:
                esta_ordenado = False
                break
            else:
                esta_ordenado = True

    print("Arreglo ordenado\n")
    for x in list:
        print(x, end=' ')
    print("\n")


if __name__ == "__main__":
    ordenar_array(numbers_array)

Resultado

Arreglo original

4 2 3 6 1 5 

Arreglo ordenado

1 2 3 4 5 6

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

La pregunta tonta del día; cual es el funcionamiento del primer

<for _ in range(len(messy_list)):>

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

Implementación de Bubble Sort en C paso a paso

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort

Ordenamiento de Arrays con MergeSort en C

Algoritmos de Ordenamiento de Datos de Mayor a Menor

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Ordenamiento Quick Sort en Python paso a paso

Algoritmos 'Greedy'

Algoritmos Voraces: Principios y Aplicaciones Prácticas

Implementación de Algoritmo Greedy para Cambio de Monedas

Cambio de Monedas en C++: Implementación y Ejecución

Grafos y árboles

Introducción a Árboles y Grafos: Estructuras de Datos Básicas

Estructura de Datos: Árboles y sus Componentes Básicos

¿Cómo comparar Algoritmos?

Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento

¿Qué sigue?

Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos

Todos los cursos GRATIS

Resumen