Aquí están los datos con coma:
3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57
Bienvenido al Curso
Introducción al curso básico de algoritmos y estructuras de datos
Introducción a los algoritmos
¿Qué entiende una computadora?
Lenguajes de programación
Estructuras de datos
¿Qué es un algoritmo?
Metodología para la construcción de un algoritmo
Variables y tipos de datos
User defined data types
Instalando Ubuntu Bash en Windows
Creando nuestro user defined data type
Abstract Data Types básicos: Lists, Stacks, Queues
Explicación gráfica Data Types básicos
Glosario de funciones para Abstract Data Types
Clases y objetos
Creando tu primera Queue: Arrays
Creando tu primera Queue: implementación.
Creando tu primera Queue: implementar la función enQueue
Creando tu primera Queue: implementar la función deQueue
Creando tu primera Queue: main code
Algoritmos de ordenamiento
Algoritmos de ordenamiento
Bubble sort
Bubble sort: implementación
Bubble sort: main code
Insertion sort
Desafío: implementa un algoritmo de ordenamiento
Recursividad
Recursividad
La función Factorial, calculando el factorial recursivamente
Manejo de cadenas de caracteres
Arte: Generando arte recursivo
Divide and conquer y programación dinámica
Divide and Conquer (divide y vencerás)
Qué es la programación dinámica (divide y vencerás v2.0)
MergeSort
Desafío: Buscar el algortimo más rápido de sort
Implementando QuickSort con Python
Implementando QuickSort con Python: main code
Algoritmos 'Greedy'
Qué son los Greedy Algorithm
Ejercicio de programación greedy
Ejercio de programación greedy: main code
Grafos y árboles
Grafos y sus aplicaciones
Árboles
¿Cómo comparar Algoritmos?
Cómo comparar algoritmos y ritmo de crecimiento
¿Qué sigue?
Cierre del curso y siguientes pasos
Desafío: Buscar el algortimo más rápido de sort
33/42Lectura
¡Hola! en esta lectura te invito a que realices el siguiente desafío: implementa un algoritmo de ordenamiento que sea capaz de ordenar de mayor a menor el set de datos dado, comparte tus resultados en la sección de comentarios, ¡comparte el código que utilizaste también!
...
Regístrate o inicia sesión para leer el resto del contenido.
Aportes 114
Preguntas 0
Ordenar por:
Cordial saludo comunidad
No es fácil para mi entender la lógica de los códigos compartidos por ustedes, comparto la solución más básica que he entendido de acuerdo a las clases anteriores, apreciaré sus comentarios y o recomendaciones para poder subir el nivel de comprensión en programación, gracias.
def mergeSort(array: list):
n1 = len(array)
for _ in range(n1 - 1):
for i in range(n1 - 1):
temp = array[i]
if (array[i] > array[i+1]):
array[i] = array [i + 1]
array[i+1] = temp
return array
lista = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57]
mergeSort(lista)
print(lista)
Slds.
<h1>Función merge_sort</h1>
def merge_sort(lista):
“”“
Este if comprueba la longitud de la lista.
”""
if len(lista) < 2:
return lista
# De lo contrario, se divide en 2
else:
middle = len(lista) // 2
right = merge_sort(lista[:middle])
left = merge_sort(lista[middle:])
return merge(right, left)
def merge(lista1, lista2):
""“
merge se encargara de intercalar los elementos de las dos
divisiones.
”""
i, j = 0, 0 # Variables de incremento
result = [] # Lista de resultado
while(i < len(lista1) and j < len(lista2)):
if (lista1[i] < lista2[j]):
result.append(lista1[i])
i += 1
else:
result.append(lista2[j])
j += 1
result += lista1[i:]
result += lista2[j:]
# Retornamos el resultados
return result
lista = [3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
merge_sort_result = merge_sort(lista)
print(merge_sort_result)
realice el reto usando merge sort en java
public class Ordenamiento {
public int [] margeSort(int [] a)//divide en dos array y ordena
{
//caso base
if (a.length <= 1)
{
return a;
}
else {
int[] left;
int[] right;
right = new int[a.length / 2];
if (a.length % 2 == 0) {
left = new int[a.length / 2];
} else {
left = new int[(a.length / 2 + 1)];
}
int i;
for (i = 0; i < left.length; i++) {
left[i] = a[i];
}
int k = 0;
for (int j = i; j < a.length; j++) {
right[k] = a[j];
k++;
}
//recursividad
int[] arrayOrdenado = merge(margeSort(left), margeSort(right));
return arrayOrdenado;
}
}
public int [] merge(int[]b, int []c)//une los dos array en uno
{
int i = 0;
int j = 0;
int [] result = new int [b.length + c.length];
for (int k = 0; k < result.length; k++)
{
if (b[i] < c[j])
{
result[k] = b[i];
i ++;
}
else{
result[k] = c[j];
j++;
}
if (i == b.length)
{
k++;
for (j = j; j< c.length; j++)
{
result[k] = c[j];
k++;
}
}
else if(j == c.length)
{
k++;
for (i = i; i< b.length; i++)
{
result[k] = b[i];
k++;
}
}
}
return result;
}
public void imprimir(int [] arr)
{
System.out.println("impresion de array: ");
for (int i = 0; i < arr.length; i++){
System.out.println(arr[i] + ",");
}
}
public static void main(String[] args) {
Ordenamiento s = new Ordenamiento();
int [] arr1 = {3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57};
int [] ordenado = s.margeSort(arr1);
System.out.println("array inicial: " );
s.imprimir(arr1);
System.out.println("array ordenado: ");
s.imprimir(ordenado);
}
}
Merge Sort Python
def mergeSort(arrayData):
if len(arrayData) > 1:
midArray = len(arrayData)//2
leftDivide = arrayData[:midArray]
rightDivide = arrayData[midArray:]
mergeSort(leftDivide)
mergeSort(rightDivide)
# i = left, j = right, t = temporary array
i = j = t = 0
while i < len(leftDivide) and j < len(rightDivide):
if leftDivide[i] > rightDivide[j]:
arrayData[t] = leftDivide[i]
i += 1
else:
arrayData[t] = rightDivide[j]
j += 1
t += 1
while i < len(leftDivide):
arrayData[t] = leftDivide[i]
i += 1
t += 1
while j < len(rightDivide):
arrayData[t] = rightDivide[j]
j += 1
t += 1
if __name__ == "__main__":
arrayData = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57]
print(f'Array before merge {arrayData}')
mergeSort(arrayData)
print(f'Array after merge {arrayData}')
Con el merge_sort (Divide y venceras), se realiza más rápido el trabajo.
SELECTION SORT:
#include <stdio.h>
void swap(int *n1, int *n2)
{
int temp = *n1;
*n1 = *n2;
*n2 = temp;
}
void selectionSortGreater(int S[], int n)
{
int i, j, greater;
for (i = n - 1; i >= 0; i--)
{
greater = i;
for (j = i; j >= 0; j--)
{
if (S[j] < S[greater])
greater = j;
}
swap(&S[i], &S[greater]);
}
}
void print(int S[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d, ", S[i]);
printf("\n");
}
int main(int argc, char const *argv[])
{
int intArray[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int sizeOf = sizeof(intArray) / sizeof(intArray[0]);
selectionSortGreater(intArray, sizeOf);
print(intArray, sizeOf);
return 0;
}
RESULTADO:
Les dejo la implementación del algoritmo ShellSort:
#include <stdio.h>
#define N 100
void shellShort(int array[], int n)
{
int inc = (int)(n / 2);
int j, temp;
for(; inc > 0; inc /= 2)
{
for(int i = inc; i < n; i++)
{
j = i - inc;
while(j >= 0)
{
if(array[j] <= array[j + inc])
{
temp = array[j];
array[j] = array[j + inc];
array[j + inc] = temp;
}
else
break;
j = j - inc;
}
}
}
}
void print_array(int arr[], int n)
{
for(int i = 0; i < n; i++)
printf("%d, ", arr[i]);
}
int main()
{
FILE *archivo;
int array[N];
archivo = fopen("datos.dat", "rb");
if(archivo != NULL)
{
for(int i = 0; i < N; i++)
fscanf(archivo, "%d", &array[i]);
fclose(archivo);
shellShort(array, N);
print_array(array, N);
}
else
printf("No se leyo el archivo");
return 0;
}
Resultados:
https://repl.it/@DaneliaSanchez/shellSort
El algoritmo es muy parecido a uno que se hace en el curso de OOP y Algoritmos con Python. Se los recomiendo un montón y les dejo el código si les interesa:
import random
def ordenamiento_mezcla(lista):
if len(lista) > 1:
medio = len(lista) // 2
izquierda = lista[:medio]
derecha = lista[medio:]
print(izquierda, "*" * 5, derecha)
# Llamada recursiva en cada mitad
ordenamiento_mezcla(izquierda)
ordenamiento_mezcla(derecha)
# Iteradores para recorrer las sublistas
i = 0
j = 0
# Iterador de la lista principal
k = 0
while i < len(izquierda) and j < len(derecha):
if izquierda[i] < derecha[j]:
lista[k] = izquierda[i]
i += 1
else:
lista[k] = derecha[j]
j += 1
k += 1
while i < len(izquierda):
lista[k] = izquierda[i]
i += 1
k += 1
while j < len(derecha):
lista[k] = derecha[j]
j += 1
k += 1
print(f'Izquierda {izquierda}, derecha {derecha}')
print(lista)
print("-" * 50)
return lista
if __name__ == "__main__":
list_size = int(input("¿De qué tamaño quieres la lista? "))
lista = [random.randint(0, 50) for i in range(list_size)]
print(lista)
print("-" * 2)
lista_ordenada = ordenamiento_mezcla(lista)
print(lista_ordenada)```
Aquí esta mi código utilizando un bubble sort
def bubble_sort(arr):
for i in range(len(arr)-1, 0, -1):
for j in range(i):
if arr[j] > arr[j+1]:
temp = arr [j]
arr[j] = arr[j+1]
arr[j+1] = temp
print(arr)
bubble_sort([3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57])```
Hola, realicé el ordenamiento mediante merge-Sort usando recursividad.
const data = require('./data.json');
/* el archivo contiene este formato:
{
"valores": [
3,
94,
86,
.
]
} */
arreglo = data.valores;
let mergeSort = (arreglo) => {
//posiciones:
let inicio = 0;
let final = arreglo.length + 1 || size - 1; //tamaño del arreglo
let medio = (inicio + final)/2;
//dividir arreglo:
if(arreglo.length != 1){
//dividir
let arreglo1 = arreglo.splice(0, medio);
let arreglo2 = arreglo.splice(-medio);
mergeSort(arreglo1);
mergeSort(arreglo2);
//unir
merge(arreglo, arreglo1, arreglo2);
}
}
let merge = ( arreglo, arreglo1, arreglo2) => {
let n = arreglo1.length + arreglo2.length // tamaño total del arreglo
let pos1 = 0;
let pos2 = 0;
for (let i = 0; i < n; i++) {
if( pos1 < arreglo1.length && pos2 < arreglo2.length){
if( arreglo1[pos1] <= arreglo2[pos2] ){
arreglo[i] = arreglo1[pos1];
pos1++;
}else{
arreglo[i] = arreglo2[pos2];
pos2++;
}
}else{
if (pos1 < arreglo1.length){
arreglo[i] = arreglo1[pos1];
pos1++;
}
if (pos2 < arreglo2.length){
arreglo[i] = arreglo2[pos2];
pos2++;
}
}
}
}
let imprimir = (arreglo) =>{
console.log(arreglo);
}
mergeSort(arreglo);
imprimir( arreglo );
/*
resultado:
[
1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10,
12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25,
26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38,
39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45,
47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59,
60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72,
74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86,
86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98,
98, 99, 99, 100
]*/```
mergeSort en python
def mergeSort(lista):
if len(lista) > 1:
mid = len(lista) // 2
izq = lista[:mid]
der = lista[mid:]
mergeSort(izq)
mergeSort(der)
i = j = k = 0
while i < len(izq) and j < len(der):
if izq[i] > der [j]:
lista[k] = izq[i]
i += 1
else:
lista[k] = der[j]
j += 1
k += 1
while i < len(izq):
lista[k] = izq[i]
i += 1
k += 1
while j < len(der):
lista[k] = der[j]
j += 1
k += 1
return lista
if __name__ == '__main__':
lista = [ 3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59,
53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57,
82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8,
45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57 ]
lista_ordenada = mergeSort(lista)
print(lista_ordenada)```
Reto, resuelto con merge sort
#include<stdio.h>
int merge(int arr[],int l,int m,int h)
{
int temp[h-l+1];
int i=l,j=m+1, k=0;
while (i<=m && j<=h)
{
if (arr[i]<=arr[j]) {
temp[k]=arr[i];
k++; i++;
}
else {
temp[k]=arr[j];
k++; j++;
}
}
while (i<=m)
{
temp[k]=arr[i];
k++; i++;
}
while (j<=h)
{
temp[k]=arr[j];
k++; j++;
}
for (i = l; i <=h ; i++)
{
arr[i]=temp[i-l];
}
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
return 0;
}
int main()
{
int n,i;
int arr[]={3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,67,100,24,67,38,57
};
n=sizeof(arr)/sizeof(arr[0]);
merge_sort(arr,0,n-1); // sort the array
printf("Sorted array:"); // print sorted array
for(i=0;i<n;i++)
printf("%d, ",arr[i]);
return 0;
}
#include<stdio.h>
int arr[]={3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,
57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
int main()
{
int i;
merge_sort(arr,0,n-1); // sort the array
printf("Sorted array: {"); // print sorted array
for(i=0;i<n;i++)
printf("%d, ",arr[i]);
printf("}");
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
return 0;
}
int merge(int arr[],int l,int m,int h)
{
int arr1[n/2],arr2[n/2]; // Two temporary arrays to hold the two arrays to be merged
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0;i<n1;i++)
arr1[i]=arr[l+i];
for(j=0;j<n2;j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;j=0;
for(k=l;k<=h;k++) //process of combining two sorted arrays
{
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
Resultado:
Sorted array: {1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10, 12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25, 26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38, 39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45, 47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59, 60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72, 74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86, 86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98, 98, 99, 99, 100, }
agregando una decisión en el código:
DATA = [
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57
]
def merge_sort(not_ordered_list):
amount_data = len(not_ordered_list)
ordered_list = []
answer = str(input('do you want to order the data from min or max?: '))
if answer == 'max':
while len(ordered_list) != amount_data:
ordered_list += [max(not_ordered_list)]
not_ordered_list.remove(max(not_ordered_list))
return ordered_list
elif answer == 'min':
while len(ordered_list) != amount_data:
ordered_list += [min(not_ordered_list)]
not_ordered_list.remove(min(not_ordered_list))
return ordered_list
else:
print('You must enter min or max')
if __name__ == '__main__':
ordered_data = merge_sort(DATA)
print(ordered_data)```
Merge Sort (JAVA):
public class MergeSort
{
// Driver method
public static void main(String args[])
{
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78,
25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60,
74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52,
44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9,
98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74,
56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
void sort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2;
sort(arr, l, m);
sort(arr , m+1, r);
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int [n1];
int R[] = new int [n2];
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (L[i] >= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Usé el método de QuickSort en Python3 ya que me parece que es muy fácil de entender ese método:
def ordenar(not_ordened_list):
if len(not_ordened_list) == 0:
return []
elif len(not_ordened_list) ==1:
return not_ordened_list
left = []
right = []
equals = []
pivote = not_ordened_list[0]
for n in not_ordened_list[1:]:
if pivote > n:
left.append(n)
elif pivote < n:
right.append(n)
elif pivote == n:
equals.append(n)
return ordenar(left) + [pivote] + equals + ordenar(right)
def run():
not_ordened_list = [
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
print('LISTA NO ORDENADA')
print(not_ordened_list)
ordened_list = ordenar(not_ordened_list)
print('\nLISTA ORDENADA')
print(ordened_list)
if __name__ == '__main__':
run()```
#include <stdio.h>
#include <stdlib.h>
int main()
{
int arreglo[] ={ 3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15,
22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59,
53,57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48,
80, 44, 25, 68, 1, 89, 77, 60 }; //*/
int tam = sizeof(arreglo)/sizeof(arreglo[0]);
/*//Se ingresa el tamaño del arreglo
int tam;
printf("Ingrese el tamaño del arreglo: ");
scanf("%i", &tam);
//Se ingresan los valores del arreglo
printf("Ingrese los %i valores del arreglo: ", tam);
for(int i=0; i<tam; i++)
{
scanf("%i", &arreglo[i]);
}
//Se imprimen lo valores del arreglo
int i = 0;
printf("Los valores del arreglo son: [");
while(i<tam)
{
printf("%i,", arreglo[i]);
i++;
}
printf("] \n"); */
//Se realiza el proceso de merge, donde se Divide, Ordena y Combina.
merge_sort(arreglo, 0, tam-1);
//Se realiza la impresion del arreglo ordenado
printf("El arreglo ordenado queda de la siguiente manera: [");
for(int i=0;i<tam;i++)
printf("%d, ",arreglo[i]);
printf("] \n");
return 0;
}
int merge_sort(int arreglo[], int low, int high)
{
int mid;
if(low<high)
{
//Se escoge una mitad del arreglo
mid = (low+high)/2;
//Divide et Impera
merge_sort(arreglo,low,mid);
merge_sort(arreglo,mid+1,high);
//Combina
merge(arreglo,low,mid,high);
}
return 0;
}
int merge(int arreglo[], int l, int m, int h)
{
//Las dos divisiones realizadas por los merge. Se dividiran en estos dos arreglos.
int arr1[10];
int arr2[10];
int n1, n2, i, j, k;
//a traves de estos calculos se establecen los limetes para cada arreglo.
n1 = m-l+1;
n2 = h-m;
//Los limetes establicidos nos ayudaran a ordenar los números establecidos en cada arreglo.
//Se ordenan los números.
for(i=0; i<n1; i++)
arr1[i] = arreglo[l+i];
for(j=0; j<n2; j++)
arr2[j] = arreglo[m+j+1];
//Las siguientes lineas establencen el limite del final de cada arreglo
arr1[i] = 9999;
arr2[i] = 9999;
//Se reinician los valores de I y J
i=0;
j=0;
// El siguiente ciclo, se encargará de combinar los dos arreglos. llegando asi a la fase final del algoritmo
for(k=0; k<=h; k++)
{
if(arr1[i] <= arr2[j])
arreglo[k] = arr1[i++];
else
arreglo[k] = arr2[j++];
}
return 0;
}```
Utilize el Merge Sort por su versatilidad con muchos datos, lo hice en JS:
function merge(leftArr, rightArr) {
var sortedArr = [];
while (leftArr.length && rightArr.length) {
if (leftArr[0] <= rightArr[0]) {
sortedArr.push(leftArr[0]);
leftArr = leftArr.slice(1)
} else {
sortedArr.push(rightArr[0]);
rightArr = rightArr.slice(1)
}
}
while (leftArr.length)
sortedArr.push(leftArr.shift());
while (rightArr.length)
sortedArr.push(rightArr.shift());
return sortedArr;
}
function mergesort(arr) {
if (arr.length < 2) {
return arr; }
else {
var midpoint = parseInt(arr.length / 2);
var leftArr = arr.slice(0, midpoint);
var rightArr = arr.slice(midpoint, arr.length);
return merge(mergesort(leftArr), mergesort(rightArr));
}
}
let unsortedArr = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));```
- Implementación simple de Bubble en python
def get_data_txt(path:str):
numbers_to_order:list = []
with open(path,'r',encoding='utf-8') as file:
for line in file:
line = line.splitlines()[0]
line = line.split('\t')
for number in line:
numbers_to_order.append(int(number))
return numbers_to_order
def order_numbers_list_bubble(list_to_order:list):
len_list = len(list_to_order)
for i in range(len_list):
for j in range(0, len_list -1):
# Comparación y cambio
if list_to_order[j] > list_to_order[j+1]:
supp = list_to_order[j]
list_to_order[j] = list_to_order[j+1]
list_to_order[j+1] = supp
return list_to_order
data = get_data_txt('./setDeDatos.txt')
order_list = order_numbers_list_bubble(data)
print(order_list)```
def ordenamiento_de_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
if __name__ == '__main__':
lista = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23,
78, 25, 2, 30, 45,98, 43, 98, 59, 53,57, 2, 64, 1, 41,32, 58, 19, 99, 60,
74, 48, 80, 44, 25,68, 1, 89, 77, 60,25, 99, 30, 76, 32,57, 82, 52, 44, 72,
87, 34, 87, 65, 30,54, 6, 31, 33, 44,44, 42, 82, 90, 17,9, 98, 28, 86, 69,
3, 17, 8, 45, 98,12, 47, 95, 43, 72,39, 41, 82, 74, 56,65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
lista_ordenda = ordenamiento_de_burbuja(lista)
print(lista_ordenda)```
quickSort en bash:
`quicksort() {`
` local pivot i smaller=() larger=()`
` if (($# == 0)); then`
` echo`
` return`
` fi`
` pivot=$1`
` shift`
` for i; do`
` if ((i < pivot)); then`
` smaller+=( "$i" )`
` else`
` larger+=( "$i" )`
` fi`
` done`
` quicksort "${smaller[@]}"`
` printf '%d ' "$pivot"`
` quicksort "${larger[@]}"`
`}`
`quicksort 3 94 86 82 90 10 87 36 61 8 17 15 22 10 23 78 25 2 30 45 98 43 98 59 53 57 2 64 1 41 32 58 19 99 60 74 48 80 44 25 68 1 89 77 60 25 99 30 76 32 57 82 52 44 72 87 34 87 65 30 54 6 31 33 44 44 42 82 90 17 9 98 28 86 69 3 17 8 45 98 12 47 95 43 72 39 41 82 74 56 65 79 50 26 67 100 24 67 38 57`
Aquí les comparto mi ejercicio comparando la velocidad entre bubble sort, insertion sort, merge sort y quick sort para el mismo array en javascript. Espero sea de apoyo 😃
/**
* Implements bubble sort algorithm
*/
function bubbleSort(array) {
for (let i = 0; i < array.length - 1; i++) {
for (let j = 0; j < array.length -i -1; j++) {
if (array[j] > array[j+1]) {
const temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}
/**
* Implements insertion sort algorithm
*/
function insertionSort(array) {
let current, j;
for (i = 1; i < array.length; i ++) {
current = array[i];
j = i - 1;
while (j >= 0 && array[j] > current) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = current;
}
return array;
}
/**
* Merge function used by mergeSort algorithm
*/
function _merge(firstHalf, lastHalf) {
let f = 0, l=0;
let newArray = [];
for (i=0; i < firstHalf.length + lastHalf.length; i++) {
if (firstHalf[f] === undefined) {
newArray = newArray.concat(lastHalf.slice(l, lastHalf.length));
return newArray;
}
if (lastHalf[l] === undefined) {
newArray = newArray.concat(firstHalf.slice(f, firstHalf.length));
return newArray;
}
if (firstHalf[f] > lastHalf[l]) {
newArray[i] = lastHalf[l];
l ++;
} else {
newArray[i] = firstHalf[f];
f ++;
}
}
return newArray;
}
/**
* Divide and merge function used by mergeSort algorithm
*/
function _divideAndMerge(array) {
if (array.length > 1) {
const middle = Math.ceil(array.length / 2);
const firstHalf = array.slice(0, middle);
const lastHalf = array.slice(middle);
return _merge(
_divideAndMerge(firstHalf),
_divideAndMerge(lastHalf),
);
} else {
return array;
}
}
/**
* Implements merge sort algorithm
*/
function mergeSort(array) {
return _divideAndMerge(array);
}
/**
* Partition function used by quick sort algorithm
*/
function _partition(array, start, end) {
const pivot = array[end];
let i = start -1;
for(let j = start; j <= end -1; j++) {
if (array[j] < pivot) {
i++;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
i ++;
const temp = array[i];
array[i] = array[end];
array[end] = temp;
return i;
}
/**
* sort function used by quick sort algorithm
*/
function _sort(array, start, end) {
if (end <= start) return // base case
const pivot = _partition(array, start, end);
_sort(array, start, pivot -1);
_sort(array, pivot + 1, end);
return array;
}
/**
* Implements quick sort algorithm
*/
function quickSort(array) {
return _sort(array, 0, array.length - 1);
}
const array = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
console.time("bubbleSort");
console.log(bubbleSort([...array]));
console.timeEnd("bubbleSort");
console.time("insertionSort");
console.log(insertionSort([...array]));
console.timeEnd("insertionSort");
console.time("mergeSort");
console.log(mergeSort([...array]));
console.timeEnd("mergeSort");
console.time("quicksort");
console.log(quickSort([...array]));
console.timeEnd("quicksort");
Resultado:
[
1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10,
12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25,
26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38,
39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45,
47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59,
60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72,
74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86,
86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98,
98, 99, 99, 100
]
bubbleSort: 14.27ms
[
1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10,
12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25,
26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38,
39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45,
47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59,
60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72,
74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86,
86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98,
98, 99, 99, 100
]
insertionSort: 0.528ms
[
1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10,
12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25,
26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38,
39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45,
47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59,
60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72,
74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86,
86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98,
98, 99, 99, 100
]
mergeSort: 0.607ms
[
1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10,
12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25,
26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38,
39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45,
47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59,
60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72,
74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86,
86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98,
98, 99, 99, 100
]
quicksort: 0.447ms
Challenge using Python:
Mi algoritmo en python:
import random
def mergeSort(arr):
new_array = arr
if len(arr) > 2:
half = len(arr)//2
left = arr[:half]
rigth = arr[half:]
left = mergeSort(left)
rigth = mergeSort(rigth)
merged_array = rigth
for number in left:
number_index = 0
for number2 in rigth:
if number < number2:
number_index += 1
merged_array.insert(number_index, number)
return merged_array
elif len(arr) > 1 and arr[0] < arr[1]:
new_array = [arr[1], arr[0]]
return new_array
if __name__ == '__main__':
arr = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
print("Original Array: ")
print(arr)
print("Sorted Array: ")
ordered_arr = mergeSort(arr)
print(ordered_arr)
Aquí mi algoritmo implementado en JavaScript
function mergeSort(arr) {
// Verificar si el arreglo es de longitud 0 o 1, si es así, ya está ordenado
if (arr.length <= 1) {
return arr;
}
// Encontrar el punto medio del arreglo
const mid = Math.floor(arr.length / 2);
// Dividir el arreglo en dos mitades
const leftArr = arr.slice(0, mid);
const rightArr = arr.slice(mid);
// Ordenar recursivamente las dos mitades del arreglo
const sortedLeft = mergeSort(leftArr);
const sortedRight = mergeSort(rightArr);
// Combinar las dos mitades ordenadas en un solo arreglo ordenado
const mergedArr = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < sortedLeft.length && rightIndex < sortedRight.length) {
if (sortedLeft[leftIndex] < sortedRight[rightIndex]) {
mergedArr.push(sortedLeft[leftIndex]);
leftIndex++;
} else {
mergedArr.push(sortedRight[rightIndex]);
rightIndex++;
}
}
// Agregar los elementos restantes del arreglo izquierdo o derecho
return mergedArr.concat(sortedLeft.slice(leftIndex)).concat(sortedRight.slice(rightIndex));
}
// Ejemplo de uso
const arr = [
3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57
];
const sortedArr = mergeSort(arr);
console.table(sortedArr);
Python 3.10.4 (v3.10.4:9d38120e33, Mar 23 2022, 17:29:05) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type “help”, “copyright”, “credits” or “license()” for more information.
a = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
a.sort()
a
[1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10, 12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25, 26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38, 39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45, 47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59, 60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72, 74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86, 86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98, 98, 99, 99, 100]
Lo logre en 0.00016331858932971954 con Python
Mi codigo:
def mergeSort(arr):
if len(arr) < 2:
return arr
half = len(arr) // 2
left = arr[:half]
right = arr[half:]
left = mergeSort(left)
right = mergeSort(right)
return mergue(left, right)
def mergue(left, right):
result = []
while left and right:
if(left[0] < right[0]):
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left)
result.extend(right)
return result
No es la version mas optima pero es la que entendi xp
https://www.youtube.com/watch?v=3_vD60LQ8Ec
# Quick Sort
list = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57
]
def partition(list):
pivot = list[0]
minus = []
mayus = []
for i in range (1, len(list)):
if list[i] < pivot:
minus.append(list[i])
else:
mayus.append(list[i])
return minus, pivot, mayus
def quicksort(list):
if len(list) < 2:
return list
minus, pivot, mayus = partition(list)
#return minus + [pivot] + mayus
return quicksort(minus) + [pivot] + quicksort(mayus)
print(quicksort(list))
MergeSOrt en Javascript 😃
llegar y probar
Si quiere el resultado de menor a mayor se tiene que invertir a < en el If de la funcion merge, el cual se encarga de dividir el array creando e insertando en el array vacío los elementos de < o > de los subarrays que crea tanto el izquierdo domo el derecho.
function merge(left, right) {
let arr = []
while (left.length && right.length) {
/* Elije el más grande entre los elementos más grandes de las submatrices izq y der
Mientras tanto se elimina el elemento elegido del subarray mediante la funcion shift(). EL proceso continua hasta que uno de los subarrays se vacie, empujando los elementos sobrantes en el arreglo principal. */
if (left[0] > right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
//Se concatenan los elementos sobrantes
return [ ...arr, ...left, ...right ]
}
// Esta función se encargara de seguir dividiendo para triunfar. Aquí se identifica el punto medio dividiéndose en submatrices usando la funcion splice().
function mergeSort(array) {
const half = array.length / 2
// Si existiese un numero impar de elementos, el de la izquierda sera menor.Se dividirá hasta que nos queden con matrices de un solo elemento (array.length<2). Finalmente se comienza a combinar los subarrays usando la función merge()
if(array.length < 2){
return array
}
const left = array.splice(0, half)
return merge(mergeSort(left),mergeSort(array))
}
array = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
console.log(mergeSort(array));
#include<stdio.h>
#include<stdlib.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r-l)/ 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int z;
for (z = 0; z < size; z++)
printf("%d “, A[z]);
printf(”\n");
}
int main()
{
int arr[] = {3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,
43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,
25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,
17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,
67,100,24,67,38,57};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Python:
def merge_sort(lista):
if len(lista) > 1:
half = len(lista) // 2
first_half = lista[:half]
second_half = lista[half:]
merge_sort(first_half)
merge_sort(second_half)
n = 0
m = 0
p = 0
while n < len(first_half) and m < len(second_half):
if first_half[n] > second_half[m]:
lista[p] = first_half[n]
n += 1
else:
lista[p] = second_half[m]
m += 1
p += 1
while n < len(first_half):
lista[p] = first_half[n]
n += 1
p += 1
while m < len(second_half):
lista[p] = second_half[m]
m += 1
p += 1
numeros = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31,
33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
print(numeros)
merge_sort(numeros)
print(numeros)
El código en C:
#include <stdio.h>
#include <math.h>
void insertionSort(int arr[], int n){
int i, currentVal, j;
for(i = 0; i < n; i++){
currentVal = arr[i];
j = i - 1;
while (j >= 0 && arr[j] < currentVal){
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = currentVal;
}
}
void printArray(int arr[], int n){
int i;
for (i = 0; i < n; i++)
printf("%d, ", arr[i]);
printf("\n");
}
//Driver program to test insertion sort
int main(){
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23,
78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32,
58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25,
99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54,
6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17,
8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50,
26, 67, 100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
printf("\n");
return 0;
}```
SelectionSort con búsqueda binaria en python
import math
num = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30,
45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80,
44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34,
87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17,
8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100,
24, 67, 38, 57]
def run():
orden = 0
for i in range(1, len(num)):
bajo = 0
alto = orden
c = math.floor((bajo + alto) / 2)
while True:
if num[i] < num[0] or num[i] > num[orden]:
if num[i] < num[0]:
num.insert(0, num[i])
del num[i + 1]
orden += 1
break
if num[i] >= num[c]:
bajo = c
else:
alto = c
c = math.floor((bajo + alto) / 2)
if alto - bajo == 1:
num.insert(alto, num[i])
del num[i + 1]
orden += 1
break
print(num)
if __name__ == '__main__':
run()
Hola a todos, comparto mi código usando heap sort porque en el anterior reto usé quick sort xD.
#include<stdio.h>
#include<stdlib.h>
void swap(int *number1, int *number2)
{
int temp = *number1;
*number1 = *number2;
*number2 = temp;
}
void printSorted(int intArray[], int length)
{
int i;
printf("The sorted array is: \n");
for(i = 0; i < length; i++)
printf("%d\n", intArray[i]);
}
void buildMinHeap(int intArray[], int arraySize)
{
//Look all the nodes with children and heapify to set as first value the lowest
for(int i = arraySize / 2; i > 0; i--)
{
heapify(intArray, arraySize, i);
}
}
void doHeapSort(int intArray[], int arraySize)
{
buildMinHeap(intArray, arraySize);
//Foreach the array since the last node throught the first one
for(int i = arraySize; i > 0; i--)
{
swap(&intArray[0], &intArray[i]);
//Ignore the last node (in theory is sorted)
arraySize--;
heapify(intArray, arraySize, 0);
}
}
void heapify(int intArray[], int arraySize, int actualNode)
{
//Children position of the actual node
int left = 2 * actualNode + 1;
int right = 2 * actualNode + 2;
//Node index with the highest value
int min = 0;
//Has left child and the left child has less value than its parent?
if(left <= arraySize && intArray[left] < intArray[actualNode])
min = left;
else
min = actualNode;
//Has right child and right child has less value than its parent or sibling?
if(right <= arraySize && intArray[right] < intArray[min])
min = right;
//If we hasn't pass through all nodes swap and heapify in the min value index
if(actualNode != min)
{
swap(&intArray[min], &intArray[actualNode]);
heapify(intArray, arraySize, min);
}
}
int main(int argc, char const *argv)
{
int number;
int intArray[300];
int i = 0;
FILE *file = fopen("numbersHeap.txt", "r");
//Read the file line by line and set the numbers into intArray
while(fscanf(file, "%d", &number) == 1)
{
intArray[i] = number;
i++;
}
int arrayLength = sizeof(intArray)/sizeof(intArray[0]);
doHeapSort(intArray, arrayLength);
printSorted(intArray, arrayLength);
fclose(file);
return 0;
}
Reto completado, les comparto cómo se ve en consola:
Así mismo el código usado en C con BubbleSort:
#include <stdio.h>
void swap(int *n1, int *n2)
{
int temp=*n1;
*n1=*n2;
*n2=temp;
}
void bubbleSortDOWN(int entry_Vector[],int n)
{
int i, j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(entry_Vector[j]<entry_Vector[j+1])
{
swap(&entry_Vector[j],&entry_Vector[j+1]);
}
}
}
}
void printArray(int entry_Vector[], int n)
{
int i;
for(i=0;i<n-1;i++)
{
printf("%i ,", entry_Vector[i]);
}
printf("\nEnd of the Bubble Sort\n");
}
int main(int argc, char const *argv[])
{
int entry_Vector[]={3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30,
45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80,
44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34,
87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17,
8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100,
24, 67, 38, 57};
int n=sizeof(entry_Vector)/sizeof(entry_Vector[0]);
bubbleSortDOWN(entry_Vector,n);
printArray(entry_Vector,n+1);
printf("\n");
return 0;
}
con merge sort en c#
using System;
using System.Collections;
namespace Merge_Sort
{
class Program
{
static void Main(string[] args)
{
int[] arreglo = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,
57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82,52, 44, 72, 87, 34, 87, 65, 30,
54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67,
100, 24, 67, 38, 57,};
arreglo = mergeSort(arreglo);
foreach(var i in arreglo)
{
Console.WriteLine(i);
}
}
static int[] mergeSort(int[] arreglo)
{
if (arreglo.Length == 1)
{
return arreglo;
}
int m = arreglo.Length / 2;
int[] arreglo1 = new int[m];
int[] arreglo2 = new int[(arreglo.Length-(m))];
for(int i=0; i < arreglo1.Length; i++)
{
arreglo1[i] = arreglo[i];
}
for (int i = 0; i < arreglo2.Length; i++)
{
arreglo2[i] = arreglo[m+i];
}
int[] arregloFinal = merge(mergeSort(arreglo1),mergeSort(arreglo2));
return arregloFinal;
}
static int[] merge(int[] arreglo1,int [] arreglo2)
{
int posicionArray1 = 0;
int posicionArray2 = 0;
int posicionArray = 0;
int[] arreglo = new int[(arreglo1.Length + arreglo2.Length)];
while (posicionArray1<arreglo1.Length && posicionArray2<arreglo2.Length)
{
if (arreglo1[posicionArray1] > arreglo2[posicionArray2])
{
arreglo[posicionArray]=arreglo1[posicionArray1];
posicionArray1++;
posicionArray++;
}
else if(arreglo1[posicionArray1] < arreglo2[posicionArray2])
{
arreglo[posicionArray] = arreglo2[posicionArray2];
posicionArray2++;
posicionArray++;
}
else
{
arreglo[posicionArray]=arreglo1[posicionArray1];
posicionArray1++;
posicionArray++;
arreglo[posicionArray]=arreglo2[posicionArray2];
posicionArray2++;
posicionArray++;
}
}
if (posicionArray1 < arreglo1.Length)
{
while(posicionArray1 < arreglo1.Length)
{
arreglo[posicionArray]=arreglo1[posicionArray1];
posicionArray1++;
posicionArray++;
}
}
if (posicionArray2 < arreglo2.Length)
{
while (posicionArray2 < arreglo2.Length)
{
arreglo[posicionArray]=arreglo2[posicionArray2];
posicionArray2++;
posicionArray++;
}
}
return arreglo;
}
}
}
merge sort en python
array = [ 3, 94, 86, 82, 90, ... ]
def merge(array1, array2):
merged_array = []
i1 = 0
i2 = 0
while i1 < len(array1) and i2 < len(array2):
if array1[i1] < array2[i2]:
merged_array.append(array1[i1])
if i1 == len(array1) - 1:
for x2 in array2[i2:]:
merged_array.append(x2)
return merged_array
i1 += 1
else:
merged_array.append(array2[i2])
if i2 == len(array2) - 1:
for x1 in array1[i1:]:
merged_array.append(x1)
return merged_array
i2 += 1
def merge_sort(array):
if len(array) == 1:
return array
else:
m = int(len(array) / 2)
array1 = array[:m]
array2 = array[m:]
sorted_array1 = merge_sort(array1)
sorted_array2 = merge_sort(array2)
return merge(sorted_array1, sorted_array2)
print(array)
sorted_array = merge_sort(array)
print(sorted_array)
Merge sort Lenguaje C, con pocos cambios
#include <stdio.h>
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8,
17, 15, 22, 10, 23, 78, 25, 2, 30, 45,
98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25,
68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30,
54, 6, 31, 33, 44, 44, 42, 82, 90, 17,
9, 98, 28, 86, 69, 3, 17, 8, 45, 98,
12, 47, 95, 43, 72, 39, 41, 82, 74, 56,
65, 79, 50, 26, 67, 100, 24, 67, 38, 57, -1}; // array to be sorted
int n = sizeof(arr) / sizeof(arr[0]); //number of item of the array
int main()
{
int i;
merge_sort(arr, 0, n - 1); // sort the array merge_sort
printf("Sorted array:"); // print sorted array
for (i = 0; i < n; i++)
printf("%d, ", arr[i]);
return 0;
}
int merge_sort(int arr[], int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2; // Divide and Conquer
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high); // Combine
merge(arr, low, mid, high);
}
return 0;
}
int merge(int arr[], int l, int m, int h)
{
int arr1[n / 2], arr2[n / 2]; // Two temporary arrays to hold the two arrays to be merged
int n1, n2, i, j, k;
n1 = m - l + 1;
n2 = h - m;
for (i = 0; i < n1; i++)
{
arr1[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
arr2[j] = arr[m + j + 1];
}
arr1[i] = 9999; // To mark the end of each temporary array
arr2[j] = 9999;
i = 0;
j = 0;
for (k = l; k <= h; k++) //process of combining two sorted arrays
{
if (arr1[i] <= arr2[j])
arr[k] = arr1[i++];
else
arr[k] = arr2[j++];
}
return 0;
}```
#include<stdio.h>
#include<stdlib.h>
int arr[]={3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,
57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
void merge_sort(int[], int, int);
void merge(int[], int, int, int);
int main()
{
int i;
printf(“Original array: {”); // print sorted array
for(i=0;i<n;i++)
printf("%d, “,arr[i]);
printf(”}\n");
merge_sort(arr,0,n-1); // sort the array
printf(“Sorted array: {”); // print sorted array
for(i=0;i<n;i++)
printf("%d, “,arr[i]);
printf(”}\n");
return 0;
}
void merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
}
void merge(int arr[],int l,int m,int h)
{
int arr1[n/2],arr2[n/2]; // Two temporary arrays to hold the two arrays to be merged
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0;i<n1;i++)
arr1[i]=arr[l+i];
for(j=0;j<n2;j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;j=0;
for(k=l;k<=h;k++) //process of combining two sorted arrays
{
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
}
Quick Sort 😄
#include <stdio.h>
#define SIZE 100
void qs(int lista[],int limite_izq,int limite_der)
{
int izq,der,temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = lista[(izq+der)/2];
do{
while(lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= lista[izq];
lista[izq]=lista[der];
lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der){qs(lista,limite_izq,der);}
if(limite_der>izq){qs(lista,izq,limite_der);}
}
void quicksort(int lista[],int n)
{
qs(lista,0,n-1);
}
int main(int argc, const char * argv[])
{
int lista[SIZE];
FILE *myFile;
myFile = fopen("numbers.dat", "rb");
int size = sizeof(lista)/sizeof(lista[0]);
for(int i = 0; i < size; i++)
fscanf(myFile, "%d", &lista[i]);
printf("Lista Desordenada \n");
for (int i=0; i<size; i++) {
printf("%d",lista[i]);
if(i<size-1)
printf(",");
}
printf("\n");
quicksort(lista,size);
printf("Lista Ordenada \n");
for (int i=0; i<size; i++) {
printf("%d",lista[i]);
if(i<size-1)
printf(",");
}
return 0;
}
Implementacion de MergeSort en Elixir
- Toma los datos de un archivo
elements.dat - Los pone en un arreglo con los datos ya convertidos
- Envia cada una de las lineas y las ordena de Mayor a Menor
- Uso de recursividad
- Cambios minimos para que se ordene de Menor a Mayor
defmodule FileManager do
def read_file(file) do
if File.exists?(file) do
File.read!(file)
end
end
def list_line(file) do
list = convert_number_line(String.split(read_file(file), "\n"))
# DIvido el string en partes pequeñas hasta \n
end
def convert_number_line([]), do: []
def convert_number_line(list) do
[ head | tail] = list
# Convierto a numeros cada uno de los elementos
[ convert_elems_to_number(String.split(head, " ")) | convert_number_line(tail) ]
end
def convert_elems_to_number([]), do: []
def convert_elems_to_number(elems) do
[ head | tail ] = elems
{ val , _ } = Integer.parse(head)
[ val | convert_elems_to_number(tail) ]
end
end
defmodule Lista do
def ordenarMerge([]), do: []
# En Caso que este Vacio
def ordenarMerge([x]), do: [x]
# En Caso de Encontrar solo 1 elemento
def ordenarMerge(lista) do
lista1 = Enum.take_every(lista, 2)
lista2 = Enum.drop_every(lista, 2)
# Toma la mitad
merge(ordenarMerge(lista1), ordenarMerge(lista2), [])
end
def merge(lista1, [], []), do: lista1 # Guarda cuando r este vacio
def merge([], lista2, []), do: lista2
def merge(lista1, [], r), do: r ++ lista1 # Cuando se quieran unir
def merge([], lista2, r), do: r ++ lista2
def merge([ l1h | l1t ] = lista1, [ l2h | l2t ] = lista2, r) do
# Tomo Cabeza y cola de cada una de las listas
cond do
l1h > l2h -> merge(l1t, lista2, r ++ [l1h]) # En caso que sea mayor
# Cambio minimo para organizar de menor a mayor
true -> merge(lista1, l2t, r ++ [l2h]) # En cualquier otro caso
end
end
end
defmodule Ejecucion do
def main do
IEx.configure(inspect: [charlists: :as_lists])
file = "elements.dat"
lista_elementos = FileManager.list_line(file)
IO.puts("---- Elementos No Ordenados ----")
IO.inspect(lista_elementos, charlists: :as_lists)
lista_elementos = Enum.map(lista_elementos, fn(x) -> Lista.ordenarMerge(x) end)
IO.puts("\n---- Elementos Debidamente Organizados ----")
IO.inspect(lista_elementos, charlists: :as_lists)
:ok
end
end
Ejecucion
InsertionSort:
#include <stdio.h>
#include <math.h>
#define SIZE 100
/* Función de insertion Sort*/
void insertionSort(int arr[], int n)
{
int i, currentVal, j;
for (i = 1; i < n; i++)
{
currentVal= arr[i];
j = i-1;
while (j >= 0 && arr[j] < currentVal)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = currentVal;
}
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
main(int argc, char const *argv[])
{
FILE *array;
int arr[SIZE];
array = fopen("array2.txt", "r");
if(array != NULL)
{
int i;
for(i = 0; i < SIZE; i++)
fscanf(array, "%d", &arr[i]);
fclose(array);
insertionSort(arr,SIZE);
printArray(arr,SIZE);
printf("\n");
}
else
printf("No se leyó el array de datos");
return 0;
} ```
ShakerSort:
//Desafio 2
//ShakerSort
#include <stdio.h>
void burbuja(int* num1, int* num2){
int aux = *num1;
*num1 = *num2;
*num2 = aux;
}
void printArray(int v[], int n){
int i = 0;
for(i = 0; i < n; i++){
printf("%i ",v[i]);
}
}
int main(int argc, char const *argv[]){
int v[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int tam = sizeof(v)/sizeof(int);
int i,j,k, change = 1;
for(i = 0; i < tam/2 && change == 1; i++){
change = 0;
for(j = i; j < tam - i - 1;j++){
if(v[j]>v[j+1]){
burbuja(&v[j], &v[j+1]);
change = 1;
}
}
for(j = tam - 2 - i;j > i;j--){
if(v[j]<v[j-1]){
burbuja(&v[j], &v[j-1]);
change = 1;
}
}
}
printArray(v, tam);
return 0;
}
Use
->Bubble Sort que me dio un tiempo de ejecucion real de 0m0.003s y
->Insertion Sort con uun tiempo de ejecucion real de 0m0.002s
#include <iostream>
using namespace std;
void printArr(int data[], int size)
{
for (int i = 0; i < size; i++)
{
std::cout << data[i] << ", ";
}
std::cout << "\n";
}
void bubbleSort(int data[], int size)
{
for (int i = 0; i <= size; i++)
{
for (int j = 0; j <= size; j++)
{
if (data[j] > data[j + 1])
{
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
void insertionSort(int data[], int size)
{
for (int i = 0; i <= size - 1; i++)
{
int current = i;
for (int j = i; j >= 0; j--)
{
if (data[current] < data[j])
{
int temp = data[current];
data[current] = data[j];
data[j] = temp;
current = j;
}
}
}
}
int main(int argc, char const *argv[])
{
// int data[] = {-796, 3229, -5164, -362, 4408, 8965, -6068, 9329, -3034, -443, -6693, 9497, 2615, -5966, -9065, -1160, 6148, 5517, 1123, -8887, 5649, 3302, -1176, -8542, -9166, 8, -2906, 8987, -2414, -7984, 4410, 8872, 5241, -4556, 59, -5562, -3877, 7452, -4467, 2076, 4076, 4297, -3847, -2055, 4483, -1484, -2371, 6199, -7261, -7032, 6010, 2325, -6625, -2601, 3870, 1822, -5665, 9622, 9883, -5794, -5218, 2926, 8599, -3099, 6399, -2570, 3943, -2409, 5114, 9791, -4420, 1065, 3077, -1062, -8004, 4397, 1635, 8578, -9226, 9222, -1793, -2691, -5060, -4727, -4098, 946, -6558, -4111, 4575, -2685, -4729, -5277, 1936, 5106, -2089, 824, 9421, -1683, -2083, 7891, -2099, 1305, -9076, -3535, 2565, -2871, 9448, 7177, -8614, -9954, -362, 1455, -8834, -9846, -8412, 1175, -1981, -5991, 7201, -1997, -5156, -1634, -9803, 1032, 9551, -6153, 8502, 3536, -2980, 8681, -9210, 4408, 8780, -916, -369, -8651, 1246, -702, -5555, 23, 8208, 2037, 6941, 9545, -5147, 5063, -8358, 2772, 8553, 9885, 4624, -3576, 9131, 1229, -429, -479, -673, -7060, -4031, 5650, 6679, 6796, 5622, -6256, -238, -6096, 3096, -1610, -2948, 6291, -1666, 5219, 5850, 7387, -3260, 3672, -1766, -9941, 8252, 2649, 7079, -8026, 6356, 676, -5065, -6338, 3287, 680, -3269, 2770, 6637, -8744, 9162, -2204, -3066, -7228, 8762, 1505, 4957, 766, -9136, 4632, -5022, -9999, 5361, 2732, 7831, -501, -4650, 7236, 3682, -2438, 5574, -8230, -9669, -7442, 7966, -2905, 7629, 7137, 200, -8670, -749, 2228, 458, 7889, -3668, -5350, -3261, 6741, -6953, 4800, 3372, 6662, -1018, 8523, 3164, 3577, 9720, -6826, -1574, -7875, -2796, -1078, -4755, 4926, 3368, 4302, 9254, 6410, -4689, 7878, 2461, 8233, -6688, 5904, 4735, -2940, 8830, 9976, -3674, 4222, -1446, 6187, -3181, -8882, 5487, -6939, -7885, 3786, -6234, -1062, -4553, -5709, 8459, 5008, 3352, 6586, 537, -7610, 3261, 8246, -2105, 5107, 7957, -7886, -2925, -2541, -7449, 9521, 5073, -239, -8054, -4379, -8323, -6485, -4828, -5294, -2720, 595};
int data[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int size = *(&data + 1) - data;
bubbleSort(data, size);
// insertionSort(data, size);
printArr(data, size);
return 0;
}
Saludos y buen codeo a todos.
Usé Insertion Sort:
#include <stdio.h>
void insertionSort(int formacion[], int tam)
{
int i, j, current;
for(i=1; i<tam; i++)
{
current = formacion[i];
j = i;
while(j > 0 && formacion[j-1] < current)
{
formacion[j] = formacion[j - 1];
j--;
}
formacion[j] = current;
}
}
int main()
{
int original[]={3,94,86,82,90,10,87,36,61,8,17,15,22,
10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,
44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,
33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,
74,56,65,79,50,26,67,100,24,67,38,57};
int e = sizeof(original)/sizeof(original[0]);
printf("\nArreglo desordenado: \n");
for(int i=0; i<e; i++)
printf("%d ", original[i]);
insertionSort(original, e);
printf("\n\nArreglo ordenado (descendente): \n");
for(int i=0; i<e; i++)
printf("%d ", original[i]);
printf("\n\nFin.");
return 0;
}
Aquí pueden verlo funcionando.
Yo usé BubbleSort y array ordenado queda así:
array = [1, 1, 2, 2, 3, 3, 6, 8, 8, 9, 10, 10, 12, 15, 17, 17, 17, 19, 22, 23, 24, 25, 25, 25, 26, 28, 30, 30, 30, 31, 32, 32, 33, 34, 36, 38, 39, 41, 41, 42, 43, 43, 44, 44, 44, 44, 45, 45, 47, 48, 50, 52, 53, 54, 56, 57, 57, 57, 58, 59, 60, 60, 61, 64, 65, 65, 67, 67, 68, 69, 72, 72, 74, 74, 76, 77, 78, 79, 80, 82, 82, 82, 82, 86, 86, 87, 87, 87, 89, 90, 90, 94, 95, 98, 98, 98, 98, 99, 99, 100]
Intente con este. Y desde una perspectiva me parece que esta bien escrito, pero deja de correr a la mitad.
#include <stdio.h>
int main(){
int w=0,i,k,tem;
int N[]={3, 94, 86, 82, 90, 10, 87, 36, 61, 8,
17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43,
98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99,
60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60};
printf("SERIE EN DESORDEN \n");
for(i=0;i<45;i++)
{
printf("%d ",N[i]);
}
while(w!=45){
w=0;
for (k=0;k<=45;k++)
{
if(N[k]<=N[k+1])
{
w=w+1;
}
else
{
tem=N[k];
N[k]=N[k+1];
N[k+1]=tem;
}
}
}
printf("LOS NUMEROS ORDENADOS SON: \n");
for(i=0;i<45;i++){
printf("%d ",N[i]);
}
return 0;
Utilizando JAVA con Merge Sort en NetBeans
public class MergeSortDesafioPlatzi {
public static void main(String[] args) {
int array[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78,
25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60,
74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52,
44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9,
98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74,
56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
System.out.println("ARREGLO SIN ORDENAR");
for (int i = 0; i < array.length; i++) {
System.out.printf("%d ", array[i]);
}
System.out.printf("\n");
System.out.println("ARREGLO ORDENADO DE MAYOR A MENOR");
sort(array,0,99);
print(array);
}
static void sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void merge(int arr[], int left, int mid, int right) {
//Encuentra el tamaño de los sub-arrays para unirlos.
int sizeA1 = mid - left + 1;
int sizeA2 = right - mid;
//arrays temporales.
int leftArray[] = new int[sizeA1];
int rightArray[] = new int[sizeA2];
//Copia los datos a los arrays temporales.
for (int i = 0; i < sizeA1; i++) {
leftArray[i] = arr[left + i];
}
for (int j = 0; j < sizeA2; j++) {
rightArray[j] = arr[mid + j + 1];
}
/* Une los arreglostemporales. */
//Índices inicial del primer y segundo sub-arreglo.
int indiceA1 = 0, indiceA2 = 0;
//Índice inicial del sub-arreglo arr[].
int indiceArr = left;
//Ordenamiento.
while (indiceA1 < sizeA1 && indiceA2 < sizeA2) {
if (leftArray[indiceA1] >= rightArray[indiceA2]) {
arr[indiceArr] = leftArray[indiceA1];
indiceA1++;
} else {
arr[indiceArr] = rightArray[indiceA2];
indiceA2++;
}
indiceArr++;
}//Fin del while.
/* Si quedan elementos por ordenar */
//Copiar los elementos restantes de leftArray[].
while (indiceA1 < sizeA1) {
arr[indiceArr] = leftArray[indiceA1];
indiceA1++;
indiceArr++;
}
//Copiar los elementos restantes de rightArray[].
while (indiceA2 < sizeA2) {
arr[indiceArr] = rightArray[indiceA2];
indiceA2++;
indiceArr++;
}
}
static void print(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.printf(arr[i] + " ");
}
System.out.println();
}
}
Implemente un Quick sort que use en un anterior reto.
const unsortedArray = [3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
/* A function to do the Quicksort, I'm going to use the pivot function to get the first sorted item from the array */
function quickSort(arr){
if (arr.length <= 1) {
return arr;
}else{
var left = [];
var right = [];
var sortedArr = [];
//array.pop() remove the last item of an array
var pivot = arr.pop();
var n = arr.length;
/* This FOR is for the whole cycle */
for (let i = 0; i < n; i++) {
if ( arr[i] <= pivot) {
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
//array.concat() is used to join two or more arrays
return sortedArr.concat(quickSort(left), pivot, quickSort(right));
}
}
//This main() function just run the functions
function main(){
console.table(quickSort(unsortedArray));
console.log("The Sorting has ended.");
}
main();
Resultado:
Quicksort con python con una función para crear 100 números aleatorios del 0 al 100:
from random import randint
''' Con esta funcion podemos crear arrays
con un numero aletorio de datos'''
def create_array(size=10, max =50):
return [randint(0, max) for i in range(size)]
def quicksort(data):
#presuponemos que si el data set es menor o igual a uno esta ordenado por definicion
if len(data) <= 1: return data
smaller, equal, larger = [], [], []
#selecionamos nuestro valor pivote de forma aleatoria desde nuestro data set
pivot = data[randint(0, len(data) -1)]
for value in data:
# si el valor es menor que nuestro numero pivote lo colocamos en smaller
if value < pivot:
smaller.append(value)
# si el valor es igual que nuestro numero pivote lo colocamos en equal
elif value == pivot:
equal.append(value)
# si no cumple ninguna de esta condiciones significa que es mayor, por lo que colocamos el valor el larger
else:
larger.append(value)
#ordenamos de forma recursiva, concatenando los resultados.
return quicksort(smaller) + equal + quicksort(larger)
dataset = create_array(100,100)
print(quicksort(dataset))
yo utilice este fue el que mejor entendi:
function quickSort(array) {
if (array.length < 1) {
return [];
}
var left=[];
var right=[];
var pivot=array[0];
for (var i = 1; i < array.length; i++) {
if (array[i]< pivot){
left.push(array[i]);
}
else {
right.push(array[i]);
}
}
return[].concat(quickSort(left),pivot,quickSort(right));
}
console.log(quickSort([3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57]));
Pregunta
¿Hay alguna página dónde uno mida cuánto se demora el código en ejecutar todas las tareas…precisamente para medir (por ahora con pequeñas cantidades de datos) cuál algoritmo se demora menos?
Utilice merge sort en python, es muy util usarlo ❤️
DATA = [
3, 94, 86, 82, 90,
10,87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57
]
print("TU LISTA ORIGINAL".center(50,"="))
print("")
print(DATA)
def merge_sort(not_ordered_list):
amount_data = len(not_ordered_list)
ordered_list = []
while len(ordered_list) != amount_data:
ordered_list += [max(not_ordered_list)]
not_ordered_list.remove(max(not_ordered_list))
return ordered_list
if __name__ == "__main__":
ordered_data = merge_sort(DATA)
print("")
print("TU LISTA ORDENADA".center(50,"="))
print("")
print(ordered_data)
No lo pude hacer con Merge Sort asi que lo hice así:
#include <stdio.h>
#include <math.h>
void Sort(int arr[], int n)
{
int i;
int j;
int valor;
for(i=0;i<n;i++)
{
valor = arr[i];
j = i - 1;
while(j>=0 && arr[j] < valor)
{
arr[j+1] = arr[j];
j = j-1;
int k = j;
}
arr[j+1] = valor;
}
}
void printArray(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d \n", arr[i]);
}
}
int main()
{
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60};
int n = sizeof(arr)/sizeof(arr[0]);
Sort(arr, n);
printArray(arr, n);
return 0;
}
Lo hice con QuickSort en C. 😄
/* #necesitamos dividir nuestro dataset
#necesitamos un punto pivotal
#recursivamente ordenar cada mitad de mi arreglo */
#include<stdio.h>
#include<time.h>
#include<unistd.h>
/* def particion(arr, low, high):
i=(low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j]<=pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return(i+1) */
int particion(int arr[], int low, int high)
{
int i = (low-1);
int pivot = arr[high];
int tempA, tempB;
for(int j = low; j<= high - 1; j++)
{
if(arr[j] <= pivot)
{
i++;
tempA = arr[i];
arr[i] = arr[j];
arr[j] = tempA;
}
}
tempB = arr[i+1];
arr[i+1] = arr[high];
arr[high] = tempB;
return(i+1);
}
/* def quickSort(arr, low, high):
if low < high:
pi = particion(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high) */
int quickSort(int arr[], int low, int high)
{
if(low < high)
{
int pi = particion(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
/* arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10]
n = len(arr)
quickSort(arr, 0, n-1)
print("Array ordenado: ")
for i in range(n):
print("%d" %arr[i]), */
int main()
{
double time_spent;
clock_t begin, end;
begin = clock();
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23,
78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60,
25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30,
54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56,
65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Array Ordenado:");
for(int i = 0; i < n; i++)
{
printf("%d, ", arr[i]);
}
end = clock();
time_spent = ((double)(end - begin)) / CLOCKS_PER_SEC;
printf("\nTime spent: %f\n", time_spent);
return 0;
}```
Deja desafio hecho en python, donde se puede medir el tiempo de ejecucion, espero que les sirva!
import time
def ordenar(not_ordened_list):
if len(not_ordened_list) == 0:
return []
elif len(not_ordened_list) ==1:
return not_ordened_list
left = []
right = []
equals = []
pivote = not_ordened_list[0]
for n in not_ordened_list[1:]:
if pivote > n:
left.append(n)
elif pivote < n:
right.append(n)
elif pivote == n:
equals.append(n)
return ordenar(left) + [pivote] + equals + ordenar(right)
if __name__ == '__main__':
desafio_list = [
3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23,
78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60,
25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30,
54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56,
65, 79, 50, 26, 67, 100, 24, 67, 38, 57]
print("Desafio sort de Platzi")
print('Lista desordenada:')
print(desafio_list)
print("contando tiempo y ordenando...")
start_time = time.time()
listaOrdenada = ordenar(desafio_list)
elapsed_time = time.time() - start_time
print("Lista ordenada en: ",elapsed_time,"s")
print("Lista resultante:")
print(listaOrdenada)
Happy Coding
#include <stdio.h>
void quickSort(int vectorEntrada[], int primerValor, int ultimoValor) {
int i, j, pivote, temp;
if (primerValor < ultimoValor)
{
pivote = primerValor;
i = primerValor;
j = ultimoValor;
while (i < j)
{
while (vectorEntrada[i] <= vectorEntrada[pivote] && i < ultimoValor)
i++;
while (vectorEntrada[j] > vectorEntrada[pivote])
j--;
if (i < j)
{
temp = vectorEntrada[i];
vectorEntrada[i] = vectorEntrada[j];
vectorEntrada[j] = temp;
}
}
temp = vectorEntrada[pivote];
vectorEntrada[pivote] = vectorEntrada[j];
vectorEntrada[j] = temp;
quickSort(vectorEntrada, primerValor, j - 1);
quickSort(vectorEntrada, j + 1, ultimoValor);
}
}
void printArray(int vectorEntrada[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d ,", vectorEntrada[i]);
}
printf("\n Fin del ordenamiento");
}
int main(int argc, char const *argv[])
{
int size = 101;
int vectorEntrada[] = {3,94,86,82,90, 10,87,36,61,8, 17,15,22,10,23, 78,25,2,30,45, 98,43,98,59,53, 57,2,64,1,41,
32,58,19,99,60, 74,48,80,44,25, 68,1,89,77,60, 25,99,30,76,32, 57,82,52,44,72, 87,34,87,65,30,
54,6,31,33,44, 44,42,82,90,17, 9,98,28,86,69, 3,17,8,45,98, 12,47,95,43,72, 39,41,82,74,56,
65,79,50,26,67, 100,24,67,38,57};
quickSort(vectorEntrada, 0, size);
printArray(vectorEntrada, size) ;
return 0;
}
Solución Python en base al código de nuestro compañero Juan Manuel @juanotero
def arrayMerge(arrayA, arrayB):
result = []
indexA, indexB = 0, 0
while indexA < len(arrayA) and indexB < len(arrayB):
if(arrayA[indexA] < arrayB[indexB]):
result.append(arrayA[indexA])
indexA+=1
else:
result.append(arrayB[indexB])
indexB+=1
if(indexA == len(arrayA)):
result.extend(arrayB[indexB:])
else:
result.extend(arrayA[indexA:])
return result
def mergeSort(array):
if len(array) <= 1:
return array
arrayLeft = mergeSort(array[:len(array)//2])
arrayRigth = mergeSort(array[len(array)//2:])
return arrayMerge(arrayLeft, arrayRigth)
if __name__ == "__main__":
array = [3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57
]
print(mergeSort(array))```
me esta generando un error alguno sabe porque que me ayude
Esta es mi solución en python3, usé una parte del set de datos para realizar la prueba, no lo usé completo.
def quick_sort(lista):
""" Ordena la lista de forma recursiva.
Pre: los elementos de la lista deben ser comparables.
Devuelve: una nueva lista con los elementos ordenados. """
# Caso base
if len(lista) < 2:
return lista
# Caso recursivo
menores, medio, mayores = _partition(lista)
return quick_sort(menores) + medio + quick_sort(mayores)
def _partition(lista):
""" Pre: lista no vacía.
Devuelve: tres listas: menores, medio y mayores. """
pivote = lista[0]
menores = []
mayores = []
for x in range(1, len(lista)):
if lista[x] < pivote:
menores.append(lista[x])
else:
mayores.append(lista[x])
return menores, [pivote], mayores
if __name__ == "__main__":
lista_desordenada = [3 ,94 ,86 ,82 ,90,10 ,87 ,36 ,61 ,8,17 ,15 ,22 ,10,23]
lista_ordenada = []
for i in quick_sort(lista_desordenada):
lista_ordenada.append(i)
print(f'La lista inicial es: \n {lista_desordenada}')
print(f'La lista ordenada es: \n {lista_ordenada}')
Este es mi codigo, utilize el insertion sort, a mi parecer es el algoritmo mas completo para tanto sets de datos pequeños como set de datos grandes.
#include <stdio.h>
#include <math.h>
void insertion(int arr[], int n){
for (int i=1;i<n;i++){
int currValue=arr[i];
int j=i-1;
while(j>=0 && arr[j]<currValue){
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=currValue;
}
}
int main()
{
for (int i=0;i<20;i++){
int arr[5];
for (int j=0;j<5;j++) {
scanf("%d",&arr[j]);
}
insertion(arr,5);
printArray(arr,5);
}
return 0;
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
Reto realizado en C de Quicksort
#include <stdio.h>
//{1992, 4654, 564, 7465, 23, 97, -98, -45};
//{3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,67,100,24,67,38,57};
int ordena(int vector_ini[], int prim, int ult)
{
int ind = prim;
int pivot = vector_ini[ind], temp;
for(int j = prim + 1; j <= ult; j++)
{
if(vector_ini[j] < pivot)
{
ind = ind + 1;
temp = vector_ini[ind];
vector_ini[ind] = vector_ini[j];
vector_ini[j] = temp;
}
}
temp = vector_ini[prim];
vector_ini[prim] = vector_ini[ind];
vector_ini[ind] = temp;
return ind;
}
void divide(int vector_ini[], int izq, int der)
{
int partind;
if (izq < der)
{
partind = ordena(vector_ini, izq, der);
divide(vector_ini, izq, partind-1);
divide(vector_ini, partind+1, der);
}
}
void imprimir(int vector_ini[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d, ", vector_ini[i]);
}
printf("\n");
}
int main()
{
int vector_ini[] = {3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,67,100,24,67,38,57};
int n = sizeof(vector_ini) / sizeof(vector_ini[0]), i;
printf("El valor de n %d \n", n);
printf("Antes de ordenar: \n");
imprimir(vector_ini, n);
divide(vector_ini, 0, n-1);
printf("Despues de ordenar: \n");
imprimir(vector_ini, n);
return 0;
}
Con JS sin fuciones adicionales.
let datos = [
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9 ,98, 28, 86, 69,
3 ,17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57,
];
function init() {
console.time('BubleSort')
for (let j = 0; j < datos.length; j++) {
for (let i = 0; i < datos.length; i++) {
if (datos[i + 1] != undefined && datos[i] > datos[i + 1]) {
temp = datos[i + 1];
datos[i + 1] = datos[i];
datos[i] = temp;
}
}
}
console.timeEnd('BubleSort');
console.log(datos);
}
//REGEX data set [\s] and replace , --->[n] and replace , //
const numberOrder =[3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,67,100,24,67,38,57,93];
console.log('[Soy el array desordenado...] \n ' +numberOrder);
const n = numberOrder.length-1;
console.log(`Este array está compuesto por ${n} elementos\n`);
function sort_numberOrder(){
let ordenados = numberOrder.sort(function(a,b){return a-b});
console.log('[Soy el array ordenado...] \n ' + ordenados)
}
console.time(sort_numberOrder)
sort_numberOrder();
console.timeEnd(sort_numberOrder) //<---- The function spend time
Aunque vi un video en donde explicaban como funcionaba el quick sort, se puede decir que lo logre implementar solo.
def open_document(doc_name):
num_list = []
with open(doc_name, 'r', encoding='utf8') as f:
numbers = f.readlines()
for number in numbers:
num_list.append(int(number))
return num_list
def quickSort(list_to_order, start, end):
move_start = start
move_end = end
pivot = list_to_order[start]
while(move_start <= move_end):
while (list_to_order[move_start] < pivot):
move_start += 1
while (list_to_order[move_end] > pivot):
move_end -= 1
if move_start <= move_end:
aux = list_to_order[move_start]
list_to_order[move_start] = list_to_order[move_end]
list_to_order[move_end] = aux
move_start += 1
move_end -= 1
if start < move_end :
quickSort(list_to_order, start, move_end)
if move_start < end :
quickSort(list_to_order, move_start, end)
return list_to_order
def run():
new_list = open_document('valores.txt')
start = 0
end = (len(new_list)-1)
new_list=quickSort(new_list, start, end)
for element in new_list :
print(element)
if __name__ == '__main__':
run()
Aún me hace falta profundizar más en el lenguaje, por lo que algunas operaciones las hice manual, pero volveré a repasar a fondo algoritmos y estructuras de datos con ya maneje un lenguaje, quiero avanzar más con C o especializarme en JavaScript ❤️
En C
#include<stdio.h>
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high)
{
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
if (array[j] < pivot)
{
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high)
{
if (low < high)
{
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Reto resuelto en Java:
import java.util.*;
public class MergeSort {
public static void main(String args[]) {
Integer[] array = {3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57};
System.out.println("Longitud: "+array.length);
array = margeSort(array);
List arr = Arrays.asList(array);
System.out.println("Longitud: "+array.length);
System.out.println("Arreglo ordenado: "+arr);
}
private static Integer[] margeSort(Integer [] array) {
int length = array.length;
if(length > 1) {
int middle = length / 2;
Integer[] arrayLeft = new Integer[middle];
Integer[] arrayRight = new Integer[length - middle];
arrayLeft = Arrays.copyOfRange(array, 0, middle);
arrayRight = Arrays.copyOfRange(array, middle, length);
arrayLeft = margeSort(arrayLeft);
arrayRight = margeSort(arrayRight);
return merge(arrayLeft, arrayRight);
}
return array;
}
private static Integer[] merge(Integer[] arrayLeft, Integer[] arrayRight) {
int length = arrayLeft.length + arrayRight.length;
int middle = arrayLeft.length;
int index = 0;
int less = 0;
Integer[] arrayResult = new Integer[length];
if(arrayLeft[arrayLeft.length-1] > arrayRight[0]) {
System.arraycopy(arrayLeft, 0, arrayResult, 0, middle);
System.arraycopy(arrayRight, 0, arrayResult, middle, arrayRight.length);
return arrayResult;
}
while(arrayLeft.length > 0 && arrayRight.length > 0) {
if(arrayLeft[0] >= arrayRight[0]) {
less = arrayLeft[0];
arrayLeft = Arrays.copyOfRange(arrayLeft, 1, arrayLeft.length);
}else {
less = arrayRight[0];
arrayRight = Arrays.copyOfRange(arrayRight, 1, arrayRight.length);
}
arrayResult[index] = less;
index++;
}
if(arrayLeft.length > 0) {
System.arraycopy(arrayLeft, 0, arrayResult, index, arrayLeft.length);
}else if(arrayRight.length > 0) {
System.arraycopy(arrayRight, 0, arrayResult, index, arrayRight.length);
}
return arrayResult;
}
}
mergeSort
#include<stdio.h>
void cambio(int *n1, int *n2){
int aux = *n1;
*n1 = *n2;
*n2 = aux;
}
int divide(int array[],int low, int high){
int pivote = array[high];
int i = (low -1);
for (int j=low;j<high;j++){
if(array[j]<pivote){
i++;
cambio(&array[i], &array[j]);
}
}
cambio(&array[i+1],&array[high]);
return (i+1);
}
void quickSort(int array[],int low,int high){
if(low<high){
int pi = divide(array,low,high);
quickSort(array,low,pi-1);
quickSort(array,pi+1,high);
}
}
void printArr(int arr[],int size){ //Imprimir el arreglo
int i;
for (i=0;i<size;i++)
printf("[%d]", arr[i]);
printf("\n");
}
int main(){ //Pruebas
int arr[] = {3, 94, 86, 82, 9010, 87, 36, 61, 817, 15, 22, 10, 2378, 25, 2, 30, 4598, 43, 98, 59, 5357, 2, 64, 1, 4132, 58, 19, 99, 6074, 48, 80, 44, 2568, 1, 89, 77, 6025, 99, 30, 76, 3257, 82, 52, 44, 7287, 34, 87, 65, 3054, 6, 31, 33, 4444, 42, 82, 90, 179, 98, 28, 86, 693, 17, 8, 45, 9812, 47, 95, 43, 7239, 41, 82, 74, 5665, 79, 50, 26, 67100, 24, 67, 38, 57};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr,0,n-1);
printf("Arreglo ordenado:\n");
printArr(arr,n);
return 0;
}
vectorIn = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23,
78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58,
19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42,
82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72,
39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57,]
def mergeSort(vectorIn):
if len(vectorIn) >1:
half = len(vectorIn)//2
list1 = vectorIn[:half]
list2 = vectorIn[half:]
mergeSort(list1)
mergeSort(list2)
i = 0
j = 0
k = 0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
vectorIn[k] = list1[i]
i+=1
else:
vectorIn[k] = list2[j]
j+=1
k+=1
while i < len(list1):
vectorIn[k] = list1[i]
i+=1
k+=1
while j < len(list2):
vectorIn[k] = list2[j]
j+=1
k+=1
def result(vectorIn):
for i in range(len(vectorIn)):
print(vectorIn[i],end=" ")
print()
mergeSort(vectorIn)
result(vectorIn)
Resultado
1 1 2 2 3 3 6 8 8 9 10 10 12 15 17 17 17 19 22 23 24 25 25 25 26 28 30 30 30 31 32 32 33 34 36 38 39 41 41 42 43 43 44 44 44 44 45 45 47 48 50 52 53 54 56 57 57 57 58 59 60 60 61 64 65 65 67 67 68 69 72 72 74 74 76 77 78 79 80 82 82 82 82 86 86 87 87 87 89 90 90 94 95 98 98 98 98 99 99 100
Este código me costó!!! 2 días de trabajo pero lo logré!! (la cantidad de printf que tiene me delata…, no los quité porque también me costó pensar cómo hacer hablar al programa donde lo necesitaba).
#include <stdio.h>
int merge (int lista[], int min, int mid, int max){
int n1, n2;
n1 = mid - min + 1;
n2 = max - mid;
int arr1[n1];
int arr2[n2];
//Inicializo arrays de comparacion en 0
for (int i = 0; i < n1; i++) {
arr1[i] = 0;
}
for (int i = 0; i < n2; i++) {
arr2[i] = 0;
}
//Lleno los arrays de comparacion
for (int i = 0; i < n1; i++) {
arr1[i] = lista[min+i];
}
for (int i = 0; i < n2; i++) {
arr2[i] = lista[mid+1+i];
}
/*printf("La primera mitad es:\n");
for (int i = 0; i < n1; i++) {
printf("(%d): %d // ", i, arr1[i]);
}
printf("\n La segunda mitad es:\n");
for (int i = 0; i < n2; i++) {
printf("(%d): %d // ", i, arr2[i]);
}*/
//Comparo dos arrays y reemplazo en la lista
int i = 0;
int j = 0;
int goOn = 1;
for (int k = min; k <= max; k++) {
//printf("\nn1 = %d, i = %d, n2 = %d, j = %d\n", n1, i, n2, j);
//printf("\narr1[%d]=%d vs. arr2[%d]=%d\n", i, arr1[i], j, arr2[j]);
//printf("goOn1: %d\n", goOn);
if (i == n1) {
goOn = 0;
lista[k] = arr2[j];
j++;
//printf("Gano default lista[%d] = %d\n", k, lista[k]);
} else if (j == n2) {
goOn = 0;
lista[k] = arr1[i];
i++;
//printf("Gano default lista[%d] = %d\n", k, lista[k]);
}
//printf("goOn2: %d\n", goOn);
if (goOn) {
if (arr1[i] <= arr2[j]) {
lista[k] = arr1[i];
i++;
} else {
lista[k] = arr2[j];
j++;
}
//printf("Gano comparacion lista[%d] = %d\n", k, lista[k]);
}
}
/*printf("\nLa lista ordenada sería:\n");
for (int k = min; k <= max; k++) {
printf("(%d): %d //\n", k, lista[k]);
}*/
}
int mergeSort(int lista[], int min, int max) {
// printf("Entra mergeSort\n\n");
// printf("min = %d // max = %d\n", min, max);
for (int i = min; i <= max; i++){
// printf("[%d]: %d\n", i, lista[i]);
}
if (min < max) {
int mid;
mid = (min + max)/2;
//printf("mid = %d\n", mid);
mergeSort(lista, min, mid);
mergeSort(lista, mid+1, max);
merge(lista, min, mid, max);
}
return 0;
}
int main (int argc, const char * argv[]) {
// Para ingresar los numeros 1 a 1
int number;
printf("Cuantos caracteres va a trabajar:\n");
scanf("%d", &number);
int arr[number];
for (int i = 0; i < number; i++) {
arr[i] = 0;
}
printf("Escriba los numeros:\n");
for (int i = 0; i < number; i++) {
scanf("%d", &arr[i]);
}
/*int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9 ,98, 28, 86, 69, 3 ,17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int number;
number = sizeof(arr)/sizeof(arr[0]);*/
printf("Esta es tu lista:\n");
for (int i = 0; i < number; i++){
printf("(%d): %d\n", i, arr[i]);
}
printf("Ahora voy a ordenar tu lista.........\n");
mergeSort(arr, 0, number-1);
printf("\nEsta es tu lista ordenada:\n");
for (int i = 0; i < number; i++){
printf("(%d): %d\n", i, arr[i]);
}
}
les dejo mi github
https://github.com/ruben-xe
#include <stdio.h>
void insertionSort(int vector[], int num)
{
int varV, j;
for(int i = 0; i < num; i++)
{
varV = vector[i];
j = i - 1;
while(j >= 0 && vector[j] > varV)
{
vector[j + 1] = vector[j];
j = j - 1;
}
vector[j + 1] = varV;
}
}
int imprimir(int v[], int n)
{
for(int i = 0; i < n; i++)
printf("%d, ", v[i]);
printf("\nFin del ordenamiento");
}
int main(int argc, char const *argv[])
{
int vec[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,
57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
int numero = sizeof(vec) / sizeof(vec[0]);
insertionSort(vec, numero);
imprimir(vec, numero);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// Fusiona dos subarray de arr[].
// Primer sub-array es arr[l..m]
// Segundo sub-array es arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k; //variables que utilizamos en los ciclos for
int n1 = m - l + 1;
int n2 = r - m;
/* creamos dos array temporales */
int L[n1], R[n2];
/* Copiamos los datos a los array temporales L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* fucionamos los array temporales en el arr[l..r]*/
i = 0; // Índice inicial del primer subarray
j = 0; // Índice inicial del segundo subarray
k = l; // Índice inicial de subarray fucionados
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copiamos los elementos restantes de L[] si no hay alguno mas*/
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copiamos los elementos restantes de R[], sino hay alguno mas */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l es para el indice izquierdo y r es el indice derecho del
sub-array de arr para ser ordenado */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;
// ordenar primera y segunda mitad del arr
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
// Declaramos nuestro arr
int arr[] = { 3, 94, 86, 82, 90,10, 87, 36, 61, 8,17, 15, 22, 10, 23,78, 25, 2, 30, 45,
98, 43, 98, 59, 53,57, 2, 64, 1, 41,32, 58, 19, 99, 60,74, 48, 80, 44, 25,68, 1, 89, 77, 60,
25, 99, 30, 76, 32,57, 82, 52, 44, 72, 87, 34, 87, 65, 30,54, 6, 31, 33, 44,44, 42, 82, 90, 17,
9,98, 28, 86, 69,3 ,17 ,8 ,45, 98,12, 47, 95, 43, 72,39, 41, 82, 74, 56,
65, 79, 50, 26, 67,100, 24, 67, 38, 57,};
int arr_size = sizeof(arr) / sizeof(arr[0]); //tamaño del array
printf("El array de entrada es: \n"); // imprimimos el array sin ordenar
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1); // ejecutamos el algoritmo de MargeSort
printf("\nEl array ordenado es: \n"); // imprimimos el arreglo ordenado
printArray(arr, arr_size);
return 0;
} ```
Versión en JavaScript
//Order from highest to lowest
const data = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53,
57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32,
57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69,
3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57]
const merge = (arrA, arrB) => {
let resultArr = []
while(arrA.length && arrB.length){
if(arrA[0] > arrB[0]){
resultArr.push(arrA[0])
arrA.shift()
}else{
resultArr.push(arrB[0])
arrB.shift()
}
};
return resultArr.concat(arrA, arrB);
};
const mergeSort = arr => {
if(arr.length < 2){
return arr;
}
let middlePoint = Math.floor(arr.length/2);
let leftArr = mergeSort(arr.slice(0, middlePoint));
let rightArr = mergeSort(arr.slice(middlePoint));
return merge(leftArr, rightArr);
}
console.log(mergeSort(data))
Listo con quickSort:
Código en C:
#include<stdio.h>
#include<stdlib.h>
int arr[100]; // array to be sorted
int main()
{
size_t i = 0; // size_t es un tipo de entero sin signo
FILE *fp = fopen("quick.txt", "r");;
if (fp == NULL)
{
fprintf(stderr, "Error leyendo el archivo.\n");
return 1;
}
while (fscanf(fp, "%d", &arr[i]) == 1)
{
i++;
}
fclose(fp);
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1); // sort the array
printf("Sorted array: ");
printf("[ ");
for( i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("]");
return 0;
}
void swap (int *n1, int *n2)
{
int temp = *n1;
*n1 = *n2;
*n2 = temp;
}
void quickSort(int arr[], int left, int right)
{
if (left < right)
{
// Divide and Conquer
int pivot = divide (arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
int divide (int arr[], int left, int right)
{
int pivot = arr[right];
size_t i = (left - 1); //indice del menor elemento
size_t j;
for (j=left; j<=right-1; j++)
{
if (arr[j] > pivot)
{
i++; // siguiente elemento de orden "pequeño"
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[right]); // poner el valor pivot en la mitad y valor de la mitad al final del arreglo
return (i+1); // Devuelve el valor de la mitad
}
Archivo de txt:
3 94 86 82 90 10 87 36 61 8 17 15 22 10 23 78 25 2 30 45 98 43 98 59 53 57 2 64 1 41 32 58 19 99 60 74 48 80 44 25 68 1 89 77 60 25 99 30 76 32 57 82 52 44 72 87 34 87 65 30 54 6 31 33 44 44 42 82 90 17 9 98 28 86 69 3 17 8 45 98 12 47 95 43 72 39 41 82 74 56 65 79 50 26 67 100 24 67 38 57
#include<stdio.h>
int arr[100];
int main()
{
int n,i;
int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41,
32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44,
44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr,0,n-1);
printf("Sorted array: \n");
for(i=0;i<n;i++)
printf(" %d \n",arr[i]);
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
return 0;
}
int merge(int arr[],int l,int m,int h)
{
int arr1[100],arr2[100];
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0;i<n1;i++)
arr1[i]=arr[l+i];
for(j=0;j<n2;j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999;
arr2[j]=9999;
i=0;j=0;
for(k=l;k<=h;k++)
{
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}```
No. ordenados:
1_ 1_ 2_ 2_ 3_ 3_ 6_ 8_ 8_ 9_ 10_ 10_ 12_ 15_ 17_ 17_ 17_ 19_ 22_ 23_ 24_ 25_ 25_ 25_ 26_ 28_ 30_ 30_ 30_ 31_ 32_ 32_ 33_ 34_ 36_ 38_ 39_ 41_ 41_ 42_ 43_ 43_ 44_ 44_ 44_ 44_ 45_ 45_ 47_ 48_ 50_ 52_ 53_ 54_ 56_ 57_ 57_ 57_ 58_ 59_ 60_ 60_ 61_ 64_ 65_ 65_ 67_ 67_ 68_ 69_ 72_ 72_ 74_ 74_ 76_ 77_ 78_ 79_ 80_ 82_ 82_ 82_ 82_ 86_ 86_ 87_ 87_ 87_ 89_ 90_ 90_ 94_ 95_ 98_ 98_ 98_ 98_ 99_ 99_ 100_
Reto completado!!
const datacollection = new Array(
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2 ,30 ,45,
98, 43, 98, 59, 53,
57, 2 ,64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1 ,89 ,77 ,60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6 ,31 ,33 ,44,
44, 42, 82, 90, 17,
9, 98 ,28, 86, 69,
3, 17 ,8 ,45 ,98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57,
)
function swap(items, leftIndex, rightIndex){
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)],
i = left,
j = right;
while (i <= j) {
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i <= j) {
swap(items, i, j);
i++;
j--;
}
}
return i;
}
function quickSort(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index < right) {
quickSort(items, index, right);
}
}
return items;
}
var sortedArray = quickSort(datacollection, 0, datacollection.length - 1);
console.log(sortedArray);```
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
const middleIdx = Math.floor(array.length / 2);
const left = array.slice(0, middleIdx);
const right = array.slice(middleIdx);
return merge(mergeSort(left, 'left'), mergeSort(right, 'right'));
}
function merge(left, right) {
let merged = [];
while (true) {
if (right.length === 0 || left.length === 0) {
merged = merged.concat(left, right);
break;
}
if (left[0] < right[0]) {
merged.push(left.shift());
} else {
merged.push(right.shift());
}
}
return merged;
}
const input = [3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57];
console.log(`Processing array with ${input.length} items`);
console.time('Merge Sort');
mergeSort(input);
console.timeEnd('Merge Sort');
output:
Processing array with 100 items
Merge Sort: 0.589ms
var unsortedArr = [3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
function merge(leftArr, rightArr) {
var sortedArr = [];
while (leftArr.length && rightArr.length) {
if (leftArr[0] >= rightArr[0]) {
sortedArr.push(leftArr[0]);
leftArr = leftArr.slice(1)
} else {
sortedArr.push(rightArr[0]);
rightArr = rightArr.slice(1)
}
}
while (leftArr.length)
sortedArr.push(leftArr.shift());
while (rightArr.length)
sortedArr.push(rightArr.shift());
return sortedArr;
}
function mergesort(arr) {
if (arr.length < 2) {
return arr; }
else {
var midpoint = parseInt(arr.length / 2);
var leftArr = arr.slice(0, midpoint);
var rightArr = arr.slice(midpoint, arr.length);
return merge(mergesort(leftArr), mergesort(rightArr));
}
}
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));
function quickSort(array) {
if (array.length < 1) {
return [];
}
let pivot = array[0];
let left = [];
let right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] > pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return [].concat(quickSort(left), pivot, quickSort(right));
}```
Implementé un merge sort!
def mergeSort(numbers):
if len(numbers) == 1:
return numbers
middle = len(numbers) // 2
lower_half = mergeSort(numbers[:middle])
upper_half = mergeSort(numbers[middle:])
sorted_numbers = []
lower_amount = len(lower_half)
upper_amount = len(upper_half)
lower_pos = 0
upper_pos = 0
count = len(numbers)
while count:
if lower_half[lower_pos] > upper_half[upper_pos]:
sorted_numbers.append(lower_half[lower_pos])
lower_pos += 1
if lower_pos == lower_amount:
sorted_numbers += upper_half[upper_pos:]
break
else:
sorted_numbers.append(upper_half[upper_pos])
upper_pos += 1
if upper_pos == upper_amount:
sorted_numbers += lower_half[lower_pos:]
break
return sorted_numbers
def run():
n = int(input('How many numbers does your list have? '))
numbers = []
for number in range(n):
numbers.append( int( input() ) )
numbers = mergeSort(numbers)
print(numbers)
run()
Bien, ya tengo el algoritmo ahora lo pondre a practicar.
Mi solución con merge sort en python
import math
def merge_sort(array):
if len(array) < 2:
return array
middle = math.floor(len(array)/2)
leftSide = array[0: middle]
rightSide = array[middle: len(array)]
return merge(merge_sort(leftSide), merge_sort(rightSide))
def merge(left, right):
result = []
while left and right:
if(left[0] <= right[0]):
result.append(left.pop(0))
else:
result.append(right.pop(0))
while len(left):
result.append(left.pop(0))
while len(right):
result.append(right.pop(0))
return result
values = [3,94,86,82,90,10,87,36,61,8,17,15,22,10,23,78,25,2,30,45,98,43,98,59,53,57,2,64,1,41,32,58,19,99,60,74,48,80,44,25,68,1,89,77,60,25,99,30,76,32,57,82,52,44,72,87,34,87,65,30,54,6,31,33,44,44,42,82,90,17,9,98,28,86,69,3,17,8,45,98,12,47,95,43,72,39,41,82,74,56,65,79,50,26,67,100,24,67,38,57]
print(merge_sort(values))
Solución con QuickSort
#include <stdio.h>
void swap(int *n1, int *n2)
{
int temp = *n1;
*n1 = *n2;
*n2 = temp;
}
int partition(int arrayList[], int low, int high)
{
int pivot = arrayList[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arrayList[j] <= pivot)
{
i++;
swap(&arrayList[i], &arrayList[j]);
}
}
swap(&arrayList[i + 1], &arrayList[high]);
return (i + 1);
}
void quickSort(int arrayOrder[], int low, int high)
{
if (low < high)
{
int pivot = partition(arrayOrder, low, high);
quickSort(arrayOrder, low, pivot - 1);
quickSort(arrayOrder, pivot + 1, high);
}
}
void displayArray(int arrayList[], int size)
{
int i;
for (i = 0; i < size; i++)
{
printf("\n");
printf(" | %d |\n", arrayList[i]);
}
}
int main(int argc, char const *argv[])
{
int arrayOrdenar[] = {3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57};
int n = sizeof(arrayOrdenar) / sizeof(arrayOrdenar[0]);
printf("\n");
quickSort(arrayOrdenar, 0, n - 1);
printf("\n Lista Ordenada:");
displayArray(arrayOrdenar, n);
return 0;
}
;
int merge(int arr[], int l, int m, int h,int size);
int main()
{
int n;
n=sizeof(arreglo)/sizeof(arreglo[0]);
merge_sort(arreglo,0,n-1,n);
for(int i=0;i<n;i++)
cout<<arreglo[i]<<",";
return 0;
}
int merge_sort(int arr[],int low,int high, int size)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid,size);
merge_sort(arr,mid+1,high,size);
// Combine
merge(arr,low,mid,high,size);
}
return 0;
}
int merge(int arr[],int l,int m,int h,int size)
{
int arr1[size/2],arr2[size/2]; // Two temporary arrays to
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0;i<n1;i++)
arr1[i]=arr[l+i];
for(j=0;j<n2;j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;j=0;
for(k=l;k<=h;k++) //process of combining two sorted arrays
{
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
Java
function mergesort(array){
if(array.length == 1){
return array;
}
let n = array.length;
let m = Math.ceil(n/2);
let array1 = [];
let array2 = [];
for(let i=0; i<m; i++){
array1.push(array.shift());
}
for(let i=m; i<n; i++){
array2.push(array.shift());
}
array1 = mergesort(array1);
array2 = mergesort(array2);
return merge(array1, array2);
}
function merge(array1, array2){
let merged_array = [];
while(array1.length && array2.length){
if(array1[0]<array2[0]){
merged_array.push(array1.shift());
}else{
merged_array.push(array2.shift());
}
}
while(array1.length){
merged_array.push(array1.shift());
}
while(array2.length){
merged_array.push(array2.shift());
}
return merged_array;
}
let nums = [3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99,60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57];
nums = mergesort(nums);
console.log(nums);
public class Merge_sort {
public void mergeSort(int array[], int left, int right){
if(left< right){
int mid = (left + right)/2;
//primera mitad
mergeSort(array, left, mid);
//segunda mitad
mergeSort(array, mid+1, right);
merge(array,left,mid,right);
}
}
public void merge(int []array, int l, int m, int r){
int i,j, n1, n2;
n1 = m - l +1;
n2 = r - m;
int [] L = new int[n1];
int [] R = new int[n2];
for (i=0; i< n1; i++)
L[i] = array[l +i];
for (j=0; j<n2; j++)
R[j] = array[m+1+j];
//realizar el merge
i = 0; j=0;
int k = l;
while(i<n1 && j<n2){
if(L[i]>= R[j]) {
array[k] = L[i];
i++;
}else{
array[k] = R[j];
j++;
}
k++;
}
while (i < n1 ){
array[k] = L[i];
i++;
k++;
}
while (j < n2){
array[k] = R[j];
j++;
k++;
}
}
public void print (int [] array){
for (int z = 0; z < array.length ; z++) {
System.out.println(array[z]);
}
}
}
///////////////////
public static void main(String[] args) {
int [] array = {3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99,60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57};
Merge_sort ms = new Merge_sort();
ms.print(array);
ms.mergeSort(array, 0, array.length-1);
System.out.println("despues....");
ms.print(array);
}
}
utilice insertion sort con python
numbers = []
def insert_values():
with open('challenge2.txt', 'r')as f:
for line in f:
numbers.append(int(line))
def insertion_sort():
n = len(numbers)
for i in range(n):
j = i-1
current = numbers[i]
while j>=0 and numbers[j]<current:
numbers[j+1]= numbers[j]
j-=1
numbers[j+1] = current
print(numbers)
if __name__ == "__main__":
insert_values()
insertion_sort()
```
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?