Complejidad



Nombre
Principales Características
Orden de Complejidad
Método
Burbuja
*Es un método sencillo
*se basa en la ordenación
Por cambio
O(n2)--- O(1)

Peor= 322,313
Mejor= 6

MétodoInserción
*Conocido como juego de las
Cartas.
*Ordena los dos primeros
Elementos de la lista y el tercer
Se inserta donde corresponda
O(n2)-- O(1)

Peor= 1524
Mejor= 1
Método
Quicksort*Es eficiente y representa una
Mejora sustancial al método
De intercambio directo
Promedio: O(n log n)
Peor caso: O(n2)

Peor= 27940
Mejor= 10

Método
Merge sort

*Así llamado comoordena-miento Por mezcla ya que divide los Elementos entre la mitad y así Mismo vuelve a tomar la división
O(n log n) - O(n)

Peor= 9
Mejor= 2

Método
Shell
*Cada Elemento es comparado de maneraadyacente
*El valor insertado será comparado con los elementos Izquierdos que ya estaban anteriormente.
O(n1.25) - O(1)
Peor= 1522
Mejor= 4

Búsqueda
Secuencial

*Compara cada elementoDel vector con el que se desea encontrar
*Puede no estar ordenado
Mejor caso: O(1)
Peor caso: O(n)

Peor= 9
Mejor= 6

Búsqueda
Binaria

*Debe estar ordenado
*Se examina el vectorpartiendo desde el elemento central de la lista

Mejor caso: O(1)
Peor caso: O(log)

Peor= 8
Mejor= 4





void burbuja(int *v, int n)
{
bool sw = true;
int li = 0;
do{
li++;
sw = true;
for (int i = 0; i < n - li; i++)
{
if ( v[i] > v[i+1] )
{
int tem = v[i];
v[i] =v[i+1];
v[i+1] = tem;
sw = false;
}
}
}
while(!sw);
}

void insercion( int * v, int n)
{
for (int i = 1, j = 0; i < n; i++){
int tem = v[i];
j = i - 1;
while ( j >= 0 && tem < v[j])
{
v[j+1] = v[j];
j--;
}
v[j+1] = tem;...