Java Arrays Sort Object Source
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Veränderung (zum vorhergehenden Autor) (Änderung, Korrektur, Normalansicht)

Verändert: 1c1,92
Beschreibe hier die neue Seite.
Von SoftwareDenkSport 1 Auflösung


Der folgende Ausschnitt stammt aus dem Originalsource von "class Arrays" und sollte alle Fragen beantworten, die sich in Bezug auf eine weitere Optimierbarkeit von "sort" stellen:

[[Code]
public static void sort(Object[] a) {
Object aux[] = (Object[])a.clone();
mergeSort(aux, a, 0, a.length);
}

/**
* Sorts the specified range of the specified array of objects into
* ascending order, according to the natural ordering of its
* elements. All elements in this range must implement the
* Comparable interface. Furthermore, all elements in this range
* must be mutually comparable (that is, e1.compareTo(e2)
* must not throw a ClassCastException? for any elements
* e1 and e2 in the array).<p>
*
* This sort is guaranteed to be stable: equal elements will
* not be reordered as a result of the sort.<p>
*
* The sorting algorithm is a modified mergesort (in which the merge is
* omitted if the highest element in the low sublist is less than the
* lowest element in the high sublist). This algorithm offers guaranteed
* n*log(n) performance, and can approach linear performance on nearly
* sorted lists.
*
* @param a the array to be sorted.
* @param fromIndex the index of the first element (inclusive) to be
* sorted.
* @param toIndex the index of the last element (exclusive) to be sorted.
* @throws IllegalArgumentException? if fromIndex > toIndex
* @throws ArrayIndexOutOfBoundsException? if fromIndex < 0 or
* toIndex > a.length
* @throws ClassCastException? if the array contains elements that are
* not mutually comparable (for example, strings and
* integers).
* @see Comparable
*/
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
Object aux[] = (Object[])a.clone(); // Optimization opportunity
mergeSort(aux, a, fromIndex, toIndex);
}

private static void mergeSort(Object src[], Object dest[],
int low, int high) {
int length = high - low;

// Insertion sort on smallest arrays
if (length < 7) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
swap(dest, j, j-1);
return;
}

// Recursively sort halves of dest into src
int mid = (low + high)/2;
mergeSort(dest, src, low, mid);
mergeSort(dest, src, mid, high);

// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
System.arraycopy(src, low, dest, low, length);
return;
}

// Merge sorted halves (now in src) into dest
for(int i = low, p = low, q = mid; i < high; i++) {
if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}

/**
* Swaps x[a] with x[b].
*/
private static void swap(Object x[], int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
]



KategorieJava

Von SoftwareDenkSport 1 Auflösung
Der folgende Ausschnitt stammt aus dem Originalsource von "class Arrays" und sollte alle Fragen beantworten, die sich in Bezug auf eine weitere Optimierbarkeit von "sort" stellen:

    public static void sort(Object[] a) {
        Object aux[] = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length);
    }

    /**
     * Sorts the specified range of the specified array of objects into
     * ascending order, according to the <i>natural ordering</i> of its
     * elements.  All elements in this range must implement the
     * <tt>Comparable</tt> interface.  Furthermore, all elements in this range
     * must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt>
     * must not throw a <tt>ClassCastException</tt> for any elements
     * <tt>e1</tt> and <tt>e2</tt> in the array).<p>
     *
     * This sort is guaranteed to be <i>stable</i>:  equal elements will
     * not be reordered as a result of the sort.<p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is
     * omitted if the highest element in the low sublist is less than the
     * lowest element in the high sublist).  This algorithm offers guaranteed
     * n*log(n) performance, and can approach linear performance on nearly
     * sorted lists.
     *
     * @param a the array to be sorted.
     * @param fromIndex the index of the first element (inclusive) to be
     *        sorted.
     * @param toIndex the index of the last element (exclusive) to be sorted.
     * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
     *	       <tt>toIndex > a.length</tt>
     * @throws    ClassCastException if the array contains elements that are
     *		  not <i>mutually comparable</i> (for example, strings and
     *		  integers).
     * @see Comparable
     */
    public static void sort(Object[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        Object aux[] = (Object[])a.clone();  // Optimization opportunity
        mergeSort(aux, a, fromIndex, toIndex);
    }

    private static void mergeSort(Object src[], Object dest[],
                                  int low, int high) {
	int length = high - low;

	// Insertion sort on smallest arrays
	if (length < 7) {
	    for (int i=low; i<high; i++)
		for (int j=i; j>low &&
                 ((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
		    swap(dest, j, j-1);
	    return;
	}

        // Recursively sort halves of dest into src
        int mid = (low + high)/2;
        mergeSort(dest, src, low, mid);
        mergeSort(dest, src, mid, high);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
           System.arraycopy(src, low, dest, low, length);
           return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = low, p = low, q = mid; i < high; i++) {
            if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object x[], int a, int b) {
	Object t = x[a];
	x[a] = x[b];
	x[b] = t;
    }


KategorieJava
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 18. April 2001 8:13 (diff))
Suchbegriff: gesucht wird
im Titel
im Text