Thread: Need help to check sort

Hello everyone.

So through my journey of all these different algorithms of sorting, I came across quick sort. Which is pretty tight, does everything, very nice and everything, but I realized... quick sort's weakness... its weakness is a sorted list :P

I got my code written and everything on getting a unsorted data sorted, but how would I check to see if the data is already sorted, and I don't wanna print it out to check..

What if there is like 1million inputs of data... don't wanna read 1 million things :P.

Thanks ya'll

Double check the sorting part of your code? You have to nail that down either way, it's your only option though if you don't want to inspect some small portions of the list. Write a program to take some random samples and compare them to see if they're sorted locally...

Depending on how much time you want to spend, you can just check the first so many. Something like

Code:

already_sorted = true
if (first > second)
    already_sorted = false
else
    move first, second up one spot
    repeat

EDIT: Although doing something like picking the pivot in a better way will really eliminate the need for this sort of thing.

Depending on your data, you could try counting sort or radix. The worst you'll waste is linear time.

It's your job as a programmer, to know what kind of data you'll be sorting. If the data has any reasonable chance of being in already sorted order, then use Introsort. It uses Quicksort, but also checks to see if lilttle progress is being made during the sort. When it detects that is happening, it switches over to heap sort, and very little time is wasted.