Ordinamento per selezione su file binario

L'implementazione del metodo di ordinamento per selezione su file non presenta particolari difficoltà. L'unica differenza, rispetto al caso di ordinamento di un vettore, è che per accedere a un elemento occorre posizionarsi nel punto opportuno del file e leggere/scrivere il valore. Nel caso di ordinamento di numeri interi, l'accesso all'i-esimo elemento si ottiene facendo fseek(fd, i*sizeof(int), fd), e poi leggendo/scrivendo il valore.

Dal momento che l'algoritmo confronta ogni volta un elemento i-esimo con tutti i successivi, si è scelto di leggere questo valore x da file una volta sola, e poi di confrontarlo con i successivi. In altre parole, facciamo un ciclo su tutti gli elementi tranne l'ultimo. Per ogni elemento, lo leggiamo nella variabile x, e poi facciamo il ciclo interno di confronto con i successivi elementi.

Ogni volta che si incontra un elemento minore di x, facciamo lo scambio. A questo punto dobbiamo tenere conto che l'elemento i-esimo non è più x, dato che è stato sostituito con un altro elemento. Invece di rileggere di nuovo l'elemento i-esimo, mettiamo direttamente in x il valore dell'elemento che abbiamo appena scritto nella posizione i del file.

Il programma completo ssort.c è riportato qui sotto.

/*
  Selection sort su file binario.
*/

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

int main(int argn, char *argv[]) {
  FILE *fd;
  int size, dim;
  int i, j;
  int x, y;

		/* controllo argomenti */
  if(argn-1!=1) {
    printf("Errato numero di argomenti\n");
    exit(1);
  }

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

		/* determina la dimensione del file */
  fseek(fd, 0, SEEK_END);
  size=ftell(fd);
  dim=size/sizeof(int);
  printf("Numero di interi su file: %u/%d = %u\n", size, sizeof(int), dim);


		/* selection sort */
  for(i=0; i<=dim-1-1; i++) {
    fseek(fd, i*sizeof(int), SEEK_SET);
    fread(&x, sizeof(int), 1, fd);

    for(j=i+1; j<=dim-1; j++) {
      fseek(fd, j*sizeof(int), SEEK_SET);
      fread(&y, sizeof(int), 1, fd);

      if(y<x) {
	fseek(fd, i*sizeof(int), SEEK_SET);
	fwrite(&y, sizeof(int), 1, fd);

	fseek(fd, j*sizeof(int), SEEK_SET);
	fwrite(&x, sizeof(int), 1, fd);

	x=y;
      }
    }
  }

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

  return 0;
}