Bubble-sort
Es el algoritmo de clasificación más simple que funciona intercambiando repetidamente los elementos adyacentes si están en orden incorrecto. Es poco eficiente, pero es muy seguro, es sencillo de entender, de explicar y de programar. Debido a su simplicidad, la clasificación de burbujas se usa a menudo para introducir el concepto de un algoritmo de clasificación.
Ejemplo:
primer paso:
( 5 1 4 2 8) -> ( 1 5 4 2 8), aquí, el algoritmo compara los dos primeros elementos y cambia desde 5> 1.
(1 5 4 2 8) -> (1 4 5 2 8), Cambiar desde 5> 4
(1 4 5 2 8) -> (1 4 2 5 8), Cambiar desde 5> 2
(1 4 2 5 8 ) -> (1 4 2 5 8 ), Los elementos ya están en orden (8> 5), el algoritmo no los intercambia.
Segundo pase:
( 1 4 2 5 8) -> ( 1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), Swap since 4> 2
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Ahora, la matriz ya está ordenada, pero nuestro algoritmo no sabe si está
completa. El algoritmo necesita un pase completo sin ningún intercambio
para saber que está ordenado.
Tercer Pase:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8 )
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Ejemplo en C:
Insertion-sort
Es más eficiente y más rápido, la ordenación por inserción se utiliza cuando el número de elementos es pequeño. También puede ser útil cuando la matriz de entrada está casi ordenada, solo unos pocos elementos están mal ubicados en una gran matriz completa.
Ejemplo Código en Java:
Quick-sort
Elige un elemento como pivote y divide la matriz dada alrededor del pivote seleccionado. Hay muchas versiones diferentes de quickSort que seleccionan pivote de diferentes maneras.
1-Elija siempre el primer elemento como pivote.
2-Elija siempre el último elemento como pivote (implementado a continuación)
3-Elija un elemento aleatorio como pivote.
4-Elija la mediana como pivote.
El proceso clave en quickSort es la partición (). El objetivo de las particiones es, dada una matriz y un elemento x de la matriz como pivote, colocar x en su posición correcta en una matriz ordenada y colocar todos los elementos más pequeños (más pequeños que x) antes de x, y poner todos los elementos mayores (más grandes que x) después X
Radix-Sort
La idea de Radix Sort es hacer una ordenación dígito por dígito comenzando desde el dígito menos significativo hasta el dígito más significativo.
// C++ implementation of Radix Sort
#include<iostream>
using namespace std;
// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n]; // output array
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i – 1];
// Build the output array
for (i = n – 1; i >= 0; i–)
{
output[count[ (arr[i]/exp)%10 ] – 1] = arr[i];
count[ (arr[i]/exp)%10 ]–;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << » «;
}
// Driver program to test above functions
int main()
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr)/sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}
Bucket-Sort
Es principalmente útil cuando la entrada se distribuye uniformemente en un rango.
bucketSort (arr [], n)
1) Crea n buckets vacíos (o listas).
2) Haga lo siguiente para cada elemento de matriz arr [i].
……. a) Inserte arr [i] en el bucket [n * array [i]]
3) Ordene los buckets individuales usando el ordenamiento por inserción.
4) Concatenar todos los buckets ordenados.
Heap-Sort
Merge-Sort (Ordenamiento por mezcla)
Fue desarrollado por Van Neumann, divide en listas más pequeñas
Divide la matriz de entrada en dos mitades, se llama a sí misma para las dos mitades y luego combina las dos mitades ordenadas.
Refencias:
Bubble Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/bubble-sort/
Insertion Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/insertion-sort/
Quick Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/quick-sort/
Radix Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/radix-sort/
Bucket Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/bucket-sort-2/
Heap Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/heap-sort/
Merge Sort – GeeksforGeeks. (2019). Retrieved 24 August 2019, from https://www.geeksforgeeks.org/merge-sort/
Blog Personal 