Solved

Sorting alogorithm

Posted on 2011-03-01
5
954 Views
Last Modified: 2012-05-11
Please tell me which sorting algorithm is most efficient when the data:
1. has very few unique elements
2. is in reverse sorted order.

Also, please tell me the complexity in each case.

Thanks!
0
Comment
Question by:dshrenik
5 Comments
 
LVL 9

Expert Comment

by:rawinnlnx9
ID: 35012615
Come on. This is homework. Go read up on Big O notation and binary trees. 20 minutes of light reading and you should be able to figure this out.

Here: http://warp.povusers.org/SortComparison/
0
 
LVL 20

Expert Comment

by:edster9999
ID: 35012633
Read something like this :
http://en.wikipedia.org/wiki/Sorting_algorithm

If you need more detailed info you will have to provide sample data or more information.
The question sounds a bit like an exam or homework question.  if this is the case you are supposed to specify that.
0
 

Author Comment

by:dshrenik
ID: 35012654
Its not a homework problem. I'm preparing for an interview.
I'm trying to identify the best algorithm for various scenarios:
When values are in a small range - Bucket sort
Nearly sorted - Insertion sort, etc.
0
 
LVL 20

Expert Comment

by:edster9999
ID: 35012782
As above the links tell you all there is to know about sorting.   The formulas give you the rough time / memory / number of steps it takes to sort the field as the size etc increases.
You need to understand the idea of things like 'the big O'
If you understand that and you are able to code the basic sort functions then you can talk about it in an interview.
read, read, read....
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 35014010
If it's in reverse sorted order, then just flipping it is best. Time complexity is O(n). You could implement some kind of 'groupsort' than keeps all the same elements together.
For the traditional algorithms, you won't get better than O(nlg(n)) anyway. But if you do 'groupsort' you could get O(n + mlg(m)) where m is the number of unique elements.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Lowest common IP of a range of IPs 6 295
How to  Transpose data in Excel through formula or code? 13 255
Math between Excel and approximations 15 110
Help with Javascript syntax 4 110
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
This video shows how to quickly and easily add an email signature for all users on Exchange 2016. The resulting signature is applied on a server level by Exchange Online. The email signature template has been downloaded from: www.mail-signatures…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question