public class Sorts {
    protected static void swap(Object[] a, int e1, int e2) {
        Object tmp = a[e1]; a[e1] = a[e2]; a[e2] = tmp;
    }
    public static void insertionsort(Comparable[] data) {
        Comparable tmp;
        int i, j;
        for (i = 1; i < data.length; i++) {
            tmp = data[i];
            for (j = i; j > 0 && tmp.compareTo(data[j-1]) < 0; j--)
                data[j] = data[j-1];
            data[j] = tmp;
        }
    }
    public static void selectionsort(Comparable[] data) {
        int i,j,least;
        for (i = 0; i < data.length-1; i++) {
            for (j = i+1, least = i; j < data.length; j++)
                if (data[j].compareTo(data[least]) < 0)
                    least = j;
            swap(data,least,i);
        }
    }
    public static void quicksort(Comparable[] data, int first, int last) {
        int lower = first + 1, upper = last;
        swap(data,first,(first+last)/2);
        Comparable bound = data[first];
        while (lower <= upper) {
            while (data[lower].compareTo(bound) < 0)
                 lower++;
            while (bound.compareTo(data[upper]) < 0)
                 upper--;
            if (lower < upper)
                 swap(data,lower++,upper--);
            else lower++;
        }
        swap(data,upper,first);
        if (first < upper-1)
            quicksort(data,first,upper-1);
        if (upper+1 < last)
            quicksort(data,upper+1,last);
    }
    public static void quicksort(Comparable[] data) {
        if (data.length < 2)
            return;
        int max = 0;
        // find the largest element and put it at the end of data;
        for (int i = 1; i < data.length; i++)
            if (data[max].compareTo(data[i]) < 0)
                max = i;
        swap(data,data.length-1,max);    // largest el is now in its
        quicksort(data,0,data.length-2); // final position;
    }
    public static void insertionsort(Comparable[] data, int first, int last) {
        Comparable tmp;
        int i, j;
        for (i = first; i <= last; i++) {
            tmp = data[i];
            for (j = i; j > 0 && tmp.compareTo(data[j-1]) < 0; j--)
                data[j] = data[j-1];
            data[j] = tmp;
        }
    }
    public static void quicksort2(Comparable[] data, int first, int last) {
        if (last - first < 30)
             insertionsort(data,first,last);
        else {
             int lower = first + 1, upper = last;
             swap(data,first,(first+last)/2);
             Comparable bound = data[first];
             while (lower <= upper) {
                 while (data[lower].compareTo(bound) < 0)
                     lower++;
                 while (bound.compareTo(data[upper]) < 0)
                     upper--;
                 if (lower < upper)
                     swap(data,lower++,upper--);
                 else lower++;
             }
             swap(data,upper,first);
             if (first < upper-1)
                  quicksort2(data,first,upper-1);
             if (upper+1 < last)
                  quicksort2(data,upper+1,last);
        }
    }
    public static void quicksort2(Comparable[] data) {
        if (data.length < 2)
            return;
        int max = 0;
        // find the largest element and put it at the end of data;
        for (int i = 1; i < data.length; i++)
            if (data[max].compareTo(data[i]) < 0)
                max = i;
        swap(data,data.length-1,max);     // largest el is now in its
        quicksort2(data,0,data.length-2); // final position;
    }
    static Comparable[] temp; // used by merge();
    protected static void merge(Comparable[] data, int first, int last) {
        int mid = (first + last) / 2;
        int i1 = 0, i2 = first, i3 = mid + 1;
        while (i2 <= mid && i3 <= last)
            if (data[i2].compareTo(data[i3]) < 0)
                 temp[i1++] = data[i2++];
            else temp[i1++] = data[i3++];
        while (i2 <= mid)
            temp[i1++] = data[i2++];
        while (i3 <= last)
            temp[i1++] = data[i3++];
        for (i1 = 0, i2 = first; i2 <= last; data[i2++] = temp[i1++]);
    }
    public static void mergesort(Comparable[] data, int first, int last) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergesort(data, first, mid);
            mergesort(data, mid+1, last);
            merge(data, first, last);
        }
    }
    public static void mergesort(Comparable[] data) {
        temp = new Comparable[data.length];
        mergesort(data,0,data.length-1);
    }
}

 


Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.35
by FdA