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.
Muy buen aporte AgroSinergía! no olvides compartirnos tu código =)
Bubble Sort (código de la clase)
#include <stdio.h>voidcambiar_pos(int *n1, int *n2){ int temp =*n1;*n1 =*n2;*n2 = temp;}voidbubbleSort(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]);}}}voidprintArray(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");return0;}
que significa el * en las entradas n1 y n2?
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.
Gracias
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.
Gracias, me suelo frustrar cuando no entiendo este tipo de cosas. Buen aporte!
Gracias, igual tenía la misma duda.
Esta es mi versión del código, ordenando de menor a mayor:
#include <stdio.h>#define TAM10voidBurbuja(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;}}}voidEntradaArreglo(int array[]){ int i;for(i =0; i <TAM; i++){printf("Elemento %d: ", i+1);scanf("%d",&array[i]);}}voidImprimeArreglo(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);return0;}
Y la ejecución:
Introduce los elementos a ordenar:Elemento1:88Elemento2:25Elemento3:73Elemento4:45Elemento5:12Elemento6:30Elemento7:1Elemento8:126Elemento9:98Elemento10:47ArregloOriginal:88257345123011269847ArregloOrdenado:11225304547738898126
Excelente trabajo Dane!!
Qué bonita versión
Vuelvo a compartir un gif que un compañero anteriormente había publicado en clases anteriores:
Screenshot del diagrama de flujo del algoritmo:
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
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
¡Gracias! Buscaba esta duda y respuesta
Para hacerlo ascendente basta con cambiar el < dentro del if, por > y listo.
voidbubbleSort(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]);}}}
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 =)
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;voidcambiar_pos(int *n1, int *n2){ int temp =*n1;*n1 =*n2;*n2 = temp;}voidbubbleSort(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]);}}}}voidprintArray(int vector_entrada[], int size){ int i;for(i=0; i<size; i++){printf("%d ", vector_entrada[i]);}printf("\nFin del ordenamiento, saludos\n");}voidintrodArray(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>voidcambiar_pos(int *n1, int *n2){ int temp =*n1;*n1 =*n2;*n2 = temp;}voidprintArray(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);}}}
No entendi porque entes de cada variable utilizas el ** * **
Según entendí el * indica que es un puntero
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>voidcambiarP(int *n1,int *n2){ int temp =*n2;*n2=*n1;*n1=temp;}voidbubbleSort(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]);}}}}voidprintArray(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);return0;}
Y esta seria la ejecucion :
Bienvenido al ordenador de numeros, ingrese la cantidad de numeros a ordenar:8Ahora vamos a ingresar todos los numeros:-14-43-8-123-3-21-856-12Felicidades, 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]```
Valores a tener en cuenta al implementar el algoritmo de ordenamiento BubbleSort.
Diagrama de flujo del algoritmo BubbleSort
Merge Sort: algoritmo de ordenamiento basado en comparaciones.
Código en python:
import random
def bubbleSort(numbers): higher =len(numbers)-1 iterations =0while iterations < higher-1:for idx inrange(higher):if numbers[idx]> numbers[idx+1]: temp = numbers[idx+1] numbers[idx+1]= numbers[idx] numbers[idx]= temp
iterations = iterations +1return 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 -=1print("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))
#include <stdio.h>voidcambiarPos(int *n1, int *n2){ int temp =*n1;*n1 =*n2;*n2 = temp;}voidbubbleSort(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]);}}}}voidprintArray(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");return0;}
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 consolafor(int e =0; e < len; e++){printf("%d\n", lista[e]);}}
el asterisco para que se usa profesor que lo veo antes de n1 y n2?
