No entiendo este algoritmo de ordenamiento:
const int ArraySize = 7;
int Numeros[ArraySize] = { 30, 50, 20, 10, 40, 80, 15 };
for (int StartIndex = 0; StartIndex < ArraySize; StartIndex++)
{
int SmallestIndex = StartIndex;
for (int CurrentIndex = StartIndex + 1; CurrentIndex < ArraySize; CurrentIndex++)
{
if (Numeros[CurrentIndex] < Numeros[SmallestIndex])
SmallestIndex = CurrentIndex;
}
swap(Numeros[StartIndex], Numeros[SmallestIndex]);
}
Soy un novato en C++, no se quejen. :-\
Yo no es que entienda perfecto el código, yo el que utilizaba y el que entendía a la perfección es el de "Ordenamiento de burbuja"
Pero igual di que entiendes, pone comentarios a los que no sabes que hace y a los que sabes que hace para que quede más fácil explicarte.
Saludos...
Había puesto otra cosa, pero luego vi la variación :P
Es una variación del de Burbuja: http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja
Saludos
Edito: ahora que miro, me recuerda a otro :-\
Si se me hizo similar Novlucker ^^, pero mucho mejor JuszR con ese articulo de la Wiki uno lo entiende mucho más rápido.
Saludos...
Es este exactamente: http://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n (Selection sort).
El tema es que entiendo el algoritmo pero no en el código jeje.
1) Busca el número más bajo
2) Intercambia el index
3) Repite los pasos 1 y 2.
;D
Aha! era el de selección, ahora lo veo :xD Es que el de selección y el de burbuja son iguales salvo por el intercambio, que uno lo hace durante la comparación y el otro al terminar de recorrer todos los valores, es que soy más asiduo de la burbuja o de las funciones sort que vienen integradas :-X
El código es difícil de explicar más claramente, intenta visualizarlo :-\
Saludos
hazte una traza en papel, suele ayudar.
Es basante simple, son dos bucles FOR, dentro de ambos se encuentra la orden de intercambio. Si el número anterior es mayor que el posterior, se intercambian.
Simplemente.
Cita de: Akai en 2 Noviembre 2010, 13:16 PM
hazte una traza en papel, suele ayudar.
Esa es la solución. Es difícil hacer eso teniendo una computadora en frente, pero es muy efectivo. ;D
1) Lee el array [outter for].
2) Compara Current (StartIndex+1) con Smallest que por el momento era 30 (Index 0) [inner for].
3) Si es menor lo intercambia con el momentáneo Smallest [if].
4) Así sucesivamente hasta encontrar el número más chico.
5) Intercambia indexes [swap].
6) Repite todo.Qué difícil que son los algoritmos. ;-)
Yo te recomiendo que mires paso a paso como van cambiando los numeros, me he hecho este código, es igualq ue el tuyo pero me he inventado una fiuncion swap, que tu no la das:
#include <stdio.h>
void swap(int *start, int *small)
{
int i = *start;
*start = *small;
*small = i;
}
int main()
{
const int ArraySize = 7;
int StartIndex = 0;
int CurrentIndex = 0;
int i = 0;
int Numeros[7] = { 30, 50, 20, 10, 40, 80, 15 };
for (StartIndex = 0; StartIndex < ArraySize; StartIndex++)
{
int SmallestIndex = StartIndex;
for (CurrentIndex = StartIndex + 1; CurrentIndex < ArraySize; CurrentIndex++)
{
if (Numeros[CurrentIndex] < Numeros[SmallestIndex])
SmallestIndex = CurrentIndex;
}
swap(&Numeros[StartIndex], &Numeros[SmallestIndex]);
}
for (i = 0; i < 7; i++)
{
printf("Nº: %i\n", Numeros[i]);
}
return 0;
}
Es bastante simple, para cada numero mira si los siguientes son menores, en el caso de que lo sean, llama a la función que los cambia, es una manera eficiente de ordenar una lista. Por ahí te han dejado un link a la wikipedia que lo explica bastante bien.
Cita de: piou en 2 Noviembre 2010, 15:55 PM
Es bastante simple, para cada numero mira si los siguientes son menores, en el caso de que lo sean, llama a la función que los cambia, es una manera eficiente de ordenar una lista. Por ahí te han dejado un link a la wikipedia que lo explica bastante bien.
No es una forma nada eficiente de ordenar el algoritmo de ordenación por selección. Lo que sucede es que es muy simple y por eso es de los primeros algoritmos que se enseñan. Este algoritmo tiene un coste de O(n
2), mientras que otros algoritmos de ordenación como heap sort, merge sort o quicksort tienen costes O(nlogn) (quicksort en caso peor es cuadrático, pero en caso medio tiene esa complejidad). De los algoritmos cuadráticos típicos (selection sort, bubble sort e insertion sort), el único que sirve es insertion sort, porque aunque sea cuadrático en caso peor, generalmente es algo mejor y para entradas pequeñas es más rápido que los que he dicho antes.
Cita de: ghastlyX en 2 Noviembre 2010, 16:06 PM
Cita de: piou en 2 Noviembre 2010, 15:55 PM
Es bastante simple, para cada numero mira si los siguientes son menores, en el caso de que lo sean, llama a la función que los cambia, es una manera eficiente de ordenar una lista. Por ahí te han dejado un link a la wikipedia que lo explica bastante bien.
No es una forma nada eficiente de ordenar el algoritmo de ordenación por selección. Lo que sucede es que es muy simple y por eso es de los primeros algoritmos que se enseñan. Este algoritmo tiene un coste de O(n2), mientras que otros algoritmos de ordenación como heap sort, merge sort o quicksort tienen costes O(nlogn) (quicksort en caso peor es cuadrático, pero en caso medio tiene esa complejidad). De los algoritmos cuadráticos típicos (selection sort, bubble sort e insertion sort), el único que sirve es insertion sort, porque aunque sea cuadrático en caso peor, generalmente es algo mejor y para entradas pequeñas es más rápido que los que he dicho antes.
La sencillez no es una manera de eficiencia? Je je, tienes razón, pero para casos en los que la lista es pequeña, yo prefiero usar un algoritmo pequeño como este que tampoco supone un gaste de rendimiento demasiado perceptible y es más fácil de implementar.
a ver :-( no estudio para ingeniero en sist....ghastlyX explicate bien q me intereso eso...pero en castellano basico
@Flony:
GhastlyX se está refiriendo al número de operaciones (coste) que realiza el algoritmo según el tamaño (talla) de la lista que le pases. En este caso concreto, el ordenamiento por el método de la burbuja realiza en su peor caso(el caso en el que la lista que quieras ordenar esté invertida) n^2 operaciones, siendo n el tamaño de la lista.
Existen luego otros algoritmos que realizan el mismo ordenamiento en menos operaciones (con costes n*log (n), o simplemente lineales (n)).
Lo mejor sería que leyeses sobre Costes computacionales.
bien ahi Akai ;-) me pongo a buscar eso