Ordinamento a bolle

Vediamo ora come si può implementare l'algoritmo di ordinamento a bolle direttamente su file. Implementare questo algoritmo direttamente su file, invece di leggere tutto il file in un vettore, è necessario quando la dimensione del file è tale da non entrare tutto in memoria principale.

Usiamo qui una versione semplificata. Ogni passo consiste nella scansione, ed eventuale scambio, di tutti gli elementi del file. Si ripete questo passo fino a quando gli elementi non risultano ordinati.

La differenza fra questo programma e quello analogo di ordinamento su array è minima: a parte l'apertura e chiusura del file, l'unica cosa che occorre sapere è che per guardare quale valore ha un certo intero si usa le funzione fread, e che dopo aver letto, se si vuole scrivere al posto di quello che si è letto, occorre riposizionarsi nel file usando la funzione fseek.

Nel dettaglio:

1. leggiamo due interi
2. se non sono nell'ordine giusto:
   1. si torna indietro nel file di due interi
   2. si scrivono i numeri scambiati
3. si ritorna indietro di un intero nel file

Si noti che tornare indietro di un intero è necessario in entrambi i casi: se non ci sono stati scambi, siamo ora posizionati sul numero che segue l'ultimo letto, mentre ancora ci manca da fare il confronto fra l'ultimo letto e il successivo. Nel caso in cui c'è stato uno scambio, la posizione dopo la scrittura è ancora alla posizione dopo la coppia, per cui va spostata indietro per lo stesso motivo.

Il programma completo bubblesort.c è qui sotto.

/*
  Ordinamento a bolle 
*/

#include<stdlib.h>
#include<stdio.h>

int main() {
  FILE *fd;
  int res;
  int pos;

  int x[2];
  int ordinato;
  int temp;


			/* apre il file */
  fd=fopen("test.dat", "r+");
  if( fd==NULL ) {
    perror("Errore in apertura del file");
    exit(1);
  }


			/* scansione */
  ordinato=0;
  while( !ordinato ) {
    ordinato=1;

    while(1) {
      res=fread(x, sizeof(int), 2, fd);	/* legge due interi */
      if( res!=2 )
        break;

      if( x[0]>x[1] ) {			/* confronto e scambio */
        ordinato=0;

        temp=x[0];
        x[0]=x[1];
        x[1]=temp;

					/* riposiziona il file */
        fseek(fd, -2*sizeof(int), SEEK_CUR);

					/* scrive */
        res=fwrite(x, sizeof(int), 2, fd);
        if( res!=2 ) {
          perror("Errore in scrittura");
          exit(1);
        }
      }

      fseek(fd, -sizeof(int), SEEK_CUR);	/* torna indietro di uno */
    }

    rewind(fd);			/* ricomincia dall'inizio */
  }


		/* chiude il file */
  fclose(fd);

  return 0;
}