Como planteariais este problema?( en C)

[leosansan]

.La complejidad de mi algoritmo es simplemente O(n). ( ya sé que no estamos discutiendo eficiencia)

Eso no lo dudo, pero te recuerdo que el algoritmo, tal como lo planteates daría para la serie de números:
121 174 39 158 144 167 76 80 112 167 59 152 161 136 129
max=174    cuasi_max=121, cuando este último debería ser 167.
De ahí la introducción de :

Código (cpp) [Seleccionar] Expandir

else if (a[i]>cuasi_maxi ) {cuasi_maxi=a[i];}
Saludos!.

[BatchianoISpyxolo]

No tiene sentido ordenar y luego extraer, quicksort en el mejor caso es n*log(n), unido a extraer quedaría O(n*log(n) + n).En el caso peor, sería O(n²).La complejidad de mi algoritmo es simplemente O(n). ( ya sé que no estamos discutiendo eficiencia)

Extraer es constante, no lineal: O(2) = O(1). Pero que sí, que se puede hacer lineal llevando el max y el cuasi_max a la par.

[oxi12pek]

Muchas gracias a todos por responder. Oye BatchianoISpyxolo!!! Podrias explicarme lo que ocurre en la funcion ord_ins?¿?¿ Es que no lo entiendo del todo.
Saludos!

[BatchianoISpyxolo]

Lo mejor para entender como funciona sería una explicación gráfica. Así que te recomiendo algún pdf o algún vídeo incluso mejor.

Pongo el código para que lo puedas leer mejor:

Ordenación por inserción:

Código (c) [Seleccionar] Expandir

void ord_ins(int v[], int n) {
   int i,j,x;
   for (i=1;i<n;i++) {
       x = v[i];
       j = i-1;
       while ( (j>-1) && (v[j]>x) )
           v[j+1] = v[j--];
       v[j+1] = x;
   }
}

índices del vector: 0..N-1 y ordenación ascendente

Bueno supongamos que tenemos el array { 7, 2, 6, 4, 8, -3 }

1º. Suponemos que el primer elemento está ordenado.

2º. Recorremos el array desde 1 hasta N-1, porque el primer elemento suponemos que está ordenado.

3º. Entonces teniendo en cuenta el for de 1 a N-1, en cada iteración del for escogeremos el elemento

Código [Seleccionar] Expandir

array[i]. Es decir, en la primera iteración el 2, en la siguiente al 6, en la siguiente al 4... Es decir x =

Código [Seleccionar] Expandir

array[i]

4º Insertamos ordenadamente x en el subvector generado por los índices 0 e i-1. En este caso insertar x en el subvector { 7 }, porque va desde 0 a i-1, y como i vale 1, pues es el subvector array(0..0). Como 2 es menor que siete, lo insertamos delante.

array { 2, 7, 6, 4, 8, -3 } Hay que mover el 7 a la derecha y el 2 situarlo en la primera posición

5º Volvemos al paso 3 hasta terminar el ciclo for

-> { 2, 7, 6, 4, 8, -3 } seleccionamos el 6 e insertamos en { 2, 7 } => { 2, 6, 7, 4, 8, -3 }

-> { 2, 6, 7, 4, 8, -3 } seleccionamos el 4 e insertamos en { 2, 6, 7 } => { 2, 4, 6, 7, 8, -3 }

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el 8 e insertamos en { 2, 4, 6, 7 } => { 2, 4, 6, 7, 8, -3 } <= El elemento está ya ordenado

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el -3 e insertamos en { 2, 4, 6, 7, 8 } => { -3, 2, 4, 6, 7, 8,} <= Vualá, vector ordenado

Recuerda que para cada inserción tenemos que mover todos los elelementos desde la posición donde vamos a insertar hasta i-1 una posición hacia adelante.

Saludos y espero que lo entiendas.

[oxi12pek]

Vale vale ahora lo veo mejor. Es que entregar un trabajo que no entiende ni lo que pasa no es muy educativo... jajajaja
Muchas gracias por la explicacion, esta muy bien.