bool ordenado = false;
while (!ordenado) {
ordenado = true;
for (int j = 2; j < size; j += 2)
{
if (v[j] < v[j - 1]) {
ordenado = false;
int auxiliar = v[j];
v[j] = v[j - 1];
v[j - 1] = auxiliar;
}
}
for (int j = 1; j < size; j += 2)
{
if (v[j] < v[j - 1]) {
ordenado = false;
int auxiliar = v[j];
v[j] = v[j - 1];
v[j - 1] = auxiliar;
}
}
}
En el brick sort entiendo que su complejidad es O(n^2) tanto en su medio como en su peor caso, ya que, entre otras cosas, es un sucedáneo del bubble sort. Pero hay algo que no entiendo, buscando información he visto que en su caso mejor este algoritmo tiene orden n y no entiendo por qué.
El entrar en el while ya te supone un n, y para ver que está ordenado tienes que entrar al for. Entonces yo pienso que su complejidad en el mejor caso es n^2, cuál es mi error?
Gracias de antemano.