CODEWITHSUNDEEP
algorithmsorting
MyNameIsMy
MyNameIsMy

Reputation: 193

Which sorting algorithm is faster?

Shell sort or odd-even transposition?

In my tests come Even-odd transposition sort is faster, correct?

Upvotes: 0

Views: 1760

Answers (6)

malejpavouk
malejpavouk

Reputation: 4445

Shell sort may be implemented with many variants of a initial gap size and its decrement in every step. The original algorithm is O(n^{3/2}), but some improvements were presented by Hilberd, Sedgewick and Ciura. So if you are asking which is better, you must always say which implementation do you use. So a single core shell sort should win on every sufficiently large dataset. On multiple cores will probably win odd-even sort, because it can use more processing units.

Upvotes: 0

wildplasser
wildplasser

Reputation: 44240

In most non-trivial case it does make sense to code your own sorting algorithm, but not all cases are non-trivial. It all depends on what you know about the data being sorted. There are even cases where bubblesort is a valid choice (or maybe even optimal).

Upvotes: 0

mike jones
mike jones

Reputation: 659

In most cases it doesn't make sense to code your own sort algorithm. Nearly every environment has a built-in sort that should be your first choice. Even-odd transposition is O(n^2) for the worst data (on a single core).

Upvotes: 1

N3dst4
N3dst4

Reputation: 6435

If I remember correctly, odd-even sort is very similar to bubble sort, but it can be executed in parallel.

On a single CPU core, Shell sort is generally better, but bubble/odd-even may win on small datasets.

Upvotes: 1

lhf
lhf

Reputation: 72312

Shell sort is faster for large arrays. How large you need to take the array before you see that depends on your implementation of both algorithms.

Upvotes: 0

Pablo Santa Cruz
Pablo Santa Cruz

Reputation: 181280

It depends on your data layout.

But QuickSort is a pretty general purpose sorting algorithm if what you are going to sort is not huge. If you are planning to sort huge amounts of data, then you need something with intermediate memory such as MergeSort.

Upvotes: 3

Related Questions