se fai un copia incolla del codice che ti ho postato e lo lanci questo fa proprio quello che chiedi.
Hai identificato questo thread con C++, quindi presumo che tu conosca le librerie standard e l'uso dei namespace. Per quest'ultimo cerca su google "namespace c++" per avere informazioni.

Ho usato la classe template (sai cosa sono?) vector come vettoro di int, ma puoi tranquillamente usare un vettore di int creato con int *.

Il concetto del codice che ti ho postato si basa sul fatto di non spostare fisicamente i record della tua rubrica, cosa che può diventare molto pesante quando fossero diverse centinaia e fossero memorizzate su un file. Invece di spostare fisicamente i record si riordinano dei riferimenti ai vari record. Così nel vettore che ti ho indicato all'inizio memorizzi la sequenza naturale dei record, se sono 4, come nel mio esempio, il vettore conterrà {0,1,2,3}, cioè la sequenza non ordinata (il primo elemento del vettore punta al record numero 0, il secondo al numero 1 e così via).
Per il riordinamento ho utilizzato la funzione standard sort , perchè è già fatta ma tu se vuoi ne puoi scrivere una a tuo uso e consumo che utilizzi l'algoritmo di riordinamento che meglio conosci.

Alla funzione sort standard puoi passare gli iteratori alla classe vettore (questo lo puoi studiare in rete o sui libri di testo in tuo possesso) e il puntatore ad una funzione di riordinamento che agisce sulla struttura della tua rubrica. Cerca su google "sort c++" per avere più informazioni sulla sort.

codice:
bool mycompare (int i, int j) {
  return strcmp(riga[i].cognome, riga[j].cognome) < 0;
}
la funzione di confronto riceve i valori del tuo vettore che sono riferimenti alla tua struttura, li trasformi nel valore del membro della struttura che vuoi ordinare (io ho usato il cognome) e tutto va a posto.

Se questo è troppo difficile per te prova a scriverti una funzione di riordinamento utilizzando l'algoritmo che trovi più semplice che vediamo come va modificata per soddisfare le tue consegne.
ciao
sergio