Difference between revisions of "DYL RADIXFLOAT" - Rhea

Revision as of 09:05, 31 January 2013

Sorting floating numbers

by Daniel Lee Last Edit: 27 January 2013

INTRODUCTION

During a CS251: Data Structure & Algorithms lecture about various sorting algorithms, Professor Aliaga mentioned a sorting algorithm of linear running time - radix sort. While showing us how radix sort can be used to sort binary numbers, he added that radix sort is not a general-purpose sorting algorithm, and our lower-bound for comparison sorts are still set at O(nlogn). But I wonder - all digital objects are represented as 0/1 in memory. Can I use radix sort to sort objects like floating point number whose binary structure is well defined?

PRELIMINARIES

Radix Sort

It's well known that the comparison sorting algorithms have a theoretical lower bound of nlogn. Therefore, we can have something radix sort, which fall outside the category of of comparison sort, that attains status of linear time sorting algorithm. To illustrate the maneuvers of radix sort, I first introduce bucket sort with an illustrative example:

Suppose you have a collection of marbles. You want to sort the marbles out categorically, say its color. You can easily sort out the marbles by going through each marble and placing them inside a "bucket" labeled blue, red, orange, yellow, etc, and Viola! your marbles are sorted.

I concede that the above example is incredibly simple, but it is only so because radix sort itself stems from a simple method. Now consider an example of radix sort:

Say you would like to sort 4 numbers, each represented by 4 binary digits: 0101 0111 1011 1000 We prepare two buckets, labeled "1" and "0" and do the following:

1. Look at the 1st digit (count from the least significant) and throw the number into corresponding bucket

"0" = (1000) "1" = (0101, 0111, 1011) Note that the order in which the numbers are stored is of importance (I chose (-) instead of {-} or [-] to emphasize this)

2. Repeat 1 for kth digit from k = 1:4, maintaining its relative order. Elements in bucket "0" is given the lower ordering than the items in bucket "1".

k = 2: "0" = (1000, 0101) "1" = (0111, 1011)

k = 3: "0" = (1000, 1011) "1" = (0101, 0111)

k = 4: "0" = (0101, 0111) "1" = (1000, 1011)

3. Collect the elements, starting from bucket "0" and maintaining its relative order. Viola! The numbers are now sorted.

Since it takes n*constant steps to categorize and throw each item into a bucket for each bit, the total time it takes to sort n number is given by n*constant *k where k = number of bits. Since k is usually 32 or 64 bits and therefore a constant, radix sort can sort n integers in O(n).

Floating Point Numbers

Integers can be represented as binary in a intuitive sense, but how can we represent decimal numbers with a decimal point? The basis of floating point number representation is not unlike the scientific notation we are familiar with

TASKS

1. Implement radix sort for integers (CHECK)

2. Investigate how floating point is represented in memory and device a method to sort floating point numbers

3. Implement modified radix sort for floating point numbers

4. Naive analysis of running time?

RESULTS

TBUploaded

back to Daniel Lee's Profile Page