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 :D

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.

Quote:

---

Originally Posted by dlwlsdn

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

---

This would be the case for a "canonical" version of quick sort that picks the first element of each partition as the pivot. As tabstop noted, there are other pivot selection strategies available, e.g., median of three and random. Introsort is an example of another take on the situation: when the recursion depth exceeds some limit (indicating that pathological worst case might be present), the algorithm switches to heap sort, which does not suffer from quadratic time worst case.

Quote:

---

Originally Posted by dlwlsdn

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

---

Depending on what are the "things", 1 million might still be okay. But if it is not, you might not even want to use quick sort in that case, e.g., you might want to use a version of merge sort applied to files, and only switch to quick sort for sufficiently small partitions.