En esta ocasión les mostrare 2 algoritmos de ordenacion, el Selection sort y el Insertion sort.
Selection Sort.
-> La complejidad del algoritmo es O(n^2) donde n es el numero de elementos, se parece al Bubble sort pero es un poco mas eficiente, dado que a lo sumo hace 1 movimiento de elementos por iteracion.
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
public class Selection {
public void sort(double [] vector) {
for(int i = 0; i < vector.length-1; i++){
int idx = i;
for(int j= i +1; j < vector.length ; j++){
if(vector[j] < vector[idx]){
idx = j;
}
}
if (i != idx){
double aux = vector[idx];
vector[idx] = vector[i];
vector[i] = aux;
}
}
}
}
Su lógica es sencilla, compara cada elemento con sus siguientes, guardando el incide del elemento de menor valor y al final lo intercambia.
ejemplo:
si se dan cuenta hace solo 1 intercambio para hallar el valor adecuado en una pocision, en ese sentido es un poco mas eficiente que el Bubble sort ya que por ejemplo para hallar el numero de menor valor (-5) el algoritmo burbuja primero habria intercambiado a 5 con 1 y luego a 1 con -5 , haciendo mas de un intercambio lo que significa tiempo y memoria.
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
Insertion sort.
-> complejidad del algoritmo O(n) en el mejor caso y O(n^2) en el peor caso, donde n es el numero de elementos. Este sigue siendo un algoritmo poco óptimo sin embargo es mejor que los dos anteriores.
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
private void insertionsort(double [] sinarreglar){
for( int i = 1; i < sinarreglar.length; i++){
double temp = sinarreglar[i];
int j = i-1;
boolean flag = true;
while (j >= 0 && flag) {
if (sinarreglar[j] > temp){
sinarreglar[j + 1] = sinarreglar[j];
}
else{
flag = false;
j++;
}
j--;
}
sinarreglar[j+1] = temp;
}
}
su lógica, aunque sencilla, es un poco mas compleja que los anteriores, básicamente organiza de izquierda a derecha seleccionando siempre un valor, buscando en las anteriores posiciones su lugar correcto e insertándolo.
un gif muy explicativo:
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
Eso fue todo, gracias por pasar!