ORDENAMIENTO POR INSERCIÓN EN ARREGLOS Y LISTAS DOBLES
Ordenamiento por inserción (insertion sort) es una forma muy sencilla de organizar u ordenar para un ser humano, se puede comparar con la manera en que se organiza un mazo de cartas enumeradas en forma arbitraria este algoritmo consiste en ir escogiendo cada número y compararlo con el anterior de derecha a izquierda, si el número de la derecha es mayor que el de la izquierda entonces los números cambiaran de lugar hasta que el arreglo se encuentre completamente ordenado.
CÓDIGO DE ORDENACIÓN PARA ARREGLOS
Este código se realizó en NetBeans IDE 8.2
package insercion;
public class Insercion
{
void ordenamiento_incercion(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int num = arr[i];
int j = i-1;
while (j>=0 && arr[j] > num)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = num;
}
}
static void mostrarArreglo(int arr[])
{
int n = arr.length;
System.out.println("Arreglo: ");
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args){
int arr[] = {12, 11, 13, 5, 6,2,1,0,10,8,4};
Insercion ob = new Insercion();
ob.ordenamiento_incercion(
mostrarArreglo(arr);
}
}
Imagen tomada de: http://miftyisbored.com/insertion-sort-implementation-java/
CÓDIGO DE ORDENAMIENTO POR INSERCIÓN PARA LISTAS DOBLEMENTE ENLAZADAS
CONTROL:
import model.nodo;
public class cNodo {
//declaración del identificador del objeto
nodo cab;
// Métodos
// Constructor
public cNodo() {
}
// Create
private nodo create(int id, String valor){
return new nodo(id, valor);
}
private nodo setInfo(nodo nn, int id, String valor){
nn.setId(id);
nn.setValor(valor);
return nn;
}
//inserción ordenada
private nodo insert(nodo nn){
if(this.cab != null){//si la lista tiene datos
nodo p = this.cab;
while(p.getSig()!=null){
p=p.getSig();
}
nn.setAnt(p);
p.setSig(nn);
return nn;
}else{//si la lista está vacia
this.cab = nn;
return this.cab;
}
}
//método público del create
public boolean insert(int id, String valor){
if(this.insert(this.create(id, valor))!=null){
return true;
}else{
return false;
}
}
//READ
public String showAll(){
nodo p = this.cab;
String cad="";
//Algoritmo de recorrido en listas
while(p!=null){
cad = cad + p.getId()+","+p.getValor()+"\n";
System.out.println(p.getId()+","+p.getValor());
p = p.getSig();
}
System.out.println("----------------");
return cad;
}
public String select(int id){
if(this.cab != null){
//cuenta cuantos elementos hay
int n = 0;
nodo p = this.cab;
while (p.getSig()!=null){
n++;
p=p.getSig();
}
//llama al método recursivo search
nodo piv = this.search(id, this.cab, p, n);
if(piv!=null){
return piv.getId()+","+piv.getValor();
}else{
return null;
}
}else{
return null;
}
}
private nodo search(int id, nodo in, nodo fin, float n){
nodo piv = in;
if(n >= 0.5){
if(piv.getId() != id){// si lo encuentra
n=n/2;
if(piv.getId() < id){// se mueve a la derecha
for (int i=0 ; i < n ; i++){
piv = piv.getSig();
}
return this.search(id, piv, fin, n);
}else{// se mueve a la izquierad
for (int i=0 ; i < n ; i++){
piv = piv.getAnt();
}
return this.search(id, in, piv, n);
}
}else{
return piv;
}
}else{
return null;
}
}
//UPDATE
public boolean update(int id, String valor){
// cuenta el número de nodos
int n = 0;//declaración del contador
nodo p = this.cab;
while (p.getSig()!=null){//algoritmo de recorrido
n++;//contador
p=p.getSig();//movimiento
}
nodo resp = this.search(id, this.cab, p, n);// busca el elemnto
if(resp != null){//si lo encuentra actualiza la info
this.setInfo(resp, id, valor);
return true;
}else{//si no lo encuentra
return false;
}
}
//DELETE
public boolean delete(int id){
// cuenta el número de nodos
int n = 0;//contador
nodo p = this.cab;
while (p.getSig()!=null){
n++;
p=p.getSig();
}
nodo resp = this.search(id, this.cab, p, n);//Busca el nodo
if(resp != null){// si lo encuentra lo elimiena
if(resp.getSig() != null){//si no es el último nodo
//se genera el salto desde el nodo siguiente al nodo anterior
resp.getSig().setAnt(resp.getAnt());
}
if(resp.getAnt() != null){//si no es el primer nodo
//se genera el salto del nodo anterior al nodo siguiente
resp.getAnt().setSig(resp.getSig());
}else{//reposiciona la cabeza porque va a borrar el primer nodo
this.cab = this.cab.getSig();
}
return true;
}else{//si no lo encuentra
return false;
}
}
// ORDENACIÓN
private nodo exchange(nodo p, nodo q){
nodo s = null;
nodo r = null;
if(p.getSig() != q){
s = p.getSig();
r = q.getAnt();
}
p.setSig(q.getSig());
q.setAnt(p.getAnt());
if(q.getSig() != null){
q.getSig().setAnt(p);
}
if(p.getAnt() != null){
p.getAnt().setSig(q);
}else{
this.cab = q;
}
if(s != null && r != null){
r.setSig(p);
s.setAnt(q);
q.setSig(s);
p.setAnt(r);
}else{
q.setSig(p);
p.setAnt(q);
}
return q;
}
public void insertionSort(){
nodo p = this.cab.getSig();
nodo max = p.getSig();
boolean flag;
while(p != null){
flag = true;
while(flag == true && p.getAnt()!=null){
flag = false;
if(p.getAnt().getId() > p.getId()){
p = this.exchange(p.getAnt(), p);
flag = true;
}
}
p = max;
if(p != null){
max = p.getSig();
}
}
}
DESCARGAR CÓDIGOS
Comentarios
Publicar un comentario