ImplementationMerge

Aus ProgrammingWiki

Archivierte Version vom 2013-12-09T08:37:40+00:00. Aktuelle Version

Hier eine mögliche Implementation von Mergesort als Klasse:

public class MergeSorter
{
    private int[] a;
    private int[] b;    // Hilfsarray

    public void sort(int[] a)
    {
        this.a=a;
        b=new int[a.length];
        mergesort(0, a.length-1);
    }

    private void mergesort(int l, int r)
    {
        if (l<r)
        {
            int m=(l+r)/2;
            mergesort(l, m);
            mergesort(m+1, r);
            merge(l, m, r);
        }
    }

    void merge(int l, int m, int r)
    {
        int i, j, k;

        for (i=l; i<=r; i++)
            b[i]=a[i];

        i=l; j=m+1; k=l;
        while (i<=m && j<=r)
            if (b[i]<=b[j])
                a[k++]=b[i++];
            else
                a[k++]=b[j++];

        while (i<=m)
            a[k++]=b[i++];
    }
}

Die Anwedung der Sortierung erfolgt durch den folgenden Aufruf in der Main:

int[] c = {1,19,15,18,20,9,7,5,24,1,9,16,12};
MergeSorter s=new MergeSorter();
s.sort(c);

ImplementationMerge

Suche