(New page: == Sorting floating numbers == by Daniel Lee Last Edit: 27 January 2013 ---- '''Introduction''' It's well known that the comparison sorting algorithms have a theoretical lower bound of <m...) |
|||
| Line 4: | Line 4: | ||
---- | ---- | ||
| − | ''' | + | '''INTRODUCTION''' |
| + | |||
| + | During a CS251: Data Structure & Algorithms lecture about various sorting algorithms, Professor A 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 <math>n \log n</math> | It's well known that the comparison sorting algorithms have a theoretical lower bound of <math>n \log n</math> | ||
| + | |||
| + | '''Floating Point Numbers''' | ||
| + | |||
| + | |||
| + | |||
| + | '''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 | ||
| + | |||
| + | ---- | ||
[[user:lee832|back to Daniel Lee's Profile Page]] | [[user:lee832|back to Daniel Lee's Profile Page]] | ||
Revision as of 03:55, 28 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 A 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 $ n \log n $
Floating Point Numbers
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
