Corso di Informatica 1 (IN110)

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); }

Author: Marco Liverani - Last modified: Friday November 14, 2014 - URI: http://www.mat.uniroma3.it/users/liverani/IN1/bubble_sort.shtml