Imagine a case where comparison of two elements is hugely expensive.

Which sorting algorithm would you use?

Which sorting algorithm uses the fewest comparisons in the average case?

What if you can expect a lot of the compared elements to be identical, say in 80% of the comparisons. Does it make a difference?

Distribution sort (using a hashing array) takes almost no comparisons.

```
m = max number may appear in the input + 1
hash = array of size m
initialize hash by zeroes
for i = 0 to n - 1
hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
while hash[i] > 0
sorted[j] = i
j = j + 1
hash[i] = hash[i] - 1
```

Have a look at this wikipedia link Your choice of data structure also impacts the sort.

Shellsort uses less comparisons.

And you have lot of identical elements, Counting sort should do the job

The winner is Sleep Sort, which uses no comparisons.

Sorting is one of those subjects where, as they say, *the devil is in the details.* Typically, secondary considerations dominate the performance input parameters.

However, if comparisons are very expensive and if most keys are identical, it is possible that the input could be considered already sorted or already almost sorted.

In that case, what you want is a reasonable algorithm that has the fastest *best case,* and that would almost certainly be *an insertion sort*.

It's depends what data do you have. You need stable algorithm or not?

Where your data are uniformly you can use bucket sort ( Θ(n), O(n^2))

counting sort (I think it's what you are looking for), it's also stable algorithm, but need more memory (less is you have a lot of identical records).

Of course you can use Sleep sort, but if you have a lot of data it won't works.

If your elements are in 80% identical maybe there is a simple way to said there are identical (just the same)?

Similar Questions

I have an array of 64 structs that hold a decent amount of data (struct is around 128 bytes, so that's 8192 bytes that need to be re-arragned). The array needs to be sorted based off a single unsigned

Is that thing using bubble sort? Or what exactly? How does it work in context with an NSFetchRequest of Core Data?

Design an efficient algorithm to sort 5 distinct - very large - keys less than 8 comparisons in the worst case. You can't use radix sort.

I have seen acrosss in a company interview test this question, but i am not clear about the question first. Could you people clarify my doubt ? Question : Write a program to sort an integer array whi

What sorting algorithm is this? I thought of this method last night and quickly drew up some code, and to my surprise worked perfectly. I've been looking through the Wikipedia article on sorting algor

Do any one know which sorting algorithm is used by .net when we implement IComparer in our class?

Is there a viable alternative in T-SQL to a nested IF ELSE for comparisons in which different logic must take place based on the result of the comparison? My situation is involves selecting a nvarchar

Does KMP(Knuth–Morris–Pratt) algorithm perform fewer comparisons than the simplified Boyer-Moore algorithm?

An in-place algorithm with O(n) running time that rearranges an unsorted array A[0 . . . n − 1] filled with distinct integers so that, for a given k (1<=k<=n), A[0 . . . k − 1] contains the k sm

What is the most efficient algorithm for grouping identical items together in an array, given the following: Almost all items are duplicated several times. The items are not necessarily integers or a

I'm looking to sort an array of about 200-300 objects, sorting on a specific key and a given order (asc/desc). The order of results must be consistent and stable. What would be the best algorithm to u

I am trying to see if it is all possible to login to a website after which I will make calls to extract some data. I am doing the latter from one website which doesn't require a login as so: doc = Jso

I am using the following algorithm, which I found on the internet and modified a little to find the median of three: private static List<int> quicksort(List<int> arr) { List<int> loe

Do anyone here have any useful code which uses reduce() function of python? Is there any code other than the usual + and * that we see in the examples? Refer Fate of reduce() in Python 3000 by GvR

I need a stable sorting algorithm for .Net Doubles that is faster than O(n log n). I am thinking of Radix sort. However if I understand correctly, it's performance is O(n k) and since I'm sorting Doub

Having a sequence, I need to find out which table.column gets its values. As far as I know, Oracle doesn't keep track of this relationship. So, looking up for the sequence in source code would be the

Which sort algorithm works best on mostly sorted data?

I was reading sorting method which include bubble sort, selection sort, merge sort, heap sort, bucket sort etc.. They also contain time complexity which help us to know which sorting is efficient. So

Which cryptography algorithm is the most secure that ships with .net?

hoping I can get a little advice on a sorting method I made. This is just a test for another program i am making and this test has a bug I can't figure out. The purpose of this code is to create a int

I've been searching for a while now, but i can't find what algorithm does visual c++ use for the std::sort function, i know the GNU Standard C++ library uses Introsort, but there doesn't seem to be an

Given the maximum element M of array with n elements [1,...,n], how the lower bound Ω(nlogn) of time complexity of every comparison based sorting algorithm is affected? I must highlight that the maxim

How does hdfs determine which data block to be stored on which node?There must be some algorithm on choosing the data nodes for data blocks.I would like to learn about that.

I read about Big-O notation. I understood some idea but when compared two algorithm I don't understood some thing look following he say existing two algorithm. First f2(n) = 2n + 20 steps. second f3(

Can anyone explain me this sentence please? The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in t

I have a list of random integers. I'm wondering which algorithm is used by the list::sort() method. E.g. in the following code: list<int> mylist; // ..insert a million values mylist.sort(); EDI

I made an algorithm for sorting but I then I thought perhaps I had just reinvented quicksort. However I heard quicksort is O(N^2) worst case, however I think my algorithm should be only O(NLogN) worst

i am new to JMS API. i want to know that whether JMS API uses any Protocol to transfer Messages? if yes ,which protocol ? i have read many articles over the net but i couldn't find an answer for this

I would like an example Android app which uses onResume, onStart and onRestart.

Hi I have a generic bubble sort algorithm which I am using and I want to track the number of comparisons that occur before the array is sorted. The number of comparisons must be stored in an array lis

I am trying to sort a Dynamic Array that contains Costs as elements. This is my sorting function: void ascending_sort(Controller* ctrl) //the function is in the controller { int i,j; DynamicVector* Co

I'm curious what algorithm Lua's default table.sort uses, only because it's slower than some other sorting algorithms I've come across. I'm also curious if Lua's table.sort is written in the Engine in

For ruby where x is an array, how does x.include?(y) check if y is in x? What's the algorithm?

What is the minimum number of comparisons under best case scenario for KMP algorithm ?

I'm using Mahout (v 0.7) parallel FPG algorithm, CLI mode, to generate frequent patterns. The algorithm works fine and generates the frequent patterns correctly. The problem I'm having is that the alg

I have the following MySQL query which works perfectly but runs incredibly slowly at times. SELECT s.ID AS `Student_ID` , IFNULL( COUNT( f.ID ) , 0 ) AS `Flags` , IFNULL( COUNT( i.ID ) , 0 ) AS `Inte

I have 4 sorting algorithms (linear, frequency, binary and hash table) for sorting lists of words. I need to analyse the number of comparisons that each makes, given a list of n words and compare them

It should quite simple algorithm, but I just can't get around it. I have some arrays in alphabetical order [0] => Array ( [0] => a [1] => b [2] => c ) and for example [0] => Array ( [0

I have a set of rectangles and I would like to reduce the set so I have the fewest number of rectangles to describe the same area as the original set. If possible, I would like it to also be fast, b

I have an ASP.NET application, which use some files in project directory (license, logs, etc). And I need method to check for file permissions. I wrote this one: public static bool IsCurrentUserHaveAc

Is there any algorithm that makes it parallel sorting of a linked list worth it? It's well known that Merge Sort is the best algorithm to use for sorting a linked list. Most merge sorts are explained

I need to write a sorting program in C and it would be nice if the file could be sorted in place to save disk space. The data is valuable, so I need to ensure that if the process is interrupted (ctrl-

Dijkstra's algorithm uses a priority queue which is ordered by the distances from the starting point, however the distances of the vertices are changeing during the algorithm. I am not sure when does

After reading this question and through the various Phone Book sorting scenarios put forth in the answer, I found the concept of the BOGO sort to be quite interesting. Certainly there is no use for th

I'm having an issue with time comparisons with PHP - I think I must be doing something stupid but I've been trying different things for hours now and I'm just hitting a brick wall. I'm pulling data fr

According to my research and googling, Javascript seems to lack support for locale aware sorting and string comparisons. There is localeCompare(), but it has been reported of browser specific differen

Possible Duplicate: for vs foreach vs while which is faster for iterating through arrays in php For each and while, which of these is faster, recommended, and what are their resource usages like?

I believe that out there we have algorithms implementations (e.g. a c++ implementation of a particular sorting algorithm) which might not be as efficient as they could be. I would like to write a rese

Is it possible to sort an array with Unicode / UTF-8 characters in PHP using a natural order algorithm? For example (the order in this array is correctly ordered): $array = array ( 0 => 'Agile', 1

I have a rendering application that renders lots and lots of cubes in a 3-dimensional grid. This is inherently inefficient as each cube represents 4 vertices, and often the cubes are adjacent, creatin