Difference between revisions of "User:Jdev/Code/Heap sort"

From Robowiki
Jump to navigation Jump to search
(really bug fix now:))
(i hope last bug fix)
 
Line 16: Line 16:
  
 
     public void sortLastN(int n) {
 
     public void sortLastN(int n) {
         for (; i > 1 && i >= array.length - n; i--) {
+
         for (; i > 0 && i >= array.length - n; i--) {
 
             final RTreeEntry temp = array[i];
 
             final RTreeEntry temp = array[i];
 
             array[i] = array[0];
 
             array[i] = array[0];

Latest revision as of 06:36, 22 December 2011

In Tomcat i has been faced with follow problem: i have an unordered array of hundreds elements and i need get only 5-10 elements (but i do not know exactly how many). My first approach was to sort all array and get first five, but in this case most part of time was spend for nothing. To solve this problem i use now heap sort, which gives every step one greatest element and do not spent time to sort elements which never used. Following code use Tomcat's specific classes, but it's demonstrate the idea and can be easy adopted for any robot.

public class HeapSort {

    private final RTreeEntry[] array;
    private int i;

    public HeapSort(RTreeEntry[] array) {
        this.array = array;
        for (int i = array.length / 2; i >= 0; i--) {
            downHeap(i, array.length);
        }
        i = array.length - 1;
    }

    public void sortLastN(int n) {
        for (; i > 0 && i >= array.length - n; i--) {
            final RTreeEntry temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            downHeap(0, i);
        }
    }

    private void downHeap(int k, int n) {
        RTreeEntry newElem = array[k];
        int child;

        while (k < n / 2) {
            child = (2 * k) + 1;
            if (child < n - 1 && array[child].location.roundTime < array[child + 1].location.roundTime) {
                child++;
            }
            if (newElem.location.roundTime > array[child].location.roundTime) {
                break;
            }
            array[k] = array[child];
            k = child;
        }
        array[k] = newElem;
    }

}

Usage of this class:

    int sortedEntris = BULLETS_PER_LOG;
    final HeapSort heapSort= new HeapSort(entries);
    heapSort.sortLastN(BULLETS_PER_LOG);    
    // other stuff
    for (int i = entries.length - 1; i >= 0; i--) {
        if (notShadowedBulletsCount == BULLETS_PER_LOG) {
            break;
        }
        if (i < entries.length - sortedEntris) {
            int entriesToSort = BULLETS_PER_LOG - notShadowedBulletsCount;
            sortedEntris += entriesToSort;
            heapSort.sortLastN(sortedEntris);
        }
        final LoadedRTreeEntry<UndirectedGuessFactor> entry = (LoadedRTreeEntry<UndirectedGuessFactor>) entries[i];
        // other stuff
    }