Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo di ordinamento Bubble sort

/*
**  bubble_sort.c
**
**  Codifica in linguaggio C dell'algoritmo Bubble
**  sort per l'ordinamento di un array di numeri interi.
**
**
**  Pseudo-codifica dell'algoritmo
**
**  Bubble_sort(V):
**    1. flag = 1
**    2. k = n-1
**    3. fintanto che flag = 1 e k>0 ripeti:
**    4.   flag = 0
**    5.   per i=0, ..., k-1 ripeti:
**    6.     se a(i)>a(i+1) allora scambia a(i) ed a(i+1) e poni flag=1
**    7.   k=k-1
**  END
**
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Marzo 2001
**
*/

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

#define MAX 100


/*
 * Legge in input il numero n ed n numeri interi
 * che memorizza nell'array. Restituisce il numero
 * di elementi letti (n).
 */
int leggi_array(int x[]) {
  int i, n;

  printf("Numero di elementi: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    scanf("%d", &x[i]);
  }
  return(n);
}


/*
 * Stampa in output l'array.
 */
void stampa_array(int x[], int n) {
  int i;

  for (i=0; i<n; i++) {
    printf("%d ", x[i]);
  }
  printf("\n");
  return;
}


/*
 * Scambia il contanuto delle due variabili
 * indirizzate dai puntatori x e y.
 */
void scambia(int *x, int *y) {
  int z;

  z = *x;
  *x = *y;
  *y = z;
  return;
}


/*
 * Funzione che implementa l'algoritmo Bubble sort.
 * Riceve come argomento l'array ed il numero di
 * elementi contenuti nell'array. Non restituisce alcun
 * valore, ma modifica il contenuto dell'array, ordinandolo.
 */
void bubble_sort(int x[], int n) {
  int flag=1, k=n-1, i;

  while (flag == 1 && k > 0) {
    flag = 0;
    for (i=0; i<k; i++) {
      if (x[i]>x[i+1]) {
        scambia(&x[i], &x[i+1]);
        flag = 1;
      }
    }
    k = k-1;
  }
  return;
}

/*
 *  Funzione principale
 */
int main(void) {
  int v[MAX], n;

  n = leggi_array(v);
  stampa_array(v, n);
  bubble_sort(v, n);
  stampa_array(v, n);
  return(0);
}