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