Results 1 to 3 of 3

Thread: Radix sort! Faster than heap!

  1. #1

    Thread Starter
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221

    Thumbs up

    Well everyone probably knows that quicksort is quick, and heapsort is even quicker, but did you know radixsort was even quicker than heapsort? Anyway i found this code but it's in java and it's a bit hard to understand. I've just got on my first introduction course on java so i tried but couldn't convert this into vb.

    Any Java-gurus that could convert this for me?
    Code:
    // RadixSort.java version 1.2
    // Java Source code for RadixSort
    
    
    package cmp.RadixSort;
    // if using JDK 1.2
    // import java.util.Comparator;
    
    /* Copyright (c) 1996-2000
     * Roedy Green
     * Canadian Mind Products
     * #208 - 525 Ninth Street
     * New Westminster, BC Canada V3M 5T9
     * tel: (604) 777-1804
     * mailto:roedy@mindprod.com
     * http://mindprod.com
     */
    
    /*
     version 1.1 1998 November 10 - add name and address.
     version 1.2 1998 December 28 - use JDK 1.2 style Comparator interface.
     version 1.3 2000 September 29 - fix bug.  Was not sorting first column
     */
    
    // May be freely distributed for any purpose but military.
    
    // RadixSort beat HeapSort which beat QuickSort.
    // RadixSort works in linear time.  It is a
    // little harder to use than ordinary sorts,
    // but it can handle big sorts many times faster.
    // Its main weakness is small sorts with long
    // keys. The sort is stable.  It does not disturb
    // pre-existing order of equal keys.
    /**
     * RadixSort for objects
     */
    
    
    public class RadixSort
    {
    
        private static final String EmbeddedCopyright =
        "Copyright 1996-2000 Roedy Green, Canadian Mind Products, http://mindprod.com";
    
        private static final boolean debugging = false;
    
        // callback object we are passed that has
        // a getKeyByteAt(Object a, int offset) method.
        private RadixComparator delegate;
    
        // pointer to the array of user's objects we are sorting
        private Object [] userArray;
    
        // pointer to source work array
        private Object [] sourceArray;
    
        // pointer to target work array
        private Object [] targetArray;
    
        // how many bytes long the sorting key is.
        private int keyLength;
    
        // used to tally how many of each key byte there were.
        private int [] counts;
    
        // create a RadixSort object and sort the user's array
        public static void sort (
                                Object [] userArray,
                                RadixComparator delegate,
                                int keyLength )
        {
            RadixSort h = new RadixSort();
            h.delegate = delegate;
            h.userArray = userArray;
            h.keyLength = keyLength;
            if ( h.isAlreadySorted() ) return;
            h.radixSort();
            if ( debugging )
            {
                // debug ensure sort is working
                if ( ! h.isAlreadySorted() ) System.out.println("Sort failed");
            }
            return;
        } // end sort
    
        // radixSort that works like a mechanical card
        // sorter, sorting least significant byte of the
        // key first. This works in linear time
        // proportional to key length and number of items
        // sorted.
        private void radixSort()
        {
            counts = new int[256];
            sourceArray = userArray;
            targetArray = new Object[userArray.length];
            // sort least significant column first,
            // working back to the most significant.
            for ( int col=keyLength-1; col>=0; col-- )
            {
                sortCol(col);
                // swap source and target, very quick, just swapping pointers
                Object [] temp = sourceArray;
                sourceArray = targetArray;
                targetArray = temp;
            } // end for
    
            // copy results back to userArray, if necessary
            if ( sourceArray != userArray )
            {
                System.arraycopy(sourceArray,0, userArray,0, sourceArray.length);
            }
        } // end radixSort
    
        // sort sourceArray by given column.  Put results in targetArray
        private void sortCol (int col)
        {
            // pass 1 count how many of each key there are:
            for ( int i=0; i<counts.length; i++ )
            {
                counts[i]=0;
            }
            for ( int i=0; i<sourceArray.length; i++ )
            {
                counts[delegate.getKeyByteAt(sourceArray[i],col)]++;
            } // end for
    
            // calculate slot number where each item will go.
            {
                int soFar = 0;
                for ( int i=0; i<counts.length; i++ )
                {
                    int temp = counts[i];
                    counts[i] = soFar;
                    soFar += temp;
                } // end for
            } // end block
            // pass 2 move each object to its new slot
            for ( int from=0; from<sourceArray.length; from++ )
            {
                int keyByte = delegate.getKeyByteAt(sourceArray[from],col);
                int to = counts[keyByte]++;
                targetArray[to] = sourceArray[from];
            } // end for
        } // end sortCol
    
        // check if user's array is already sorted
        private boolean isAlreadySorted()
        {
            for ( int i=1; i<userArray.length; i++ )
            {
                if ( delegate.compare(userArray[i],userArray[i-1]) < 0 )
                    return false;
            }
            return true;
        } // end isAlreadySorted
    
    } // end class RadixSort
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  2. #2
    Lively Member
    Join Date
    Aug 2000
    Posts
    125
    see the sort timer and viewer for VB routines at:

    http://pages.about.com/vbmakai/

    radix sorts use multi arrays to hold sorted data
    as such there is no guarantee it is more stable that a
    quick sort

  3. #3

    Thread Starter
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    Yeah well i thought that I could have use for it anyway, quicksort haven't given me any out of stack spaces yet
    Radix wasn't in the list? ALso sorting methods get's effective at certain areas, large keys to sort, or many items or how scrambled the items are.
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width