Corso di Informatica 1 (IN110)

Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo di ordinamento Quick sort

/*
**  quick_sort.c
**
**  Codifica in linguaggio C dell'algoritmo Quick Sort
**  per l'ordinamento di un array di numeri interi.
**
**  Pseudo-codifica dell'algoritmo
**
**  Quick_Sort(V, p, r):
**    1. pivot = Trova_Pivot(V, p, r)
**    1. se p<r e pivot != -1 allora
**    2.   q = Partiziona(V, p, r, pivot)
**    3.   Quick_Sort(V, p, q)
**    4.   Quick_Sort(V, q+1, r)
**  End
**
**  Trova_Pivot(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)
**    1. x = V(p)
**    2. i = p
**    3. j = r
**    4. ripeti:
**    5.   fintanto che V(j)>=x ripeti:
**    6.     j = j-1
**    7.   fintanto che V(i)<x ripeti:
**    8.     i = i+1
**    9.   se i<j allora scambia V(i) e V(j)
**   10. fintanto che i<j
**   11. restituisci j
**  End
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Marzo 2001
**
*/

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

/*
 *  Trova_pivot: 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 trova_pivot(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);
}

/*
 * Quick_sort: funzione ricorsiva
 */

void quick_sort(int V[], int p, int r) {
  int q, pivot;
  pivot = trova_pivot(V, p, r);
  if (p<r && pivot!=-1) {
    q = partiziona(V, p, r, pivot);
    quick_sort(V, p, q);
    quick_sort(V, q+1, r);
  }
  return;
}

/*
 *  Funzione principale
 */

int main(void) {
  int n, A[100];
  n = leggi_array(A);
  quick_sort(A, 0, n-1);
  stampa_array(A, n);
  return(0);
}

Author: Marco Liverani - Last modified: Thursday November 03, 2016 - URI: http://www.mat.uniroma3.it/users/liverani/IN1/quick_sort.shtml