Serious Fragmentation How do I fix it?

9600 G3

I have a seriously fragmented OS X Drive and Norton Utilities says it can not optimize it. Now what do I do. I am afraid to try to run Disk Doctor that just seems like a bad idea. Any Suggestions?
Sometimes the best way to get rid of problems with a hard drive is to reformat it. If I were you I would do some back up of anything you dont want to loose from your HD, then start up from the disc that came with your computer and reformat using Drive Setup. Also, if your going to install the Mac OS X beta it's a good idea to partition your HD giving the beta at least 1.5 GB of space if you haven't already. That's just my suggestion.
I have OS X on a seperate 6gb partition. Is Norton safe to use on OS X? I highly doubt it but, I am afraid to try.