Un algoritmo de ordenamiento es aquel algoritmo que te ayuda a poner elementos de una lista en orden.
Estos son algunos de los algoritmos de ordenamiento:
Bubble sort
El ordenamiento por burbuja (Bubble Sort) es un algoritmo bastante simple. Empiesa al principio de los datos y compara los primeros dos datos para saber cual es mayor, despues repite el siguiente paso pero comparando el primer par de datos con el segundo.
Su rendimiento promedio y mas bajo es: O(n2), por lo tanto no es conveniente usarlo en cantidades largas de datos. Este método es: IterativoCodigo en C
while (!done)
{
done = TRUE;
numItems--; /* one less item left to sort after each pass */
endItem = numItems * itemSize;
for (i = 0; i < endItem; i += itemSize)
{
if (compareFunc(VoidPtrOffset(list, (i + itemSize)),
VoidPtrOffset(list, i)) < 0)
{
Swap(VoidPtrOffset(list, i),
VoidPtrOffset(list, (i + itemSize)), temp, itemSize);
done = FALSE;
.
Selection sort
El algoritmo de seleccion (Selection Sort) Busca el valor minimo y lo pocisiona en el primer lugar de la cadena, repite este paso dependiendo de la cantidad de valores en la cadena.Tiene eficiencia de O(n2), por lo tanto no es conveniente usarlo en cantidades largas de datos.
Este método es : Iterativo
Codigo en C
void selection_sort(int list[], int n){
int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i+1; j < n; j++)
{
if (list[j] < list[min])
{
min = j;
}
}
swap(&list[i], &list[min]);
}
}
void printlist(int list[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",list[i]);
Insertion sort
Codigo en C
temp = malloc(itemSize);
assert(temp != NULL);
endItem = numItems * itemSize;
for (i = itemSize; i < endItem; i += itemSize)
{
j = i;
memcpy(temp, VoidPtrOffset(list, i), itemSize);
while ((j > 0) &&
(compareFunc(temp, VoidPtrOffset(list, (j - itemSize))) < 0))
{
memcpy(VoidPtrOffset(list, j),
VoidPtrOffset(list, (j - itemSize)),
itemSize);
j -= itemSize;
}
A continuación un vídeo que demuestra los diferentes sonidos que hacen estas cadenas al ser ordenadas por cada tipo de algoritmo.
Rendimiento
Esta tabla explica cuales son los peores y mejores casos de los rendimientos de la tabla.
Ejemplo graficado:Quicksort
Aquí se demuestra que el rendimiento de nlogn es superior que a el de n^2, demostrando que n^2 es el peor caso.
Bibliografia:
http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
http://cprogramminglanguage.net/selection-sort-algorithm-c-souce-code.aspx
http://www.youtube.com/watch?v=t8g-iYGHpEA
http://www.monografias.com/trabajos32/algoritmos-de-ordenamiento/algoritmos-de-ordenamiento.shtml
http://ict.udlap.mx/people/ingrid/Clases/IS211/Ordenar.html
http://www.gratisblog.com/weblogs/juand/organizacion_1_.jpg
Codigos de:
http://michael.dipperstein.com/
Animaciones de:
http://www.sorting-algorithms.com/
for(i=0;i<n;i++)
printf("%d\t",list[i]);
Insertion sortEl algoritmo de inserción (Insertion Sort) usa elementos de la cadena uno por uno ordenandolos e insertandolos en su posicion correcta en una nueva cadena.
Este método es: Iterativo
Este método es: Iterativo
Codigo en C
temp = malloc(itemSize);
assert(temp != NULL);
endItem = numItems * itemSize;
for (i = itemSize; i < endItem; i += itemSize)
{
j = i;
memcpy(temp, VoidPtrOffset(list, i), itemSize);
while ((j > 0) &&
(compareFunc(temp, VoidPtrOffset(list, (j - itemSize))) < 0))
{
memcpy(VoidPtrOffset(list, j),
VoidPtrOffset(list, (j - itemSize)),
itemSize);
j -= itemSize;
}
Shell sort
El allgoritmo Shell inventado por Donald Shell en el 59´ mueve mas de un elemento al mismo tiempo.
Este método es: Iterativo
Codigo en C
temp = malloc(itemSize);
assert(temp != NULL);
for (increment = 1;
increment <= numItems;
increment = (increment * 3) + 1);
endItem = numItems * itemSize;
for (increment /= 3; increment > 0; increment /= 3)
{
incrementItem = increment * itemSize;
for (i = incrementItem; i < endItem; i += itemSize)
{
j = i;
memcpy(temp, VoidPtrOffset(list, i), itemSize);
while ((j >= incrementItem) &&
(compareFunc(temp,
VoidPtrOffset(list, (j - incrementItem))) < 0))
{
memcpy(VoidPtrOffset(list, j),
VoidPtrOffset(list, (j - incrementItem)),
itemSize);
j = j - incrementItem;
} memcpy(VoidPtrOffset(list, j), temp, itemSize);
Merge sort
El ordenamiento por mezcla (Merge Sort) empieza comparando cada dos elementos y cambiándolos si el segundo debe ir antes que el primero, y después repite este paso con todas las parejas de datos de la cadena y las ordena. En su peor caso: O(n log n).
Este método es: Recursivo
pivot = (numItems - 1) / 2;
MergeSort(list, (pivot + 1), itemSize, compareFunc);
MergeSort(VoidPtrOffset(list, ((pivot + 1) * itemSize)),
numItems - pivot - 1, itemSize, compareFunc);
merged = malloc(numItems * itemSize);
assert(merged != NULL);
pivot *= itemSize;
numItems *= itemSize;
lowPtr = 0;
highPtr = pivot + itemSize;
mergedPtr = 0;
while ((lowPtr <= pivot) && (highPtr < numItems))
{
if (compareFunc(VoidPtrOffset(list, lowPtr),
VoidPtrOffset(list, highPtr)) < 0)
{
memcpy(VoidPtrOffset(merged, mergedPtr),
VoidPtrOffset(list, lowPtr),
itemSize);
lowPtr += itemSize;
}
else
{
memcpy(VoidPtrOffset(merged, mergedPtr),
VoidPtrOffset(list, highPtr),
itemSize);
highPtr += itemSize;
}
mergedPtr += itemSize;
}
if (lowPtr > pivot)
{
/* finish high half */
while(highPtr < numItems)
{
memcpy(VoidPtrOffset(merged, mergedPtr),
VoidPtrOffset(list, highPtr),
itemSize);
mergedPtr += itemSize;
highPtr += itemSize;
}
}
else
{
/* finish low half */
while(lowPtr <= pivot)
{
memcpy(VoidPtrOffset(merged, mergedPtr),
VoidPtrOffset(list, lowPtr),
itemSize);
mergedPtr += itemSize;
lowPtr += itemSize;
}
}
Heapsort
El ordenamiento de montículos (Heapsort) funciona determinando cual es el elemento mas grande o mas chico de una cadena y posicionando lo al principio o a el final de esta y continua con el resto de la lista pero de una manera muy eficiente. En su peor caso O(n logn) .
Este metodo es: Recursivo
Codigo en C
int (*compareFunc) (const void *, const void *))
{
size_t i;
void *temp;
if (numItems <= 1)
{ return;
}
/* create temporary swap variable */
temp = malloc(itemSize);
assert(temp != NULL);
/* build a heap adding one element at a time */
for (i = numItems / 2; i > 0; i--)
{
SiftDown(list, i, numItems - 1, itemSize, compareFunc, temp);
}
SiftDown(list, 0, numItems - 1, itemSize, compareFunc, temp);
while (numItems > 1)
{
Swap(list, VoidPtrOffset(list, ((numItems - 1) * itemSize)) , temp,
itemSize);
numItems--;
SiftDown(list, 0, numItems - 1, itemSize, compareFunc, temp);
}
free(temp);
return;
Quicksort
El ordenamiento rapido (Quick Sort) hace una particion agarra a un elemento para hacer una particion y los elementos menores a este se mueven a una posición anterior y los mayores a una posición mas adelante.
Este método es : Recursivo
Codigo en C
if (numItems > 1)
{
temp = malloc(itemSize);
assert(temp != NULL);
left = 0;
right = (numItems - 1) * itemSize;
while(TRUE)
{
while (left < right)
{
left += itemSize;
if (compareFunc(VoidPtrOffset(list, left), list) > 0)
{
break;
}
}
if (left > right)
{
break;
}
while (left <= right)
{
if (compareFunc(VoidPtrOffset(list, right), list) <= 0)
{
break;
}
right -= itemSize;
}
if (left >= right)
{
break;
}
Swap(VoidPtrOffset(list, left), VoidPtrOffset(list, right), temp,
itemSize);
}
Swap(list, VoidPtrOffset(list, right), temp, itemSize);
free(temp);
QuickSort(list, right / itemSize, itemSize, compareFunc);
QuickSort(VoidPtrOffset(list, (right + itemSize)),
numItems - ((right / itemSize) + 1), itemSize, compareFunc);
A continuación un vídeo que demuestra los diferentes sonidos que hacen estas cadenas al ser ordenadas por cada tipo de algoritmo.
Rendimiento
Esta tabla explica cuales son los peores y mejores casos de los rendimientos de la tabla.
Ejemplo graficado:Quicksort
Bibliografia:
http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
http://cprogramminglanguage.net/selection-sort-algorithm-c-souce-code.aspx
http://www.youtube.com/watch?v=t8g-iYGHpEA
http://www.monografias.com/trabajos32/algoritmos-de-ordenamiento/algoritmos-de-ordenamiento.shtml
http://ict.udlap.mx/people/ingrid/Clases/IS211/Ordenar.html
http://www.gratisblog.com/weblogs/juand/organizacion_1_.jpg
Codigos de:
http://michael.dipperstein.com/
Animaciones de:
http://www.sorting-algorithms.com/
No hay comentarios:
Publicar un comentario