Sign in to follow this  
vaneger

Sorting array question

Recommended Posts

Depending on many factors, there is a dedicated area of research under Optimal Sorting.

It is possible to sort the array using 4 assignments only - just write the values in correct slots.

Fastest method would require no action, since elements would already be sorted.

As far as compare and swap class of algorithms goes, there are limits on numbers of comparisons and swaps for n elements.

Share this post


Link to post
Share on other sites
Given an array of 4 elements, you're probably best off with something ultra-simple like selection sort which can sort easily in place. There are better general-purpose sorting algorithms, but they require overheads which would make them slower on arrays that small.

Share this post


Link to post
Share on other sites
At that size even bubble sort would do well!

However since you're wanting to generate the number of the permutation in order to undo the sorting in your decompressor later, you can probably kill two birds with one stone by using selection sort.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this