Ordenamiento de Listas

• Mantener listas de elementos ordenados es importante para facilitar las busquedas
• Una lista de elementos desordenaods no permite realizar busquedas de manera eficiente
• Hay muchos algoritmos de ordenamiento
• La meta es encontrar algoritmos cada vez mas eficientes

Selection sort

• consiste en usar el menor elemento, sacarlo de la lista, ponerlo en otra y repetir hasta que la lista original este vacia
  Este enfoque es costoso en terminos de espacio, pero se puede mejorar:
  static void selectSort(){
  int end=size-1;
  for(int current=0;current<end;current++){
  swap(current,minimo(current,end));
  }
  }

Bubble Sort

• Consiste en "empujar" el mayor hacia el final de la lista
• Unicamente se compara elementos adyacentes

Insertion sort

Las listas se dividen en dos partes
* elementos ordenados * elementos desordenados

• El algoritmo saca el primer eliminado de la lista desordenada y lo inserta en la lista ordenada
• No existen dos listas aparte, la division es logica
• Al insertar en la lista ordenada, se van corriendo los elementos hasta encontrar la posicion que le corresponde al elemento por insertar

void insert(int[] a){
int in =0;
int out =0;
for(out=1;out<a.Lenght;out++){
int temp =a[out];
in=out
while(in>0&&a[in-1]>=temp){
a[in]=a[in-1];
--in;
}
a[in]=temp;
}
}

Merge Sort

• Parte el array en dos
• Llama recursivamente en cada mitad
• Cuando la recursion llega a array de un elemento, se devuelve y empieza a unir un orden cada subArray

QuickSort

EL mas popular de los algoritmos de ordenamiento
El mas util en la mayoria de casos
Particiona el arreglo en dos y se llama recursivamente en cada mitad

El paso inicial es calcular el pivote(elemento central del arreglo)
Iterativamente compara los elementos previos y posteriores al pivote contra el valor del pivote

Hace swap de los elementos para colocarlos en la mitad que le corresponde
Cuando los indices se cruzan, se recorre en cada mitad

Radix Sort

• Utiliza enfoque diferente al resto de algoritmos de ordenamiento vistos
• Los algoritmos vistos consideran la llave(el elemento de la lista) como unidad indivisible
• 100 se considera como el numero 100
• Radix divide su la llave en cada uno de sus digitos y ordena por cada uno de estos

• Radix =base/raiz del sistema numerico
  Si se ordenan numeros en base 10, radix=10
  Si se ordenan los numeros en base 2,radix=2

Binary Search

• Busca un elemento en una lista o en un array ordenado
• Compara el elemento central del array con el elemento buscado
• Si el buscado==Central, termina .
  central>buscado, se busca en mitad inferior
  central<Buscado, se busca en la mitad superior

---