Best algorithm for sorting a nearly sorted array?

[Armitage]

I'm sure a few minutes of googling will turn it up, but there haven't been many actual programming threads lately.

I've got an aplication that has to sort a few arrays every time step - each about 10,000 objects. But they should be nearly sorted from one timestep to the next.

I'm using the standard quicksort at the moment but I'm thinking bubble sort should do pretty good - it'll be O(n) for a completely sorted list.

 

[notfred]

I'd just stick with quicksort unless it's really too slow. If you switch to bubble sort you might get a small performance increase until that one time that a list is all out of order and it takes forever.

 

[Armitage]

Originally posted by: notfred
I'd just stick with quicksort unless it's really too slow. If you switch to bubble sort you might get a small performance increase until that one time that a list is all out of order and it takes forever.

Well, by the physics of the situation, it can't ever get *really* badly out of order after the first sort. But I agree - the difference may not be appreciable. 10,000 really isn't that big.

 

[clamum]

Quicksort performs poorly if the sequence to be sorted is almost or nearly sorted: O(n^2). Heap-sort or merge-sort I believe should do it in O(n log n) time.

EDIT: With the sequence size being 10,000, I'm not sure if this makes a noticeable impact though.

 

[Armitage]

Originally posted by: clamum
Quicksort performs poorly if the sequence to be sorted is almost or nearly sorted: O(n^2). Heap-sort or merge-sort I believe should do it in O(n log n) time.

EDIT: With the sequence size being 10,000, I'm not sure if this makes a noticeable impact though.

Yep - but it sorts those 10000 element arrays alot.
Anyway, maybe I'll play with it a bit tomorrow.

 

[clamum]

Originally posted by: Armitage

Originally posted by: clamum
Quicksort performs poorly if the sequence to be sorted is almost or nearly sorted: O(n^2). Heap-sort or merge-sort I believe should do it in O(n log n) time.

EDIT: With the sequence size being 10,000, I'm not sure if this makes a noticeable impact though.

Yep - but it sorts those 10000 element arrays alot.
Anyway, maybe I'll play with it a bit tomorrow.

I'd be interested to see what the results are. That fact about quicksort has stuck in my head since my data structures and algorithms class... finally it's been put to use! Haha.

 

[Thyme]

Quicksort will be O(N^2) unless it is comparing items randomly. Heapsort of Mergesort or another O(nlogn) algorithm will be better.

 

[itachi]

divide and conquer algorithms are ineffecient with partially sorted lists.

i'd go with shell-sort. it allows more adjustment as time passes, and works better with sorted lists (trait of insertion sort).

 

[Armitage]

Turns out the STL sort doesn't use quicksort any more - it uses introsort (http://www.sgi.com/tech/stl/sort.html) which apparently gets around quicksorts quadratic worst case scenario. So there's not much point. I wrote a merge-sort anyway, but the performance completely sucks, and I'm not inclined to dig into why just now.