Gli esercizi
Testi e soluzioni di alcuni esercizi
Algoritmo di ordinamento Quick sort
/*
** quickSort.c
**
** Codifica in linguaggio C dell'algoritmo Quick Sort
** per l'ordinamento di un array di numeri interi.
**
** Pseudo-codifica dell'algoritmo
**
** QuickSort(V, p, r):
** 1. pivot = TrovaPivot(V, p, r)
** 1. se p<r e pivot != -1 allora
** 2. q = Partiziona(V, p, r, pivot)
** 3. QuickSort(V, p, q-1)
** 4. QuickSort(V, q, r)
** End
**
** TrovaPivot(V, i, j)
** 1. se V[i]...V[j] ha almeno due elementi
** distinti, allora restituisce il massimo
** tra i due, altrimenti restituisce -1
** End
**
** Partiziona(V, p, r, pivot)
** 1. i = p
** 2. j = r
** 3. ripeti:
** 4. fintanto che V[j]>pivot ripeti:
** 5. j = j-1
** 6. fintanto che V[i]<pivot ripeti:
** 7. i = i+1
** 8. se i<j allora scambia V[i] e V[j]
** 9. fintanto che i<j
** 10. restituisci j
** End
**
** Marco Liverani (liverani@mat.uniroma3.it) - novembre 2019
**
*/
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
/*
* Scambia il contanuto delle due variabili
* indirizzate dai puntatori x e y.
*/
void scambia (int *a, int *b) {
int c;
c = *a;
*a = *b;
*b = c;
return;
}
/*
* Legge in input il numero n ed n numeri interi
* che memorizza nell'array. Restituisce il numero
* di elementi letti (n).
*/
int leggiArray(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 stampaArray(int x[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%d ", x[i]);
}
printf("\n");
return;
}
/*
* trovaPivot: individua l'elemento pivot in
* V[i]...V[j]; se esistono almeno due elementi
* diversi allora l'elemento scelto come pivot
* e' il piu' grande fra i due. Restituisce -1
* se tutti gli elementi sono uguali.
*/
int trovaPivot(int V[], int i, int j) {
int k;
for (k=i+1; k<j; k++) {
if (V[k]>V[i])
return(V[k]);
else
if (V[k]<V[i])
return(V[i]);
}
return(-1);
}
/*
* Partiziona: funzione per la ridistribuzione
* degli elementi in base al valore del "pivot".
*/
int partiziona(int V[], int p, int r, int pivot) {
do {
while (V[r]>pivot)
r = r-1;
while (V[p]<pivot)
p = p+1;
if (p<r)
scambia(&V[p], &V[r]);
} while (p<r);
return(p);
}
/*
* quickSort: funzione ricorsiva
*/
void quickSort(int V[], int p, int r) {
int q, pivot;
pivot = trovaPivot(V, p, r);
if (p<r && pivot!=-1) {
q = partiziona(V, p, r, pivot);
quickSort(V, p, q-1);
quickSort(V, q, r);
}
return;
}
/*
* Funzione principale
*/
int main(void) {
int n, A[100];
n = leggiArray(A);
quickSort(A, 0, n-1);
stampaArray(A, n);
return(0);
}