Implementazioni di algoritmi/Merge sort
Il merge sort è un algoritmo di ordinamento molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.
Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.
L'algoritmo fu inventato da John von Neumann nel 1945.
merge (a[], left, center, right)
i ← left
j ← center + 1
k ← 0
while ((i <= center) && (j <= right)) do
if (a[i] <= a[j]) then
b[k] ← a[i]
i ← i + 1
else
b[k] ← a[j]
j ← j + 1
k ← k + 1
end while
while (i <= center) do
b[k] ← a[i]
i ← i + 1
k ← k + 1
end while
while (j <= right) do
b[k] ← a[j]
j ← j + 1
k ← k + 1
end while
for k ← left to right do
a[k] ← b[k - left]
mergesort (a[], left, right)
if (left < right) then
center ← (left + right) / 2
mergesort(a, left, center)
mergesort(a, center+1, right)
merge(a, left, center, right)
Implementazioni
modificaSeguono alcune implementazioni in vari linguaggi.
C, ricorsivo
modificaQuesta versione di mergeSort lavora su una struttura di tipo nodo che contiene una chiave di ordinamento (key) e un pacchetto di dati (data). Nelle chiamate ricorsive non vengono mai dichiarati nuovi vettori. Vengono dichiarate solo poche variabili nello Stack. la funzione mergeSort si occupa di allocare un solo vettore ausiliario e alla fine di eliminarlo. la funzione Msort esegue il cosiddetto "divide"; La funzione merge "impacchetta il vettore".
///chiamata a funzione:
mergeSort(vettore);
//tipo Dato utilizzato:
typedef struct data{
char*some;
int data;
} DATA;
typedef struct _nodo{
int key;
DATA data;
}nodo;
///Per comodità la variabile n rappresentante la lunghezza del vettore è globale.
int n;
void merge(nodo*a,nodo*aux,int left,int right,int rightEnd){
int i,num,temp,leftEnd=right-1;
temp=left;
num=rightEnd-left+1;
while((left<=leftEnd)&&(right<=rightEnd)){
if(a[left].key<=a[right].key){
aux[temp++]=a[left++];
}
else{
aux[temp++]=a[right++];
}
}
while(left<=leftEnd){
aux[temp++]=a[left++];
}
while(right<=rightEnd){
aux[temp++]=a[right++];
}
for (i=1;i<=num;i++,rightEnd--){
a[rightEnd]=aux[rightEnd];
}
}
void mSort(nodo*a,nodo*aux,int left,int right){
int center;
if (left<right){
center=(left+right)/2;
mSort(a,aux,left,center);
mSort(a,aux,center+1,right);
merge(a,aux,left,center+1,right);
}
}
void mergeSort(nodo*p){
nodo*temp=(nodo*)malloc(sizeof(nodo)*n);
mSort(p,temp,0,n-1);
int i;
for(i=0;i<n;i++)
free(temp);
}
Questa particolare implementazione iterativa dell'algoritmo si basa su un principio inverso alla ricorsione, mentre molte implementazioni iterative tentano di imitare la ricorsione usando una pila che simuli lo stack delle funzioni ricorsive, questa invece effettua le operazioni matematicamente inverse a quelle effettuate dal metodo ricorsivo:
il metodo ricorsivo divide il vettore per due fino ad arrivare all'elemento più piccolo, l'unità indivisibile, dopodiché comincia a fondere i singoli elementi formando delle coppie ordinate, poi crea delle coppie di coppie e cosi via fino ad ottenere il vettore completo ed ordinato, durante queste operazioni però ci sono dei resti, cioè dei pezzi di vettore avanzati che non potevano formare delle coppie, questi nel metodo ricorsivo sono molto facili da gestire poiché vengono lasciati nello stack, e fusi al momento opportuno con il pezzo di vettore precedentemente ordinato tramite il merge.
Nel metodo iterativo puro invece essi sono più difficili da gestire, ma con la variabile sizetomerge e l'operazione %n (resto della divisione per n) si è cercato di simulare proprio questo concetto, ottenendo cosi un algoritmo che operasse come il merge sort ricorsivo, senza usare strutture d'appoggio stack per i dati.
Si Parte dall'elemento indivisibile per formare delle coppie da fondere fino a coprire l'intera dimensione del vettore.
v={3,2,5,6,1}
iterative merge sort()
ciclo
{
elementi indivisibili [3] [2] [5] [6] [1]
merge a due a due [2,3] [5,6] resto: [1] sizetomerge - 1
merge a due a due [2,3,5,6] resto: [1] se ci fossero altri resti verrebbero fusi tra di loro
}
- n è il numero di elementi unitari costituenti la coppia di cui fare il merge. es. n=2 merging [e1] whit [e2]
- merge() effettua il classico merge sul vettore di due sottovettori a e b dove a = [ v[start], v[center] ] e b = [ v[center], v[end] ]
- sizetomerge è la lunghezza del vettore da coprire con il merging delle coppie per la prossima iterazione
- sizetomerge%n è il numero di elementi che non possono essere accoppiati (il resto)
- quando dopo un'iterazione ci sono elementi che non possono essere accoppiati sizetomerge decrementa per lasciarli da parte, mentre se c'era già un vecchio resto i due resti vengono fusi in modo ordinato e poi si decrementa sizetomerge per lasciarli da parte.
- alla fine il resto ordinato viene fuso con il vettore ordinato
void merge(int a[], int start, int center, int end, int size) {
int i, j, k;
int app[size];
i = start;
j = center+1;
k = 0;
while ((i<=center) && (j<=end)) {
if (a[i] <= a[j]) {
app[k++] = a[i++];
} else {
app[k++] = a[j++];
}
}
while (i<=center)
app[k++] = a[i++];
while (j<=end)
app[k++] = a[j++];
for (k=start; k<=end; k++)
a[k] = app[k-start];
printv(a,size);
// printf("merging.. {v[%d] - v[%d]} whit {v[%d] - v[%d]} \n",start,center,center+1,end);
}
void iterativemergesort(int a[],int size) {
int sizetomerge=size-1;
size--;
int i;
int n=2;
while (n<sizetomerge*2) {
for (i=0; (i+n-1)<=sizetomerge; i+=n) {
merge(a,i,(i+i+n-1)/2,i+(n-1),sizetomerge);
}
i--;
if ((sizetomerge+1)%n!=0) {
if (size>sizetomerge)
merge (a,sizetomerge -((sizetomerge)%n),sizetomerge,size,size);
sizetomerge=sizetomerge-((sizetomerge+1)%n);}
n=n*2;
}
if (size>sizetomerge)
merge (a,0,size-(size-sizetomerge),size,size);
}
//dal main chiamare iterativemergesort(vettore,dimensione del vettore);
typedef int Item;
int main() {
const int n=8;
int a[n] = {10, 3, 15, 2, 1, 4, 9, 0};
mergesort(a,0,n-1);
return 0;
}
void mergesort(Item a[], int left, int right) {
if (left<right) {
int center = (left+right)/2;
mergesort(a, left, center);
mergesort(a, center+1, right);
merge(a, left, center, right);
}
}
void merge(Item a[], int left, int center, int right) {
Item* aux = new int[right + 1];
int i,j;
for (i = center+1; i > left; i--)
aux[i-1] = a[i-1];
for (j = center; j < right; j++)
aux[right+center-j] = a[j+1];
for (int k = left; k <= right; k++)
if (aux[j] < aux[i])
a[k] = aux[j--];
else
a[k] = aux[i++];
delete [] aux;
}
import java.util.*;
import java.util.Arrays;
public class Sort {
private static void mergeSort(int[] a, int[] vectorTemp, int left, int right) {
if (left < right) {
int center = (left + right) /2;
mergeSort (a, vectorTemp, left, center);
mergeSort (a, vectorTemp, center+1, right);
merge (a, vectorTemp, left, center+1, right);
}
}
public static void mergeSort(int[] a) {
int vectorTemp [];
vectorTemp = new int [a.length];
mergeSort (a, vectorTemp, 0, a.length-1);
}
private static void merge(int[] a, int[] vectorAux, int posLeft, int posRight, int posEnd) {
int endLeft = posRight -1;
int posAux = posLeft;
int numElemen = posEnd - posLeft +1;
while (posLeft <= endLeft && posRight <=posEnd) {
if ((a[ posLeft ])< (a[posRight]))
vectorAux [posAux++]=a[posLeft++];
else
vectorAux [posAux++] = a[posRight++];
}
while (posLeft <= endLeft)
vectorAux [posAux++]=a[posLeft++];
while (posRight <= posEnd)
vectorAux [posAux++]=a[posRight++];
for (int i=0;i<numElemen;i++,posEnd--)
a[posEnd]=vectorAux[posEnd];
}
public static void main(String[] args) {
int vector[]= { 10, 3, 15, 2, 1, 4, 9, 0};
System.out.println("Array Non Ordinato: "+Arrays.toString(vector)+"\n");
mergeSort(vector);
System.out.println("Array Ordinato Con MergeSort: "+Arrays.toString(vector));
}
}
Java (Versione ottimizzata)
modificaMetodi di supporto
modificaimport java.lang.reflect.Array;
class SortUtils {
/*
* scambia gli elementi dell'array in posizione i, j
* T(n) = O(1)
*/
static <T> void swap(T[] array, int i, int j) {
T aus = array[i];
array[i] = array[j];
array[j] = aus;
}
/*
* calcola la posizione in cui inserire l'elemento key nell'array da from a to
* attraverso la ricerca binaria
* T(n) = O(log n), n = to - from
*/
static <T extends Comparable<T>> int insertionPos(T[] array, int from, int to, T key) {
int low = from, high = to;
while (low < high) {
int mid = (low + high) / 2;
if (array[mid].compareTo(key) > 0)
high = mid;
else
low = mid + 1;
}
return low;
}
/*
* inserisce una porzione di array nel vettore di supporto aus, in modo che risulti ordinato
* T(n) = O(n), n = to - from
*/
static <T extends Comparable<T>> int insert(T[] array, T[] aus, int from, int to, T key, int i) {
int insPos = insertionPos(array, from, to, key);
int n = insPos - from;
System.arraycopy(array, from, aus, i, n);
return n;
}
/*
* esegue il merge delle parti del vettore in maniera ottimizzata
* T(n) = O(n), n = to - from nel caso peggiore
* T(n) = O(1) nel caso migliore
*/
@SuppressWarnings("unchecked")
static <T extends Comparable<T>> void merge(T[] array, int from, int mid, int to) {
if (array[mid - 1].compareTo(array[mid]) <= 0)
return;
int start = insertionPos(array, from, mid, array[mid]);
T[] aus = (T[]) Array.newInstance(array.getClass().getComponentType(), to - start);
int i = 0, posLeft = start, posRight = mid;
while (posLeft < mid && posRight < to) {
int n = insert(array, aus, posRight, to, array[posLeft], i);
i += n;
posRight += n;
if (posRight < to) {
n = insert(array, aus, posLeft, mid, array[posRight], i);
i += n;
posLeft += n;
}
}
if (posLeft < mid)
System.arraycopy(array, posLeft, array, start + i, mid - posLeft);
System.arraycopy(aus, 0, array, start, i);
}
}
Versione ricorsiva
modificapublic class RecursiveMergeSort {
/*
* esegue il merge sort ottimizzato in maniera ricorsiva
* T(n) = O(n log n) nel caso peggiore
* T(n) = O(1) nel caso migliore
*/
public static <T extends Comparable<T>> void sort(T[] array, int from, int to) {
int len = to - from;
if (len == 2) {
/*
* se la lunghezza della porzione da ordinare è 2, evita il merge e le chiamate ricorsive e,
* se necessario, scambia di posto gli elementi
*/
if (array[from].compareTo(array[from + 1]) > 0)
SortUtils.swap(array, from, from + 1);
} else if (len > 2) {
int mid = from + len / 2;
sort(array, from, mid);
sort(array, mid, to);
SortUtils.merge(array, from, mid, to);
}
}
}
Versione iterativa
modificapublic class IterativeMergeSort {
/*
* esegue il merge sort ottimizzato in maniera iterativa
* T(n) = O(n log n) nel caso peggiore
* T(n) = O(1) nel caso migliore
*/
public static <T extends Comparable<T>> void sort(T[] array) {
// caso base (lunghezza porzione = 2)
for (int i = 1; i < array.length; i += 2)
if (array[i - 1].compareTo(array[i]) > 0)
SortUtils.swap(array, i - 1, i);
// passo induttivo (esecuzione del merge)
int n;
for (n = 4; n < array.length; n *= 2) {
int half = n / 2;
for (int i = n, mid = half; i <= array.length; i += n, mid += n)
SortUtils.merge(array, i - n, mid, i);
// l'ultimo merge può essere eseguito solo restano 2 porzioni finali
if (array.length % n > half) {
int last = n * (array.length / n);
SortUtils.merge(array, last, last + half, array.length);
}
}
n /= 2;
// esegue l'ultimo merge nel caso in cui le due porzioni finali siano di lunghezza diversa
if(n < array.length)
SortUtils.merge(array, 0, n, array.length);
}
}
def mergesort(v,l,r):
if l >= r: return
m = (l+r)/2
mergesort(v,l,m)
mergesort(v,m+1,r)
merge(v,l,m,r)
def merge(v,i1,f1,f2):
dim = f2-i1+1
aux = []
i2 = f1+1
i = 0
j = i1
while i1 <= f1 and i2 <= f2:
if v[i1] < v[i2]:
aux.append(v[i1])
i1 += 1
else:
aux.append(v[i2])
i2 += 1
i += 1
if i1 <= f1:
for i in xrange(i,dim):
aux.append(v[i1])
i1 += 1
else:
for i in xrange(i,dim):
aux.append(v[i2])
i2 += 1
for i in xrange(dim):
v[j] = aux[i]
j += 1
REPORT zab.
DATA: BEGIN OF a OCCURS 0,
numero TYPE i,
END OF a.
DATA ls_a LIKE LINE OF a.
DATA left TYPE i.
DATA right TYPE i.
ls_a-numero = 1.
APPEND ls_a TO a.
ls_a-numero = 111.
APPEND ls_a TO a.
ls_a-numero = 41.
APPEND ls_a TO a.
ls_a-numero = 16.
APPEND ls_a TO a.
ls_a-numero = 81.
APPEND ls_a TO a.
ls_a-numero = 4.
APPEND ls_a TO a.
left = 0.
DESCRIBE TABLE a LINES right.
right = right - 1.
LOOP AT a INTO ls_a.
WRITE:/ ls_a-numero.
ENDLOOP.
PERFORM mergesort TABLES a USING left right.
LOOP AT a INTO ls_a.
WRITE:/ ls_a-numero.
ENDLOOP.
FORM mergesort TABLES a STRUCTURE ls_a USING VALUE(left) VALUE(right).
IF left < right .
DATA center TYPE i.
DATA center_piu_1 TYPE i.
center = ( left + right ) DIV 2.
center_piu_1 = center + 1.
PERFORM mergesort TABLES a USING left center.
PERFORM mergesort TABLES a USING center_piu_1 right .
PERFORM merge TABLES a USING left center right.
ENDIF.
ENDFORM.
FORM merge TABLES a STRUCTURE ls_a USING VALUE(left) VALUE(center)
VALUE(right).
DATA i TYPE i.
DATA j TYPE i.
DATA k TYPE i.
DATA i_piu_1 TYPE i.
DATA j_piu_1 TYPE i.
DATA k_piu_1 TYPE i.
DATA k_meno_left_piu_1 TYPE i.
DATA b LIKE ls_a OCCURS 0.
DATA ls_b LIKE LINE OF b.
DATA ls_a_j LIKE LINE OF a.
DATA ls_a_i LIKE LINE OF a.
i = right - left + 1.
DO i TIMES.
APPEND INITIAL LINE TO b.
ENDDO.
i = left.
j = center + 1.
k = left.
WHILE i <= center AND j <= right.
i_piu_1 = i + 1.
READ TABLE a INDEX i_piu_1 INTO ls_a_i.
j_piu_1 = j + 1.
READ TABLE a INDEX j_piu_1 INTO ls_a_j.
IF ls_a_i-numero <= ls_a_j-numero.
k_meno_left_piu_1 = k - left + 1.
MODIFY b INDEX k_meno_left_piu_1 FROM ls_a_i.
i = i + 1.
ELSE.
k_meno_left_piu_1 = k - left + 1.
MODIFY b INDEX k_meno_left_piu_1 FROM ls_a_j.
j = j + 1.
ENDIF.
k = k + 1.
ENDWHILE.
WHILE i <= center.
k_meno_left_piu_1 = k - left + 1.
i_piu_1 = i + 1.
READ TABLE a INDEX i_piu_1 INTO ls_a_i.
MODIFY b INDEX k_meno_left_piu_1 FROM ls_a_i.
i = i + 1.
k = k + 1.
ENDWHILE.
WHILE j <= right.
k_meno_left_piu_1 = k - left + 1.
j_piu_1 = j + 1.
READ TABLE a INDEX j_piu_1 INTO ls_a_j.
MODIFY b INDEX k_meno_left_piu_1 FROM ls_a_j.
j = j + 1.
k = k + 1.
ENDWHILE.
k = left.
WHILE k <= right.
k_meno_left_piu_1 = k - left + 1.
READ TABLE b INDEX k_meno_left_piu_1 INTO ls_b.
i_piu_1 = k + 1.
MODIFY a INDEX i_piu_1 FROM ls_b.
k = k + 1.
ENDWHILE.
ENDFORM.
Altri progetti
modifica
Wikipedia contiene una voce su questo algoritmo
