Por cada reordenación estás haciendo tres copias de cadenas:
strcpy(aux, nombres[f]);
strcpy(nombres[f], nombres[f + 1]);
strcpy(nombres[f + 1], aux);
La copia de cadenas es una operación costosa, y además la haces ¡tres veces!. En lugar de ordenar cadenas, ordena índices:
void Ord_Alfabeticamente(char *nombres[], int indices[], int n)
{
for (int k = 0; k < n - 1; ++k)
{
for (int f = 0; f < (n - 1) - k; ++f)
{
if (strcmp(nombres[indices[f]], nombres[indices[f + 1]]) > 0)
{
int aux = indices[f];
indices[f] = indices[f + 1];
indices[f + 1] = aux;
}
}
}
}
Verás que es significantementenotablemente más rápido, puedes ver el código funcionando en Try it online!.