2018-06-18_2 esercizio "integer sort"
Tema
Descrivere un algoritmo che, dati n numeri interi compresi nell’intervallo da 0 a k, svolga un’analisi preliminare del suo input e poi risponda nel tempo O(1) a qualsiasi domanda su quanti degli n interi ricadono nell’intervallo [a..b] con a e b interi. Il vostro algoritmo dovrebbe impiegare un tempo È(n+k) per l’analisi preliminare.
Svolgimento
Nota: descrivere = scrivere.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_ELEMENTS 20
#define MAX_ABS_VALUES 50
int *prepare(int values[], int size, int *min, int *max) {
int i;
int * aux;
if(size == 0) {
return NULL;
}
*min = values[0];
*max = values[0];
for(i = 0; i < size; i++) {
if(values[i] < *min) *min = values[i]; if(values[i] > *max) *max = values[i];
}
aux = malloc(sizeof(int) * (*max - *min + 1));
for(i = 0; i < *max - *min + 1; i++) aux[i] = 0;
for(i = 0; i < size; i++) {
aux[values[i] - (*min)]++;
}
for(i = 1; i < *max - *min; i++) aux[i] = aux[i] + aux[i-1];
return aux;
}
int main(int argc, char *argv[])
{
int *values; // contiene i valori non ordinati
int min; // il valore più piccolo
int max; // il valore più grande
// la dimensione del vettore di appoggio è data da min - max
int *aux; // l'array ausiliario dell'integer sort
int i;
int da, a; // il minimo e massimo tra i valori chiesti all'utente
int ind_da, ind_a; // gli indici più vicini a da e a
values = malloc(sizeof(int) * N_ELEMENTS);
srand(time(0));
for(i = 0; i < N_ELEMENTS; i++)
values[i] = rand() % (MAX_ABS_VALUES * 2) - MAX_ABS_VALUES;
aux = prepare(values, N_ELEMENTS, &min, &max);
for(i = 0; i < max - min; i++) printf("%d: %d\t", i+min, aux[i]);
printf("\nInserire il primo elemento: ");
scanf("%d", &da);
printf("Inserire il secondo elemento: ");
scanf("%d", &a);
if(a - da < 0) { a = da+a; da = a-da; a = da-a;} // scambio gli elementi se a < da
printf("La quantità di numeri compresi tra %d e %d e' %d\n", da, a, (a>=max?aux[max-min-1]:aux[a-min]) - (da<=min?0:aux[da-min-1]));
system("PAUSE");
return 0;
}
Commento all'algoritmo
L'algoritmo è una variante dell'integer sort.
Dati n numeri compresi tra n1 e n2 si inizializza un array di k+1 elementi indicizzati da 0 a n2 - n1 e inizializzati a zero.
Esempio (vettore n):
| 6 | -7 | 5 | -1 | 8 | 0 | 4 | -2 | -8 | 3 |
Per ogni elemento in n si incrementano gli indici corrispondenti come nell'integer sort:
Esempio (vettore k):
| Ind: | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Val: | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
poi si cumula la somma da n1 a n2
| Ind: | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Val: | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 4 | 5 | 5 | 5 | 6 | 7 | 8 | 9 | 9 | 10 |
Questo richiede ancora un costo Θ(n+k).
In tempo O(1) si estrae l'elemento precedente di A (o zero se A è il primo) e si sottrae all'elemento B.
Esempio:
A = -2
B = 3
k[A-1] = 3
k[B] = 5
k[B] - k[A-1] = 2
Se A o B sono rispettivamente minore del più piccolo e maggiore del più grande è sufficiente considerare il primo e l'ultimo elemento.
Come richiesto, il tempo di preparazione è Θ(n+k) e quello di consultazione è O(1).
Commento al codice
Si è deciso di separare la procedura principale (il tema d'esame) da quella di appoggio, contenente l'inizializzazione e le richieste all'utente.
La chiamata prevede il ritorno di tre valori: l'array k e il minimo e il massimo. Questi due valori sono due int nella procedura di appoggio, che sono passati come puntatori alla procedura principale.
Due costanti indicano la dimensione dell'array e l'intervallo di numeri che è possibile inserire in senso assoluto (es. 5 => da -5 a +5) ottenendo un intervallo di n*2+1 valori.
Nella procedura principale, i valori di minimo e massimo vanno inizializzati con uno dei valori dell'array, poi con un ciclo si valuta se abbassare il minimo o alzare il massimo.
È necessario anche inizializzare i valori dell'array k a zero, perché c'è una probabilità non nulla che alcuni valori non compaiano mai (soprattutto se |n| è piccolo e |k| è grande).
Rispetto all'integer sort è necessario un ulteriore ciclo per calcolare il valore cumulato, che però non ha impatti sul costo asintotico.
Nella procedura principale, a parte il popolamento dell'array con valori casuali, è degno di nota il sistema per gestire la richiesta di valori minori del minimo o maggiori del massimo, che per sintesi è reso con l'utilizzo di operatori ternari.